Implement a Dictionary in Swift

Image for post
Image for post

It is not just a HashMap…but how can we implement our own version of a Dictionary in Swift?

Dictionaries are a data type that are a function of hash table. Dictionaries provide fast access to the values it stores. The table stores entries as a key-value pair (with the value representing any object).

var myDictionary: [Int: Int] = [:]

can be added to through

myDictionary[4] = 17

and then the value retrieved through

myDictionary [4] // returns 17

Retrieving a value us often O(1), but can be as slow as O(log n). Insertion and deletion are typically O(1) but can be as slow as O(n (log n)).

Prerequisites:

Terminology

Hashable protocol: To make an object conform to Hashable you need to provide a hashValue that returns a unique number for each instance. Since the Hashable protocol inherits from Equatable you may also need to implement an == function.

Hash table: A hash table is a data structure that is used to store key-value pairs, using a hash function to compute the index into which an element will be inserted or stored. The average time for searching for an element in a hash table is O(1), as is insertion and deletion.

Hashing: A technique used to uniquely identify a specific object from a group of similar objects

Hash function: Any function that can be used to map a data set of an arbtrary size to a data set of a fixed size

Load factor of a hash table: The percentage of the capacity currently used. If there are 10 items in a table with 5 buckets, the load factor (10 / 5) = 2 (200%). Any load factor larger than 1 is a sign of a table that will not be performant.

The challenge

This implementation will include the following functions:

  • put(key, value) : Insert a (key, value) pair into the Dictionary. If the value already exists in the Dictionary, update the value.
  • get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
  • remove(key) : Remove the mapping for the value key if the Dictionary contains the key.

The Dictionary will only store Integer keys and values i.e. an implementation of:

var myDict : [Int:Int] = [:]

The Naive Array implementation

This implementation will use a simple array as the backing.

By using reservecapacity (which is an O(n) call) pre-allocating the space needed for the array makes sense and is performant.

The Theory of Hash Tables

Hash tables are an array. When an array is entered into a hash table, the key is used to calculate the array index of that element, via a hash function.

The choice of hash function is extremely important.

A hash table where all the elements are stored at the same index would function like a linked list — it would take O(n) to access a specific element.

Image for post
Image for post
A poor implementation of a hash table

A clearly better implementation would be for each element (as near as possible) to have their own index. This requires a good hash function.

Image for post
Image for post

Swift has its own inbuilt hashValue. These values are not guaranteed to be equal across executions of programs, but this does not matter for our implementation.

Notes:

  • hashValue can return a negative value, so we need to use abs to make sure it is positive
  • As above, each index can hold multiple elements
  • Each element will be a key-value pair

The issue with this implementation is obvious: As we add more elements in to the dictionary the performance suffers.

To resize the table you need to take into account the currentLoadFactor and resize accordingly; typically you will want double the number of empty slots in the implementation as compared to used slots

which is then called when items are added and removed into the hash map!

The full Playground is here:

Conclusions

Collisions are very important, and considering the load factor is essential to producing a worthwhile dictionary — if you chose to create one yourself!

If you want to learn more about Swift’s Dictionaries follow the link below:

Want to get in contact? Use Twitter:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store