Direct Access Table

Take huge array and use phone numbers as index in the array. if phone number is not present entry is empty, else the array entry stores pointer to records corresponding to phone number.
Searching in DA: O(1) but HUGE Extra Space required.
Hash Table is improvement over DAT

What is Hash Table

Search Complexity: Average=O(1), Worst case=O(n)
Disadvantages:
  1. Elements are not sorted
  2. Rehashing: Once all HT entries are filled it needs resized/rehashing which is a time-consuming operation. Let HT size = 100, we want to insert 101st element. Not only the size of hash table is enlarged to 150, all element in hash table have to be rehashed. This insertion operation takes O(n).
Hash Function? Hash function maps a big number or string to a small integer that can be used as index in hash table.

key -> |Hash Function| -> index of array/table

Internal Implementation of Hash Table

Let use consider simple example to insert following key,value pairs: {"a",1}, {"b",2}, {"b",3}
Keys("a", "b", "b") are passed to hashfunction and indexes are returned in bucket which acts as hash table
Collision: if same index is returned, chaining is done, ie element is inserted into next position in vector

key value
a   1
b   2
c   3

i   value           hash               index
0   a=97        randomval + 97 = 97   97 % 4 = 1
1   b=98        randomval + 98 = 98   98 % 4 = 2
2   c=99        randomval + 99 = 99   99 % 4 = 3

Hash Table
|   | a |   b   | c |
  0   1     2     3  

struct Entry {
    std::string key;
    int value;
};
class HashTable {
    static const int CAP = 4;
    std::vector<Entry> buckets[CAP];
    int hashFunction (const std::string &s) {
        // Very simple hash
        unsigned long h = 0;
        for (char c : s) {
            h = h * 31 + (unsigned char)c;
        }
        return (int)(h % CAP);      //index into bucket
    }
public:
    void insertIntoHashTable(const std::string &key, int value) {
        int idx = hashFunction (key);
        auto &bucket = buckets[idx];

        // update if key exists
        for (auto &e : bucket) {
            if (e.key == key) {
                e.value = value;
                return;
            }
        }
        // otherwise insert
        bucket.push_back(Entry{key, value});
    }
};
            

Hash Collision

This means hash function provides same index for 2 different keys.

1. Open Addressing

hash(a) = 1
            | a |  |
              1
hash(b) = 1. Insert after open place in array
            | a | b |
              1

2. Seperate Chaining

Each index of the hash table points to a secondary data structure, typically a linked list. When a collision occurs, the new key is simply appended to the list at that index
Insert(x): O(1). Insert at head of LL, Search(x): O(n). Need to search complete list

hash(a) = 1, hash(b) = 1, hash(c) = 1
hash(d) = 1, hash(e) = 1

Hash Table (Array of Buckets)
+---------+
| Index 0 | ---> NULL
+---------+
| Index 1 | ---> [ "a" ] ---> [ "b" ] ---> [ "c" ] ---> NULL
+---------+
| Index 2 | ---> NULL
+---------+
| Index 3 | ---> [ "d" ] ---> [ "e" ] ---> NULL
+---------+
| Index 4 | ---> NULL
+---------+

C++ hashmap(unordered_map / unordered_set) = Seperate Chaining

A hash table container like std::unordered_map or std::unordered_set is implemented using separate chaining for collision resolution.
Allocations: Similar to vector
  A default-constructed hash table (:unordered_map <int, string> map;) starts with a bucket count of 0.
  1st map.insert(), it allocates its initial bucket array (size=1).
  Check Rehashing

Rehashing

load factor = number of elements / number of buckets
default max_load_factor() = 1.0

When an insertion causes the load factor to exceed 1.0 (i.e., elements >= buckets), a rehash is triggered automatically.
During a rehash, a new, larger bucket array is allocated (typically scaling to the next prime number), and all existing elements are re-hashed and redistributed into the new buckets.
Let us consider unordered_map<int,string> storing unique keys. At start of program sizeof hash table=3

Key | Value
  ----------
  01  | amit
  02  | never
  03  | give
        

Now, (4, up) need to be stored, but hash table has no space so size of hash table is increased to 6. (old Hash function = %3) we can only goto index number=2.
But we want to reach 5. Hence Hash function is changed (new Hash function = %6). So hash is again calculated for existing values.

Implementations

2-left hashing

2 equal sized hash tables having 2 seperate hash functions are used. Seperate chanining is used in both. Table1(hash1), Table2(hash2).
Cuckoo Hashing is a type of 2-left hashing
Inserting key into table: Always keep Table1 loaded, key is inserted into Table2 only when too many collisions happen on Table1.
Advantages? 1. On parallel systems. 2 cores can query 2 hash tables, ie Thread-1 can query Table1 and Thread2 Table2.

d-left Hashing

Split 1 hash table into d blocks. Similar to 2-left hashing, left most hashtable should be loaded.
d buckets, n entries. Each bucket has n/d entries

Code

1. Student Hash table

Hash table stores Student data (Key:Value)
(1,20)  (2,70)  (42,80)  (4,25)  (12,44)  (13,78)  (14,32) (17,11)  (37,97)
        

2. Leetcode Solved. Design a HashMap without using any built-in hash table libraries.