Swift Algorithm Club: Hash Tables
Learn how to implement a hash table data structure in Swift, in this step-by-step tutorial from the Swift Algorithm Club. By Kelvin Lau.
Sign up/Sign in
With a free Kodeco account you can download source code, track your progress, bookmark, personalise your learner profile and more!
Create accountAlready a member of Kodeco? Sign in
Sign up/Sign in
With a free Kodeco account you can download source code, track your progress, bookmark, personalise your learner profile and more!
Create accountAlready a member of Kodeco? Sign in
Contents
Swift Algorithm Club: Hash Tables
20 mins
Implementation
In the Sources directory, create a new Swift file and name it HashTable.swift
. Delete any text in the file and write the following:
public struct HashTable<Key: Hashable, Value> {
private typealias Element = (key: Key, value: Value)
private typealias Bucket = [Element]
private var buckets: [Bucket]
private(set) public var count = 0
public var isEmpty: Bool {
return count == 0
}
public init(capacity: Int) {
assert(capacity > 0)
buckets = Array<Bucket>(repeating: [], count: capacity)
}
}
Although you created a hash function based on the djb2 hash algorithm, it's better to leverage Apple's version. Through the constraining the Key
as Hashable
, your dictionary enforces that all keys have a hash value, so your dictionary doesn't need to worry about calculating the actual hash.
The main array is named buckets
It has a fixed size provided by the init(capacity)
method. You also keep track of how many items have been added to the hash table using the count
variable.
Operations
Now that the scaffolding for your hash table is complete, you'll want to define the mutating operations for this structure. There are four common things you will do with a hash table:
- insert a new elements
- look up an element
- update an existing element
- remove an element
You'll want the syntax to look like this:
hashTable["firstName"] = "Steve" // insert
let x = hashTable["firstName"] // lookup
hashTable["firstName"] = "Tim" // update
hashTable["firstName"] = nil // delete
Start by defining the following helper method in your HashTable
structure:
private func index(for key: Key) -> Int {
return abs(key.hashValue) % buckets.count
}
This method will help ensure the key maps to an index within the bounds of the storage array. Next, add the following just below index(for:)
:
Value Retrieval
Write the following inside the HashTable
structure:
// 1
public subscript(key: Key) -> Value? {
get {
return value(for: key)
}
}
// 2
public func value(for key: Key) -> Value? {
let index = self.index(for: key)
return buckets[index].first { $0.key == key }?.value
}
If a match is found, you use optional chaining to extract the value. Otherwise, first
will return nil
, signifying that the key doesn't map to a value in the hash table.
- The
subscript
method takes a key and returns a value. The actual logic will reside in thevalue(for:)
method. -
value(for:)
first callsindex(for:)
to convert the key into an array index. That returns the bucket number, but this bucket may be used by more than one key if there were collisions. Thus, you use thefirst
method that takes a closure, where you compare the key of each element with the key you want to match it with.
Inserting Values
The subscript
method can also work as a setter. Add the following code at the bottom of subscript
:
set {
if let value = newValue {
update(value: value, for: key)
}
}
This adds a setter to the subscript operation. newValue
is a invisible reference to the value that is being assigned to the subscript. Once again, you'll be defining actual logic in a helper method.
Add the following below value(for:)
:
@discardableResult
public mutating func update(value: Value, for key: Key) -> Value? {
let index = self.index(for: key)
// 1
if let (i, element) = buckets[index].enumerated().first(where: { $0.1.key == key }) {
let oldValue = element.value
buckets[index][i].value = value
return oldValue
}
// 2
buckets[index].append((key: key, value: value))
count += 1
return nil
}
Here's the play-by-play:
- You first check to see if the value is already inside a bucket. If it is, you update the value at the index
i
. - If execution comes to this point, it means the key doesn't map to a particular value inside the hash table. You then add the new key-value pair at the end of the bucket.
With that, you're finally able to try your hash table out. Navigate back to the playground page and write the following at the bottom of the playground:
var hashTable = HashTable<String, String>(capacity: 5)
hashTable["firstName"] = "Steve"
if let firstName = hashTable["firstName"] {
print(firstName)
}
if let lastName = hashTable["lastName"] {
print(lastName)
} else {
print("lastName key not in hash table")
}
You should see the following output in the console:
Steve lastName key not in hash table
Removing Items
The final operation you'll implement is the one that removes the key. Update the subscript
method to the following:
public subscript(key: Key) -> Value? {
get {
return value(for: key)
}
set {
if let value = newValue {
update(value: value, for: key)
} else {
removeValue(for: key)
}
}
}
Next, add the remove(value:for:)
method at the bottom of the HashTable
structure:
@discardableResult
public mutating func removeValue(for key: Key) -> Value? {
let index = self.index(for: key)
// 1
if let (i, element) = buckets[index].enumerated().first(where: { $0.1.key == key }) {
buckets[index].remove(at: i)
count -= 1
return element.value
}
// 2
return nil
}
This is fairly similar to the update
method. You first check to see if the value is in the bucket. If it is, you remove the key in the chain, decrement the count, and return the value. Otherwise, you return nil
, since you couldn't find the key-value pair to remove.
Navigate back to the playground page and write the following:
hashTable["firstName"] = nil
if let firstName = hashTable["firstName"] {
print(firstName)
} else {
print("firstName key is not in the hash table")
}
You should see the following in the console:
Steve lastName key not in hash table firstName key is not in the hash table
Resizing the Hash Table
This version of the hash table always uses an array of fixed size or capacity. If you have many items to store in the hash table, choose a prime number greater than the maximum number of items.
The load factor of a hash table is the percentage of the capacity that is currently used. If there are 3 items in a hash table with 5 buckets, then the load factor is 3/5 = 60%
.
If the hash table is small, and the chains are long, the load factor can become greater than 1, which is a sign of bad performance. One way to avoid this is to resize the hash table. Adding the code for this condition is left as an exercise for the reader. Keep in mind that making the buckets array larger will change the array indices that the keys map to! This requires you to insert all the elements again after resizing the array.