Running time for dictionary operations

In order to be able to examine how dictionaries work, you need to understand what hashing is and how it works. Hashing is the process of transforming a value — String, Int, Double, Bool, etc — to a numeric value, known as the hash value. This value can then be used to quickly lookup the values in a hash table.

Swift dictionaries have a type requirement for keys. Keys must be Hashable or you will get a compiler error.

Fortunately, in Swift, all basic types are already hashable and have a hashValue

integer property. Here’s an example:

print("some string".hashValue)

// > -497521651836391849

print(1.hashValue)

// > 1 print(false.hashValue)

// > 0

The hash value has to be deterministic — meaning that a given value must always return the same hash value. No matter how many times you calculate the hash value for some string, it will always give the same value. (You should never save a hash value, however, as there is no guarantee it will be the same from run-to-run of your program.)

Here’s the performance of various dictionary operations. This great performance hinges on having a good hashing function that avoids value collisions. If you have a poor hashing function, all of below algorithms degenerate to linear time, or O(n) performance. Fortunately, the built-in types have great, general purpose hashValue implementations.

Accessing elements: Getting the value of a given key is a constant time operation, or O(1).

Inserting elements: To insert an element, the dictionary needs to calculate the

hash value of the key and then store data based on that hash. These are all O(1) operations.

Deleting elements: Again, the dictionary needs to calculate the hash value to know exactly where to find the element, and then remove it. This is also an O(1) operation.

Searching for an element: As mentioned above, accessing an element has constant running time, so the complexity for searching is also O(1).

While all of these running times compare favorably to arrays, remember that you lose order information when using dictionaries.