A Hash Table is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends of the efficiency of the hash function used.

Let a hash function H(x) maps the value at the index x%10 in an Array. For example if the list of values is [11,12,13,14,15] it will be stored at positions {1,2,3,4,5} in the array or Hash table respectively.

### Characteristics

- An array, storing pointers to elements
- Maps key to table index with Hash Function
- Efficiency depends on Hash Function and table size
- Hash Function returns signed Int in Swift
- Table Index = abs(key.hashValue%table.count)
- Collisions
- Multiple keys mapping to same index
- Can handle collisions with Chaining

- Chaining
- At every table index, point to array or linked list
- After a collision, append element to array or linked list

- Table Size
- Choose sufficiently large table for the number of elements
- Choose next largest prime number to reduce chances of collisions

### Applications

- Password Verification
- Unordered_set & unordered_map in C++, HashSet & HashMap in java, dict in python etc.
- Compiler Operation
- Rabin-Karp Algorithm
- Linking filename and path together.

### Structure

`table.count`

Returns a Int with the number of elements in the hash table.

`table.isEmpty`

Returns a Bool. True if the hash table is empty. False if the hash table has elements.

`table.value(forKey key: Key) -> Value?`

Given a key to the hash table, returns an associated value.

`table.updateValue(_ value: Value, forKey key: Key) -> Value?`

Updates the value for the location of the given key. Returns a value.

`table.removeAll()`

Removes all the elements in the hash table.

`table.index(forKey key: Key) -> Int`

Returns an Int with the Index of the element associated with the given key.

## Hash Table with Chaining

## Hash Table with Only Keys

### References

- https://developer.apple.com/documentation/swift/dictionary
- https://www.raywenderlich.com/206-swift-algorithm-club-hash-tables
- https://en.wikipedia.org/wiki/Hash_function
- https://developer.apple.com/documentation/swift/hashable/1540917-hashvalue
- https://developer.apple.com/documentation/swift/hashable/2995575-hash