Každá hodnota má svoj index.
Mapovanie Index => Hodnota
int pole[4] = {4,3,2,1};
index: 0 1 2 3
+------+------+-------+-------+
hodnota: | 4 | 3 | 2 | 1 |
+------+------+-------+-------+
adresa: \#10 \#14 \#18 \#22Zovšeobecnenie klasického poľa
Mapovanie Kľúč => hodnota.
NOTE: Kľúč je väčšinou reťazec.
index: prvy druhy treti stvrty
| | | |
v v v v
+------+------+-------+-------+
hodnota: | 4 | 3 | 2 | 1 |
+------+------+-------+-------+Množina údajov, kde sa kľúč nemôže opakovať.
Kľúč a hodnota by mali byť blízko pri sebe.
Súčasťou informácie o hodnote by mal byť aj kľúč.
struct asoc {
char key[20];
int value;
};
struct asoc array[10];Má všetky nevýhody klasického poľa (lineárna zložitosť skoro všetkých operácií).
+-------------+---------------+
| prvy 3 | druhy 1 |
+-------------+---------------+NOTE: Vo všeobecnosti je HT lepšia ako BVS.
index: prvy druhy treti stvrty
|| || || ||
\/ \/ \/ \/
hash: 0 1 2 3
|| || || ||
\/ \/ \/ \/
+------+------+-------+-------+
slot | 4 | 3 | 2 | 1 |
+------+------+-------+-------+Slot je miesto pre jednu hodnotu v HT
n / m - očakávaný počet hodnôt v jednom slote.
n:: počet hodnôt
m:: - počet slotov (možných hodnôt hash funkcie).
index: prvy treti
|| ||
\/ \/
hash: 0 2
|| ||
\/ \/
+------+------+-------+-------+
slot | 4 | | 2 | |
+------+------+-------+-------+[quote, Mastering Algorithms] The primary idea behind a hash table is to establish a mapping
between the set of all possible keys and positions in the array using a hash function.
[quote, Introduction ot Algorithms] Many applications require a dynamic set that supports only the dictionary
operations INSERT , SEARCH , and DELETE.
[quote, Introduction ot Algorithms] A hash table is an effective data structure for implementing dictionaries.
Although searching for an element in a hash table can take as long as searching for an element in a linked list—‚.n/ time in the worst case—in practice, hashing performs extremely well. Under reasonable assumptions, the average time to search for an element in a hash table is O.1/. A hash table generalizes the simpler notion of an ordinary array.
Funkcia, ktorá ľubovoľne veľkej hodnote priradí hodnotu fixnej veľkosti.
WARNING: Je možné, že dva rôzne vstupy majú rovnakú hodnotu hešovacej funkcie.
Funkcia, ktorá hodnote a priradí hodnotu b, tak že pre ľubovoľné b existuje maximálne jedno a.
Nepozná kolízie.
int hash_string(const char* word){
for (int counter = 0; word[counter]!='\0'; counter++){
hash = word[counter] + (hash << 6) + (hash << 16) - hash;
}
return hash;
}https://stackoverflow.com/questions/14409466/simple-hash-functions
VSTUP:: kľúč, hešovacia tabuľka
VÝSTUP:: hľadaná hodnota alebo NULL.
Mala by by priradiť indexy uniformnou pravdepodobnosťou.
[quote, Mastering Algorithms]
A hash function h is a function we define to map a key k to some position x in a hash table. x is called the hash coding of k. Formally stated: h ( k ) = x
[quote]
An alternative to the division method is to multiply the integer key k by a constant A in the range 0 < A < 1; extract the fractional part; multiply this value by the number of positions in the table, m; and take the floor of the result.
Je potrebné, aby kľúč bol uložený v hešovacej tabuľke spolu s hodnotou.
Chceme, aby všetky sloty mali približne rovnakú veľkosť.