Implement a Dictionary in Swift
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:
- Some experience of using Dictionaries in Swift, and you might benefit from some knowledge of the Hashable protocol
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.
A clearly better implementation would be for each element (as near as possible) to have their own index. This requires a good hash function.
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:
