Take quiz & check grades
Hashing Tables
 | Motivation: If key can be used as index to array, search is O(1). |
| Keys as index may not be practical in several situations. |
Hash tables:
Try to achieve efficiency of arrays.
Hashing Functions:
map a key into an index for the array. If array has N entries, key should be mapped to an integer between 0 and N-1 (or 1 and N). Assume the key is an integer or may be treated as an integer.
| Division Method: Using an array of size N, divide the key by N and take the remainder as an index. Some values of N are better than others. Typically, use a prime N. |
| Multiplication Method: Divide the key by a number A ( 0<A<1) and take the fractional part of the number. Multiply this fractional part by the number of elements in the array to obtain the index. |
| Universal Hashing: Use a collection of functions. Select one function at run time. |
Collision:
Some keys will map to same index. How will you handle collisions?
| Linked list: Instead of array of records, use an array of linked lists of records.
| ||
| Open addressing: Use vacant positions of the array for the colliding records |
Properties:
| number of elements stored: n |
| number of indexes in the array: m |
| load factor: (alfa= n / m) |
| simple uniform hashing: assume each element is equaly likely to hash into any of the m slots |
Theorem 12.1:
Hash table with collisions handled by chaining, unsuccessful search takes Teta(1+alfa) on the average.
Theorem 12.2:
Hash table with collisions handled by chaining, successful search takes Teta(1+alfa) on the average.