Learn

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.

// 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.

// 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.

Instructions

1.

Change the initializer method to create an array of empty arrays instead of an array of empty Strings. Additionally, change the type of values to an array of array of tuples. The tuple will contain two Strings.

2.

Change the array’s name from values to buckets. Reflect the name change in the rest of the code.

3.

Inside your value(for:) function:

1) Change elementIndex to bucketIndex

2) Create an if let statement setting the tuple variables (_, currentValue) equal to:

  • The enumeration of buckets at the desired index.
  • The first value in the enumeration where the element’s key matches the provided key
4.

If the value is found, return the currentValue’s value which is located at the first index. Otherwise, return the empty string.

Uncomment return value(for: key) inside of the subscript(key:) method.

5.

Inside your update(value:for:) function:

1) Change elementIndex to bucketIndex

2) Create an if let statement setting the tuple variables (bucketIndex, _) equal to:

  • The enumeration of buckets at the desired index.
  • The first value in the enumeration where the element’s key matches the provided key
6.

If the index is found, set the value at the outer bucketIndex and inner elementIndex equal to the (key, value) tuple pair. Otherwise, append the (key, value) tuple to buckets at the desired bucketIndex.

Uncomment update(value: value, for: key) inside of the subscript(key:) method.

7.

Inside your removeValue(for:) function:

1) Change elementIndex to bucketIndex

2) Create an if let statement setting the tuple variables (bucketIndex, _) equal to:

  • The enumeration of buckets at the desired index.
  • The first value in the enumeration where the element’s key matches the provided key
8.

If the index is found, remove the element located at elementIndex inside the array located in buckets at bucketIndex.

Uncomment removeValue(for: key) inside of the subscript(key:) method.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?