A hash table stores data so that it can be found almost instantly, without searching through every item. It uses a hash function to turn a key directly into a position in an array.

Hash functions

A hash function takes a key (a number or string) and returns an index. A simple example for numeric keys in a table of size 10 is the modulus method:

index = key MOD 10

Key 47 goes to index 7, key 123 to index 3. For text keys, you can add up the character codes and then take MOD of the table size.

A good hash function:

  • Is fast to calculate.
  • Spreads keys evenly over the table.
  • Always gives the same index for the same key.

Looking up a record then takes one calculation and one array access, so it is on average constant time, regardless of how much data is stored. This beats a linear search through an unsorted array.

Collisions

A collision happens when two different keys hash to the same index (for example 27 and 47 both give 7). Collisions are unavoidable when the table has fewer slots than possible keys, so they must be handled.

Open addressing (linear probing): if the slot is taken, try the next slot, wrapping around, until an empty one is found.

Table size 10, insert 27, 47, 17:
27 -> index 7
47 -> index 7 taken -> index 8
17 -> index 7, 8 taken -> index 9

When searching, follow the same probe sequence until you find the key or hit an empty slot. Deleting needs care, as simply emptying a slot can break the chain.

Chaining: each table slot holds a linked list of all keys that hash there. Collisions just add to the list.

Rehashing: use a second hash function to find another slot.

Load factor and uses

The load factor is the number of items divided by the table size. As the table fills up, collisions increase and performance drops, so tables are usually resized (and everything rehashed) once the load factor passes about 0.7.

Uses: database indexes, dictionaries or maps in programming languages, caches, symbol tables in compilers and password checking (stored hashes). Weaknesses: items are not stored in sorted order, so range queries and ordered output are inefficient.

Check your understanding

What does a hash function return?

  • A sorted list
  • An index in the table
  • A password
  • A pointer to the OS

Answer: An index in the table. It is calculated from the key.

What is a collision?

  • Two keys hashing to the same index
  • A full disk
  • A syntax error
  • An empty table

Answer: Two keys hashing to the same index. It must be resolved by probing or chaining.

In linear probing, what happens if the calculated slot is occupied?

  • The item is discarded
  • The next slot is tried until an empty one is found
  • The table is cleared
  • The key is changed

Answer: The next slot is tried until an empty one is found. Searching follows the same sequence.

What is the average lookup time in a well-designed hash table?

  • Constant
  • Linear
  • Quadratic
  • Exponential

Answer: Constant. One calculation and one array access find the item.

PreviousNext