7.3. Hash Tables

7.3. Hash Tables
	Chapter 7. Hash Tables

Hash tables are one of the most used data structures when developing applications (the reader is advised to type this term in any search engine and see the number of found links). There are multiples libraries in almost any programming language providing efficient implementations of these tables (i.e. the java.util.Hashtable class which is part of the Java libraries).

A hash table implementation is based on the following elements:

A reasonably sized table to store the (key, value) pairs.
A “hash” function that receives a key and returns an index to access a table position.
A procedure to treat the cases in which the previous function returns the same index for two different keys. This situation is known with the term collision.

The implementation of each of these three elements offers a huge number of possibilities, turning into as many possible implementations of a hash table. It follows a detailed description of one possible solution for handling the collisions.

Answer the following questions to see if you understood what the content of this document:

A hash function is
- A function that, given a key, returns the table index of the hash table where the element is stored (or where you must store it).
- A function that, given a key, returns the element stored in the hash table.
- A function that, given an element, returns its key in the hash table.
In a hash table, a collision happens when:
- With a well-designed hash function, there will not be collisions.
- There is no enough space in the hash table for all the elements. In this case, the table must be redimensioned.
- The hash function retrieves the same index for two different keys.

UC3M

Telematic/Audiovisual Syst./Communication Syst. Engineering

Systems Architecture

September 2017 - January 2018

7.3. Hash Tables


7.2. Possible Implementations		7.4. Handling Collisions with Linked Lists