Hashing

Hashing

Data Structures
1. Associative Array or Dictionary
O(1) to find any record
Hash Functions
1. Should produce hash codes that are (almost) uniformly random
2. Hashing methods
  1. Division
    1. Use prime number as table size, m
    2. Convert keys, k, into integers
    3. use remainder, h(k) = k % m as hash value
  2. Folding
    1. Divide the int key, k, into sections
    2. Add, subtract and/or multiply them, combining them into the hash code
  3. Middle-Squaring
    1. Choose a middle section of the int key, k
    2. Square the chosen section
    3. Use middle section of hat result as hash key
  4. Truncation
    1. Delete part of the key, k
    2. Use remaining part as hash key
Hash Collisions
1. The Perfect Hash Function is one that gives a different hash code for every key
2. A Minimal hash function is when the number of keys n equals the array size m
3. Collision Resolution Policy
  1. OALP - Open Addressing with Linear Probing
    1. Successive search for first entry with matching key at lower location in table
    2. If no such entry, "Wrap around" the table
    3. Clusters keys together
  2. OADH - OA with Double Hashing
    1. Hash a collided key again with a different hash function
    2. Use result of second hashing as increment for probing table locations
  3. Other Techniques
    1. Hash Buckets
      1. 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
    2. Chaining
      1. All records for a single hash address are kept in a linked list, or chain, started at that address
Desired Properties for a good Hashing theme
1. Hash locations spread out
2. Use relatively small table size, that doesn't affect performance
3. The function h is fast to compute

Next up

Description

Resource summary

0 comments

Similar

	Created by dadelgado01 over 10 years ago