CS201: Elementary Data Structures

8.1: Hash Tables

• Massachusetts Institute of Technology: Erik Demaine's "Hashing with Chaining" Page

  This lecture introduces the concept of key/value pairs and how to search for them via hash functions. Chaining is used to handle collisions, which are when multiple values share the same key.
  

• Massachusetts Institute of Technology: Erik Demaine's "Table Doubling and Karp-Rabin" Page

  This lecture expands upon the previous one to introduce the possibilities of running out of space in the hash table or of having chains that are too long. In those cases, we would want to increase the size of the hash table; this lecture discusses how to do that effectively.
  

• Massachusetts Institute of Technology: Srini Devadas' "Open Addressing and Cryptographic Hashing" Page

  Watch this lecture, which foregoes chaining as a means of handling collisions and uses table-probing instead.
  

• Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Hashing" File

  Read this section on hashing, which presents a different perspective than the lectures above. This section uses C/C++ syntax.