Understanding Hash Tables, Dictionaries & Sets with Swift

When helping iOS developers prepare for technical interviews, I often discuss Hash Tables. Due to their efficiency, Hash tables are a great tool candidates should consider when tackling coding challenges as well as real-world applications. In this essay, we’ll explore the concept of a Hash table and will compare it to other collection types such as Dictionaries and Sets.

The Dictionary

To understand why Hash tables are useful, one should be familiar with their design. When asked, many students assume that a “hash table is a dictionary.” To test this idea, let’s review the standard Swift Dictionary type:

var list = Dictionary<String, String>()
//add dictionary values - constant time O(1)
list["WB"] = "Wayne Bishop"
list["FB"] = "Frank Hobbs"
list["LP"] = "Larry Page"
list["AE"] = "Albert Einstein"
//retrieve keys
for s in list.keys {
    print(s)
}
//retrieve values
for v in list.values {
    print(v)
}
//retrieve value with key - constant time O(1)
let item = list["WB"] //retrieves "Wayne Bishop"

Dictionaries are useful types that handle many scenarios. Since both keys and values get supplied at runtime, one can write routines to retrieve individual keys, values or a mixture thereof. Also, since each supplied value is associated with a key, one can also perform necessary data insertion, lookup and retrieval in O(1) — constant time.

The Hash Table

Hash tables are a close relative to Dictionaries but differ in two areas. Hash tables also support key-value pairs, but their keys are generated programmatically through the use of an additional function called a hash algorithm. Since Hash table keys get created at runtime (and are not subject to change), they are often not stored with the data structure. These features allow Hash tables to execute in O(1) — constant time while occupying minimal space. Consider the following custom implementation taken from the book:

let list = HashTable<String>(capacity: 4)
//add hash table items - constant time O(1)
 = list.insert("Wayne Bishop")
 = list.insert("Frank Smith")
 = list.insert("Jennifer Hobbs")
 = list.insert("Tim Cook")
//evaluation test - constant time O(1)
if list.contains("Tim Cook") {
   print("user found!")
}

If you’ve had the opportunity to program in other languages (e.g. Java) you’ll be familiar with the HashTable or HashMap types. In iOS development, there is no official corresponding HashTable type. However, in its place, we have the popular Hashable protocol. The idea is that one can extend any type to support Hash table-like functionality. Consider the following component used to create a blockchain algorithm:

//custom type (used with graph programming)
public class Vertex {
    
    var key: String?
    var neighbors: Array<Edge>
    var visited: Bool = false
    
    init() {
     self.neighbors = Array<Edge>()
    }
}

...

//type conformance for Hashable
extension Vertex: Hashable {
    
    public var hashValue: Int {
        
        var remainder: Int = 0
        var divisor: Int = 0
        
        //test early exit
        guard let scalars = self.key?.unicodeScalars else {
            return 0
        }
   
   for item in scalars {
            divisor += Int(item.value)
        }
        
        remainder = divisor % 10
                       
        return remainder        
    }
    
    //note: requirement for inherited Equatable protocol     
    public static func == (lhs: Vertex, rhs: Vertex) -> Bool {
       return lhs.key == rhs.key
    }    
    
}

As a protocol, Hashable ensures all conforming types get correctly indexed with a unique numerical value. Under this model, the required hashValue computed property acts as the hash algorithm. We can also see this functionality in action when working with standard Swift collection types such as Sets:

var items = Set<String>() //note: Swift Strings conform to Hashable

//add set items - constant time O(1)
items.insert("Wayne Bishop") 
items.insert("Frank Hobbs")
items.insert("Larry Page")
items.insert("Albert Einstien")

//obtain hash index for first set item
if let itemvalue = items.first?.hashValue {
   print(itemvalue)  //prints -312247953819291399
}

Since the native Swift String type already conforms to Hashable, it supports built-in compliance for the hashValue computed property. Lastly, iOS developers looking for more flexibility can sidestep the Hashable model altogether to create a unique implementation. Knowing how to write a simple hash algorithm becomes particularly useful in a technical interview. Consider the following design also taken from the book. This approach applies a protocol-oriented technique through the use of a protocol extension:

protocol Keyable {       
       
       var keystring: String {get}
       
       //note: in this case hashValue operates as a function
       func hashValue(for key: String!, using buckets: Array<T>) -> Int 
 }
    
extension Keyable {
        
        //compute item hash
        func hashValue<T>(for key: String!, using buckets: Array<T>) -> Int {
                    
            var remainder: Int = 0
            var divisor: Int = 0
            
            //trivial case
            guard key != nil else {
                return -1
            }        
            
            for item in key.unicodeScalars {
            divisor += Int(item.value)
            }        
            
            remainder = divisor % buckets.count        
            return remainder
         }        
  }

Liked this essay? Read and discover my Swift Algorithms Book on Medium.