Hash

Definition: a hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Support O(1) time insert, delete and findElement.
Does not support sort, findMin or findMax.

Deal with hash collision:

1. Separate Chaining: 将hash到同一个值的所有元素保存到一个链表里。

   
   separate chaining where hash(x) = x mod 10
2. Open addressing: 当collision发生时就尝试选择另一个单元，直到找到空的单元 (Probe)。对单元, h_1(x),h_2(x)...)进行probe，其中 = (hash(x)+f(i)) \mod TableSize) f(i)是冲突解决函数。

• Linear probing: f(i) is a linear function
• Quadratic probing: f(i) is a quadratic function
• Double hashing: f(i) = newHash(x)

Hash in C++:
use unordered_map, support insert, access, find, erase in O(1).

//unordered_map<key_type, value_type>
//example
#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int main()
{
    // Create an empty unordered_map
    unordered_map<string, int> wordMap;
    
    // Insert Few elements in map
    wordMap["First"] = 1;
    wordMap["]Second"] = 2;
    
    //Another way to insert
    wordMap.insert( { "Third", 3 });
    
    // Overwrite value of an element
    wordMap["Third"] = 8;
    
    //define iterator
    unordered_map<std::string, int>::iterator it;
    
    // Iterate Over the unordered_map and display elements
    for(it = wordMap.begin();it != wordMap.end(); it++)
    {
        cout << it->first << " : " << it->second << endl;
    }
    
    //Find value in map
    it = wordMap.find("First");
    if (it != wordMap.end()) cout << "Find First" << endl;
    else cout << "Not exists" << endl;

    //Erase value in map
    wordMap.erase(it);
    
    return 0;
}
/* Output
Third : 8
Second : 2
First : 1
Find First
*/