Hashing

Hashing

1. Data Structures

   • Associative Array or Dictionary

2. O(1) to find any record

3. Hash Functions

   • Should produce hash codes that are (almost) uniformly random
   • Hashing methods
     • Division
       • Use prime number as table size, m
       • Convert keys, k, into integers
       • use remainder, h(k) = k % m as hash value
     • Folding
       • Divide the int key, k, into sections
       • Add, subtract and/or multiply them, combining them into the hash code
     • Middle-Squaring
       • Choose a middle section of the int key, k
       • Square the chosen section
       • Use middle section of hat result as hash key
     • Truncation
       • Delete part of the key, k
       • Use remaining part as hash key

4. Hash Collisions

   • The Perfect Hash Function is one that gives a different hash code for every key
   • A Minimal hash function is when the number of keys n equals the array size m
   • Collision Resolution Policy
     • OALP - Open Addressing with Linear Probing
       • Successive search for first entry with matching key at lower location in table
       • If no such entry, "Wrap around" the table
       • Clusters keys together
     • OADH - OA with Double Hashing
       • Hash a collided key again with a different hash function
       • Use result of second hashing as increment for probing table locations
     • Other Techniques
       • Hash Buckets
         • Divide a big hash table into several small sub-tables, or buckets
           • Hash function maps key into one of the buckets
           • Keys are stored in each bucket in sequentially increasing order
       • Chaining
         • All records for a single hash address are kept in a linked list, or chain, started at that address

5. Desired Properties for a good Hashing theme

   • Hash locations spread out
   • Use relatively small table size, that doesn't affect performance
   • The function h is fast to compute