Data Structures - Dictionaries

by Zoja Savkovic

Dictionaries, as with so many things on this blog, are most easily understood via a series of definitions! Though in simple colloquial terms, you would think that a dictionary is like an index, at the back of a book, that tells you what page to go to, for a certain topic. They are. But a lot of things need to be defined and understood, which this post aims to do. Examples of things to understand include a hash function, hash table ("invented in 1953") and associative array.

Also, as mentioned in the post on data structures - a dictionary (also known as associative array) is an abstract data type (from the point of view of the user), not a data structure (from the point of view of the implementation).

In that previous post we already defined the associative array which is a dictionary, in short, from Wikipedia:

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

Let's define some other things used in the implementation of a dictionary.

Hash Function

A hash function is any function that can be used to map data of arbitrary size to fixed-size values. Note that:

  • An example is the modulo operation eg f(x) = x mod m
  • The values returned by a hash function are called hash values, hash codes, digests, or simply hashes.
  • The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.
  • Use of hash functions relies on statistical properties of key and function interaction: worst-case behaviour is intolerably bad with a vanishingly small probability, and average-case behaviour can be nearly optimal (minimal collision).
  • Use of hash functions relies on statistical properties of key and function interaction: worst-case behaviour is intolerably bad with a vanishingly small probability, and average-case behaviour can be nearly optimal (minimal collision).

Hash Table

This is the key of this blog post - one example of a dictionary implementation.

According to Wikipedia, the hash table was "invented in 1953", and

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.

Search Tree

A search tree is simply another implementation of an associative array, which we will leave for now as a separate post will focus on trees.

And that's all there is to it - implementations of data structures for the abstract daat type that is the dictionary.