] Hash Tables

1. Basic ideas

• Average case complexity for BST insert and find is O(lg n).
• We can do better, in O(1), if we give up some things.
• Take advantage of array index -- random access to A[i] is a constant time operation.
  A solution: Hash tables
  
• How do we decide the index i for a given item X? -- We need a function which maps X to i (where 0 ≤ i < tablesize).
• Basic components of a hash table:
  1. Array of size M, which is 'appropriate' to store N data items.
     • N/M ... load factor (between 0 and 1.0)
  2. A hash function which maps X to i in the range between 0 and M-1.

2. Hash Function

• Desirable Properties:
  • efficient
  • distributes X's evenly across the range for i -- for less collisions.
• But, it is (almost) impossible to know the range of values for X beforehand.  So, 'good' hash functions do the following as a best try.
  1. Look at all bytes (or bits) in X and utilize all available info in deciding i.
  2. Randomize the gathered info so that 'close' X's are assigned remote i's -- for even distribution of X's
• Example hash functions (for hashing string):

  // Example 'good' hash function (modified slightly from p. 157)
  public int hash( String key, int tableSize )
  {
    int hashVal = 0;
  
    for (int i = 0; i < key.length(); i++)
      hashVal = 37 * hashVal + key.charAt( i );
  
    return Math.abs(hashVal % tableSize); // a value between 0 and (tableSize-1)
  }

• hashCode() method in Java
  • In Java, the class Object contains a method called hashCode() and it is inherited in every class.
  • The hashCode() methods returns a hash code of the object in which the method is called.
  • Java predefined classes already have the method implemented -- so you can just call them.
  • For user-defined classes, you can write your own hashCode() method.

    public class Person
    {
      public Person(String fn, String ln, int a)
      {
        fname = fn; lname = ln; age = a;
      }
    
      public int hashcode()
      {
        String fullname = fname + " " + lname;
        return fullname.hashCode();  // hashCode() in String class --
                                     // fullname's hash code is the
                                     // hash code of a Person
      }
    
      private String fname; // first name of a person
      private String lname; // last name of a person
      private int age;      // age of a person
    }

• Collisions
  • Hash function may (will) produce the same key for two or more (different) data items.
  • Collision resolution by different strategies: 
    • linear probing
    • quadratic probing
    • separate chaining

3. Linear Probing (or "Open Addressing with linear probing")

• Every slot in the table is either:
  • null
  • non-null and marked with true -- active
  • non-null and marked with false -- deleted or inactive
• Insert -- First go to the slot which the hash function returned for an element X (initial index). Then, search sequentially until 
  • a null slot -- put the element as active there; or
  • a slot that has the same value (X) and is active is encountered -- duplicate is found, no insertion

  Example:

  Assume the type of X is int, M is 10, and the hash function returns X % M.

  

• Find -- First go to the slot specified by the hash function. Then, do linear search until 
  • the element to search which is marked active is found (success)
  • a null slot is encountered (fail)

• Delete/Remove
  • Can NOT mark the slot for X empty -- messes up the find operation
  • Do lazy deletion by marking the item deleted. 

    

  • With this scheme, no item is physically removed until array is rehashed.

  • NOTE: Any non-null slot that is marked deleted can NOT be re-used by insertion (except for the case when the same item is re-inserted) -- WHY??
    

• Linear probing suffers from Primary Clustering Problem:

  Primary Clustering problem Large clusters of occupied (active or deleted) cells may form during linear probing. [Cormen (491 textbook)] "Long runs of occupied slots build up, increasing the average search time."

   
• Rehashing
  • Usually to extend the size of the table, to the next prime from 2 * current_table_size.
  • Performed when the load factor becomes more than a fixed value (e.g. 0.8).
  • Usually applied as the LAST STEP IN INSERTION, to keep the table under the specified load factor.
  • Distribute existing active elements to the new table by applying % by the new table size, from table[0] to table[M-1].

    e.g. Initial table M = 5, maximum load factor = 0.75

    
    

• Average Expected number of probes:

  Let λ be the load factor.

  Successful Search:
  Unsuccessful Search:
  Insert:	, same as unsuccessful search

   

  Some examples:

• So, the average-case complexity for insert and (both) find are O(1), irrespective of n.
• How about the worst-case complexity??
  • insert
  • unsuccessful find
  • successful find

4. Quadratic Probing (or "Open Addressing with quadratic probing")

• Another collision resolution method which distributes items more evenly.
• From the original index H, if the slot is filled, try cells H+1², H+2², H+3²,.., H + i² with wrap-around.

  

• Considerations:
  1. Will different cells be tried at each probe?
     • If M is prime, quadratic probing guarantees that the first M/2 probes visit different cells .
  2. Does insertion always succeed when there are empty slots?
     • From 1, if an empty slot is found in the first M/2 probes, insertion succeeds. In other words, insertion (also find) will always succeed if the load factor is no more than 0.5. 
     • So, we need to rehash into a larger table when load factor becomes > 0.5.

• QP overcomes Primary Clustering problem, but still has Secondary Clustering problem:

  Secondary Clustering problem [Weiss, p. 166] -- a little confusing "In QP, elements that hashed to the same position probe the same alternative cells. .. Secondary clustering is a slight mathematical blemish." [Cormen (491 textbook)] -- better definition "If two keys have the same initial probe position, their probe sequences are the same; if h(key1, 0) = h(key2, 0) implies h(key1, i) = h(key2, i)." [My rephrasing]  Elements hashed to the same position end up having to probe longer and longer.

5. Separate Chaining

• More space-saving. Load factor can be more than 1.0.
• Architecture: a header table of size M, each element is a linked list (or pointer to a node).

  

• Insert -- Go to the position specified by the hash function for the item X. Traverse the list to see if X exists already. If not, insert a new node at the rear of the list.
• Find -- Go to the original position specified by the hash function. Then traverse the linked list.
• Delete -- usual linked list deletion

• Average Expected number of probes:

  Let λ be the load factor.

  Successful Search:
  Unsuccessful Search:	λ
  Insert:	λ , same as unsuccessful search

• IMPORTANT NOTES:

  1. Usually a separate chaining table does NOT rehash -- too expensive.
  2. Probing for a separate chaining table is to traverse a linked list (anchored from a slot in the header table), NOT the header table.

6. Hash tables vs. Linked List and Trees

• Hash tables support more efficient insert/find.
• But hash tables lose locality of data
  • no sorting, 
  • no find min/max