Skip to main content
Engineering LibreTexts

7: Hash Tables

  • Page ID
    47915
  • 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.
    362px-HASHTB08.svg.png
    Figure \(\PageIndex{1}\): A small phone book as a hash table.

    • Was this article helpful?