Hash Table

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

  • Identify the steps of hashing (convert to hash code and compression).
  • Enumerate the properties of a good hash function.
  • Describe the job of Java's hashCode method.
  • Define what a hash table is.
  • Explain what collision (in the context of hashing) is and when it happens.
  • Describe Open Addressing with Linear Probing as a collision resolution.
  • Understand and apply the tombstone mechanism when removing an entry from a Hash Table with open addressing schemes.
  • Explain what is meant by contamination of open address hash tables.
  • Understand rehashing well enough to implement it.
  • Compute the load factor of a hash table.
  • Determine table size and when to rehash.
  • Analyze efficiency of open address hash tables.
  • Describe primary (and secondary) clustering effect of linear probing.
  • Describe other probing strategies (quadratic, double hashing, ...) for open address hash table.
  • Differentiate chaining collision resolution from open addressing.
  • Analyze efficiency of separate chaining hash table.