HASH FUNCTIONS
Division method : k mod m (m is size of hash table)
Example : k = 2345 so hash value = 5 and k is stored at 5
Mid square method : k^2 * extract middle digits
Example: k = 60 so k^2 = 3600 and mid digits are 60 so hash value is 60
and k is stored at 60
K= 13 , k^2 = 169 and mid digits are 6 so hash value is 6 and k is stored
at 6
Digit folding method : fold k into equal size parts
Example : k=12345 , after folding 12+34+5 = 51 so 51 is the hash value
and k is stored at 51
Multiplication method : floor(m (kA mod 1)) where 0 < A < 1
Example : k = 12345 and A = 0.01 so floor(4.5) = 4 (hash value)
IF TWO NUMBERS HAVE SAME HASH VALUE , IT IS CALLED COLLISION
Open Hashing (Closed Addressing) : Separate chaining -> each
bucket in hash table is a linked list
Closed Hashing (Open Addressing) :
LINEAR PROBING : h(k) = k mod m
(h(k) + i) mod m [i ranges from 0 to m]
For example, when k = 634 , then (4+0) mod 10 = 4 , (4+1) mod 10 = 5
until find an empty space.
QUADRATIC PROBING : h(k) = k mod m
(h(k) + i^2) mod m [i ranges from 0 to m]
For example, when k = 634 , then (4+0) mod 10 = 4 , (4+1) mod 10 = 5
, (4+4) mod 10 = 8 until find an empty space.
If quadratic probing is used and the table size is prime, then a new
element can always be inserted if the table is at least half empty.
Double Hashing : h(k) = k mod m
(h1(k) + i h2(k)) mod m [i ranges from 0 to m]
If double hashing is used and the table size is prime, then a new element
can always be inserted if the table is not full and the second hash
function is suitable (not evaluated to 0).
In a hash table, the content stored is usually of the form (key, data).
Therefore, when you are given a specific key k, you can find the
corresponding key-based data in the table. Suppose the current slot you
are checking contains (k’, data). If k=k’, then you already find the data
you want, otherwise if k!=k’, then you go on to check the next possible
slot according to the probing rules. 2.
A number n is prime if for any integer m satisfying 1<m< n , the
inequality n%m!=0 always hold.
LOAD FACTOR
N = number of elements
M = number of buckets in hash table (size of hash table)
Load factor = n/m (avg entries in one bucket)
Generally when load factor > 0.75 , we do rehashing
REHASHING : Increasing size of hash table and redistributing elements
in it
