---

Separate Chaining: Handling collision in hashing

---

• Separate chaining
  • Separate chaining:

    Separate chaining is the easiest way to resolve collision in Hashing Each bucket contains a linked list of entries Since a linked list can be arbitrarily long, one bucket can contain a arbitrary large number of entries

  • Example:

    Map content: { (11,D), (13,C), (23,F), (63,Z), (16,A), (56,C), (7,Q) } Bucket array: 10 buckets (N = 10) Hash function: h(k) = k%10 Storage of the Map content in the hash table: Separate chaining:

    ---

  • Psuedo codes:

    put(k,v):

    Value put(Key k, Value v) { int idx; idx = h(k); // Hash the key... if ( A[idx] == null ) { /* Empty list */ insert (k,v) into list at A[idx]; N++; // One more entry... return(null); } else { /* Non-empty list */ Find key k in list at A[idx]; // Traverse the list at A[idx] ! if ( not found ) { insert a new entry (k, v); N++; // One more entry... return(null); } else { REPLACE the value in entry with input v; return(old v); } } }

    ---

    get(k):

    Value get(Key k) { int idx; idx = h(k); // Hash the key... if ( A[idx] == null ) { /* Empty list */ return(null); // Not found } else { /* Non-empty list */ Find key k in list at A[idx]; // Traverse the list at A[idx] ! if ( not found ) { return(null); // Not found } else { return(v in entry found); } } }

    ---

    remove(k):

    Value remove(Key k) { int idx; idx = h(k); // Hash the key... if ( A[idx] == null ) { /* Empty list */ return(null); // Not found... } else { /* Non-empty list */ Find key k in list at A[idx]; // Traverse the list at A[idx] !!! if ( not found ) { return(null); // Not found.... } else { Remove entry found; N--; // One less entry return(old v); } } }