Separate Chaining

• Separate Chaining

  keep a list of all elements that hash to the same value.
• To perform a search, we use the hash function to determine which list to traverse
• To perform an insert, we check the appropriate list to see whether the element is already in place. If the element turns out to be new, it is inserted at the front of the list, since it is convenient and also because frequently it happens that recently inserted elements are the most likely to be accessed in the near future.
• Hash tables work only for objects that provide an appropriate equals method and a hashCode method that returns an int.
• In the insertion routine, if the item to be inserted is already present, then we do nothing; otherwise, we place it in the list. The element can be placed anywhere in the list; using add is most convenient in our case.
• Hash function


  A function that converts a key into an array index
• Hash function implementation

  1. Calculate hashVal by iterating through key string and multiplying by 37

  2. Reduce hashVal to be within table size

  3. If hashVal is negative, add table size
• Separate chaining hash table

  • Keeps a list of all elements that hash to the same value
  • Uses standard library list implementations
• Searching in separate chaining hash table

  1. Use hash function to determine which list to traverse

  2. Search the appropriate list
• Inserting in separate chaining hash table

  1. Check the appropriate list to see if element is already present

  2. If new, insert at front of list
• Load factor (λ)


  Ratio of number of elements in hash table to table size
• Average length of list in separate chaining hash table is the load factor (λ)
• Unsuccessful search in separate chaining hash table examines λ nodes on average
• Successful search in separate chaining hash table examines about 1 + (λ/2) links
• The hash table implementation only works for objects that provide appropriate equals and hashCode methods