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

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

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

Leave a Reply

Come See Me

San Francisco, CA
hello@ingax.com

See My Work