Skip to main content
Engineering LibreTexts

7: Hash Tables

  • Page ID
  • hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person's name), find the corresponding value (e.g. that person's telephone number). It works by transforming the key using a hash function into a hash, a number that the hash table uses to locate the desired value. This hash maps directly to a bucket in the array of key/value pairs, hence the name hash map. The mapping method lets us directly access the storage location for any key/value pair.

    Hash table<Element> Operations

    make-hash-table(integer n): HashTable

    Create a hash table with n buckets.

    get-value(HashTable h, Comparable key): Element

    Returns the value of the element for the given key. The key must be some comparable type.

    set-value(HashTable h, Comparable key, Element new-value)

    Sets the element of the array for the given key to be equal to new-value. The key must be some comparable type.

    remove(HashTable h, Comparable key)

    Remove the element for the given key from the hash table. The key must be some comparable type.
    Figure \(\PageIndex{1}\): A small phone book as a hash table.

    • Was this article helpful?