Learn how to create a hash table in Swift.

Hash Tables: Swift

We have a hash table implementation, but what happens when two different keys generate the same index? Run the code in *HashTable.swift* to see a collision in action. 

Instead of returning `"Marsh Plant"` and `"Wild Animal"`, we retrieve `"Wild Animal"` twice. This is because both key-value pairs are assigned to the same index 0 and the first value, `"Marsh Plant"` was overwritten.

When two different keys resolve to the same array index, this is called a collision. In our current implementation, all keys that resolve to the same index are treated as if they are the same key. This is a problem because they will overwrite one another's values.


Collisions

The current hashing function will return a very large integer, approximately 19 digits long. The hash value is not within the bounds of the hash table array, which was defined at `5` in the last exercise. This is a problem because you cannot store a value at index 1,234,567,890,123 if there are only 5 indices. To fix this, we need to use compression.

Compression means taking some input and returning an output that is within a specific range.

In our hash table implementation, we're going to have our `index(for:)` function handle hash value calculation as well as compression.

To do this, we'll use modular arithmetic. Because modular arithmetic prevents a value from growing larger than some limit, it's a common solution when we want a value to "wrap around". 

The modulo operator, `%`, returns the remainder when dividing two numbers, discarding the result of the division. This means that the returning value can never be bigger than the divisor. 

 Take the following division problem for example:

```pseudo
11 % 2 = 1
```
 
The remainder of any number modulus `2` will never be greater than `1`. This is because any value divided by `2` will either have a remainder of `0` or `1`. We'll apply the same modular arithmetic to our array size so the hash value never surpasses the size of our array. 

Compression

Let's implement a collision strategy to avoid overwriting data on collisions in our hash table. 

Our first step in implementing a collision strategy is modifying the initializer method to store arrays inside the hash table array instead of just Strings. This will allow us to store multiple values at the same index by adding new values within the inner array instead of overwriting a single value. This strategy of handling collisions is called _separate chaining_.

```pseudo
// Hash Table without Separate Chaining
array = [1, 2, 3, 4, 5, 6] // capacity of 6
array.add(7) // 7 % 6 = 1
array = [7, 2, 3, 4, 5, 6]

// Hash Table with Separate Chaining
array = [[1], [2], [3], [4], [5], [6]] // capacity of 6
array.add(7) // 7 % 6 = 1
array = [[1, 7], [2], [3], [4], [5], [6]]
```

Our second step consists of modifying the `HashTable` array type to reflect the changes in the previous paragraph. Instead of storing an array of Strings, we will need to store an array that contains arrays that contain a tuple with two elements: one String for the key and one String for the value. You'll need to store the key so you can find the exact value as you iterate through the inner array when you have a collision. This method allows us to have multiple elements at each index instead of overwriting a single value.

```pseudo
// Example hash table with key-value pairs
array = [[("Key", "Value")], [], [], [("Batman", "The Dark Knight")]]
```

Our third, fourth, and fifth steps consist of modifying the `value(for:)`, `update(value:for:)`, and `removeValue(for:)` methods to delete the correct index instead of deleting the entire index. 

If we are trying to add an a value and that index already contains an element, we need to add that element to the end of the array at that index. 

If we are trying to retrieve a value, we need to iterate through the inner array, find the specified value and retrieve it.

If we are trying to delete an element, we need to iterate through the inner array, find the value, and delete the specific element.


Collisions: Assign, Retrieve, Delete

We now have everything we need to store a value in the hash table array. The only thing left is to assign the value at the index we calculated with the `index(for:)` function.
 
Storing and printing a value in a hash table should look something similar to:

```swift
someHashTable["Orange"] = "Fruit"
print(someHashTable["Orange"]) // Prints: Fruit
```

To assign a value to an array using the above subscript format, we will first create an `update(value:for:)` method that will handle the logic needed to take a key-value pair from the `subscript()` function and store the value at a particular index. 

Secondly, we will [overload the `subscript()` function](https://docs.swift.org/swift-book/LanguageGuide/Subscripts.html) to assign a key-value pair.

Assign

Now that we can assign elements to the hash table, we have to be able to retrieve the values we are storing. Retrieving an element should look something like:

```swift
// Assignment
someHashTable["Name"] = "John"
// Retrieval
print(someHashTable["Name"]) // Prints: John
```

To retrieve a value from a hash table, we'll create a private method `value(for:)` to return a value from the array. It will first calculate the index of the key-value pair you desire using the `index(for:)` function and return the value at the calculated index. 

Next, let's call and return `value(for:)` inside of `subscript(key:)`'s getter function. This will return the value at the desired index when retrieving it similar to the example above. 


Retrieve

The last operation we need our `HashTable` to allow is deleting elements. Deleting an element would look something like:

```swift
someeHashTable["Orange"] = "Orange"
print(someHashTable["Orange"] // Prints: Orange
someHashTable["Orange"] = nil
print(someHashTable["Orange"] // Prints: ""
```

To delete a value from the array, we will first create a `removeValue(for:)` method to delete the value from the array. In the example above, notice that the value is the empty String, not `nil`. Since the array needs to stay the same size, deleting an element actually means setting the value to the empty String instead of removing the element from the array.

Secondly, we will modify the `subscript(key:)` function's setter to remove the value if the value provided is equal to `nil`. That is, if no value is actually provided, we will call the `removeValue(for:)` function on the provided key.


Delete

Now that we have all of the functionality of a hash table, it's time to review what we've learned. Use what you know about hash tables to record animal sounds.

Review

The hashing function is the secret to efficiently storing and retrieving values in a hash table. A hashing function takes a value, passes it through a formula, and produces a result called a _hash_. 

This function is said to be deterministic. That means the hashing function must always return the same value when given the same key. This is important because we will need to hash the key again later to retrieve the stored value. We won't be able to do this unless our hashing function behaves in a predictable and consistent way. 

Fortunately, Swift provides a `hashValue` computed property for types that conform to `Hashable`. Many types in the standard library [conform to `Hashable`](https://developer.apple.com/documentation/swift/hashable), to include Strings, Integers, and Boolean values. 


Hashing

Hash tables are data structures that serve as efficient key-value stores. They are capable of assigning and retrieving data in the fastest way possible. This is because the underlying data structure that hash tables use is an array.

A value is stored at an array index determined by plugging the key into a hash function. Because we always know exactly where to find values in a hash table, we have constant-time access to any of the values it contains.

This quick access to values makes hash tables a good choice of data structure whenever we need to store a lot of values but need fast look-up time.

In this lesson, you will create your own implementation of a hash table by building out a `HashTable` structure. You'll build methods to hash and access key-value pairs, assign an index at which to store a value and retrieve stored values.

To implement a hash table, the `HashTable` initializer will create an empty array to hold values. You'll determine where to store values in the hash table by using a hash value. While going through the following exercises, remember that the purpose of this lesson is to gain a deeper understanding of the data structure rather than creating a production-quality data structure.