hash_functions

hash_functions.rst

Hash Functions

A hash table is a data structure that implements an dictionary abstract data type, and is used to map keys to values.

                         array (key)
                           ┌───┐
                         0 │ ⊙─┼─► value
                           ├───┤
                         1 │ ⊙─┼─► value
                           ├───┤
                         2 │   │  A Hash table is implemented by using a large array.
                           ├───┤  This is usually called the table's "backing array
                         3 │   │  because it backs the hash table.
                           ├───┤
To place an item A       4 │   │
into the backing array,    ├───┤
calculate a hash value.  5 │   │
                           ├───┤
                         6 │   │
                           ├╶╶╶│
               ┌──────┐    │   │
     "cab" ──► │ hash │    │   │
               │ func │    │   │
               └───┼──┘    │   │   Multiple items might have the same hash value.
                   │       │   │   This is called a collision. There are 2 ways
                   │       │   │   to handle collisions: chaining and linear probing.
                   │       ├╶╶╶│
                   │       │   │     linked-list
                   │       ├───┤    ┌───────┬───┐  ┌─────────┬───┐
                   └──► 98 │ ⊙─┼──► │ "cab" │ ⊙─┼──┼─► "cat" │ ⊙─┼────►
 the hash value is         ├───┤    └───────┴───┘  └─────────┴───┘
 then mod(%) with       99 │   │
 the array size.           └───┘

Additional Notes:

• Load Factor is the Number of Entries in the Hash Table divided by the size of the backing array. The higher the load factor, the greater the probability of collisions.
• A Load factor of 0.75 is generally considered a good point to double the size of the backing array.
• When you resize the backing array, you have to remap all the entries in the table.

Requirements:

1. Deterministic
2. Evenly distributed
3. Should use all values of the input

Hash Codes:

To generate hash codes, we use polynomials. We set x to a prime number, (e.g, 31, 53 or 101).