Hash Tables and Arrays

Hash Tables

Advantage for dealing with individual data

1. Quick insert
2. Quick remove
3. Quick lookup (*)
   • Retrive a data in a constant time
4. Quick Modify

Define Hash Table

• A hash table consists of an array to store the data in
  • The table may contain complex types or pointers to objects
  • One attribute of the object is designed as the table’s key
• A hash table also need a hash function that maps a key to an array index.
  • Collision: the hash function maps two different keys to the same index

Hash Function

• We want the keys to be distributed evenly over the underlying array
  • e.g. h(x) = x mod tableSize
  • try to avoid collision
• Hash Function should be fast and easy to calculate

Dealing with Collision

Open addressing

shortage: when a deletion happens, it may break the logic existing in open addressing.

Linear probing

• if there is collision, we should search an empty space start from current position sequentially until we find an available space.
• shortage: Linear probing leads to primary clustering

Quadratic probing

• Quadratic probing is a refinement of linear probing that prevents primary clustering.
  • For each successive probe, i, add i² to the original location index
    • e.g. 1st probe: h(x)+1², 2nd: h(x)+2², 3rd: h(x)+3², etc.
• shortage: after some time a sequence of probes repeats itself
  • Results in secondary clustering. (By analysing, this isn’t a big issue).

Double Hashing

• make another hash key h₂.

Seperate Chaining

the method seperate chaining is to put linked list in the entry of array.