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.countReturns a Int with the number of elements in the hash table.
table.isEmptyReturns 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) -> IntReturns 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
