Hash Table Theory

Hash table is a data structure that can be used to detect if an element appears in a collection. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

If the number of keys greaters than the size of hash table, what we need to handle is hash collision.

  1. Open Addressing (Linear Probing)
    If a hash collision occurs, the table will be probed to move the record to an alternate cell that is stated as empty.
  2. Separate chaining
    If two records are being directed to the same cell, both would go into that cell as a linked list.

Application

There are three types of hash structures:

  1. Array: used when the number of keys is limited to a small number (like char).
  2. Set: used when we need to check if an element appears in a collection in O(1) time complexity.
  3. Map: used when we need to search how many times an element appears in a collection in O(1) time complexity.

Practice
Leetcode 242 - Valid Anagram
Leetcode 349 - Intersection of Two Arrays
Leetcode 202 - Happy Number
Leetcode 1 - Two Sum
Leetcode 454 - 4Sum II
Leetcode 383 - Ransom Note

Note

  • Unexpected behavior when using .size():

    1
    2
    3
    for (int i = 0; i < arr.size() - 3; i++)  {
        ...
    }

  • A value overflow can occur in this case because .size() returns an unsigned int. If arr‘s length is smaller than 3, arr.size() - 3 will be a very large value.

  • Always check if the data type fits the range of a value.

  • Accessing a key in a std::map (or std::unordered_map) that does not exist will insert the key with a default value.