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

Hash Table?

This is a data structure which can search/delete element in almost O(1) time, Unlike arrays or linked lists that require searching through elements one by one and takes O(n) time
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 hash function 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    hash (key%3)=index in array
a        97 % 3 = 1
b        98 % 3 = 2
c        99 % 3 = 0
d       100 % 3 = 1

Hash Table (using Chaining/Separate Chaining)
+----+
|  0 | ---> (c,3) ---> NULL
+----+
|  1 | ---> (a,1) ---> (d,4) ---> NULL
+----+
|  2 | ---> (b,2) ---> NULL
+----+

struct Entry {
    char key;
    int value;
};
class HashTable {
    static const int CAP = 4;
    std::vector<Entry> buckets[CAP];
    int hashFunction (char &c) {
        // Very simple hash
        unsigned long random = 5;
        int h = random + (unsigned char)c;
        return (int)(h % CAP);      //index into bucket
    }
public:
    void insertIntoHashTable(char 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.
Solutions to Hash Collision

1. Open Addressing

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

2. Seperate Chaining (Discussed above)

Extra Overhead with hash table

Memory Overhead:
  1. Every bucket requires memory for a pointer. Since key-value is stored in Linked List, requires extra bytes to store a pointer to the "next" node in the chain.
  2. Rehashing Overhead. When Load Factor becomes greater than .75, then larger bucket is allocated, all keys are rehashed
Computation Overhead
  1. Every read, write, and delete requires running the hash function algorithm to calculate the index.

Load Factor

Load factor measures of how "full" the hash table is

Load factor = Total number of elements / number of slots in buckets

Above example:
 elements: (a,1), (b,2), (c,3), and (d,4)
 slots: 3
 LF = 4/3 = 1.33

if (Load Factor > 0.75), then rehashing is triggered.
(Load Factor > 1) means
- Elements > slots, that means there is atleast 1 collision
- Collision means Search is not O(1) now, its moving towards O(n)

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

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).
  Rehashing

Rehashing / Resizing

When Load Factor > 0.75, a rehash is triggered automatically.
During a rehash, a new, l arger 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. Table1(hash1), Table2(hash2). Eg: Cuckoo 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.