Youtube上看到一个小哥讲的Hash Table，讲清它的原理和结构之后又带着从零开始实现了构造哈希函数、创建哈希表、增加/删除数据等一系列系统的操作，讲解和示例清晰完整，丝毫不拖泥带水，大赞。

链接

Introduction to Hash Tables

需要科学上网，有强烈欲望想要看的同学可以参考之前这篇ubuntu下服务器搭建的博客，自己配置外网服务器

哈希表

哈希表(Hash Table)，是一种数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中的一个位置来访问，这加快了查找的速度。STL中的map就是哈希表的一种实现。
键值可以是字符串或者其它较为复杂的类型，下面以字符串为例。若将它们直接存储在数组里，当想要访问它们的时候只能O(n)复杂度的遍历一遍。但是通过构造哈希函数，我们可以首先将这个字符串映射为一个整数类型，将这个整数作为它们所在数组位置的下标，这样当我们想要访问某一个字符串，只需要把它送到哈希函数里得到一个返回的哈希值，也就是它所在数组位置的下标，就能以O(1)的复杂度访问它。
哈希函数的构造方法有很多，但一般我们得不到一个完美的哈希函数，即可能会存在两个字符串它们对应的哈希值相同。为了应对这种冲突，我们可以把数组的每个位置当做链表，存在多值时就链接到链表后面。如上图所示。

代码

边听着小哥的讲解边写的代码，包括了构造哈希函数、创建哈希表、增加/删除数据等操作。

#include <bits/stdc++.h>

using namespace std;

const int tablesize = 40;
string s;
struct item{
    item(){
        name = "empty";
        drink = "empty";
        next = NULL;
    }
    string name;
    string drink;
    item* next;
};
item* hashTable[tablesize];

void Init();
int Hash(string s);
void AddItem(string name, string drink);
int NumberOfItemsIndex(int idx);
void PrintTable();
void PrintItemInIndex(int idx);
void FindDrink(string name);
void RemoveItem(string name);

void RemoveItem(string name){
    int idx = Hash(name);
    item* ptr = hashTable[idx];

    //Case 0 - bucket is empty
    if(ptr->name == "empty"){
        cout << name << " was not found in the hashTable" << endl;
    }

    //Case 1 - only 1 item contained in bucket and that item has matching name
    else if(ptr->name == name && ptr->next == NULL){
        ptr->name = "empty";
        ptr->drink = "empty";
        cout << name << "was removed from the Hash Table." << endl;
    }

    //Case 2 - match is located in the first item int the bucket but there are 
    //more items in the bucket
    else if(ptr->name == name && ptr->next != NULL){
        hashTable[idx] = ptr->next;
        delete ptr;
        cout << name << " was removed from the Hash Table." << endl;
    }

    //Case3 - bucket contains item but first item is not a match
    else{
        item* p1;
        item* p2;
        p1 = ptr->next;
        p2 = ptr;
        while(p1 != NULL && p1->name != name){
            p1 = p1->next;
            p2 = p2->next;
        }
        //Case 3.1 - no match
        if(p1 == NULL){
            cout << name << " was not found in the hashTable" << endl;
        }
        //Case 3.2 - match is found
        else{
            p2->next = p1->next;
            delete p1;
            cout << name << " was removed from the Hash Table." << endl;
        }
    }
}

void FindDrink(string name){
    int idx = Hash(name);
    bool foundName = false;
    string drink;

    item* ptr = hashTable[idx];
    while(ptr){
        if(ptr->name == name){
            foundName = true;
            drink = ptr->drink;
            break;
        }
        ptr = ptr->next;
    }
    if(foundName){
        cout << name << "'s favorite drink = " << drink << endl;
    }
    else{
        cout << name << "'s info was not found in the hashTable." << endl;
    }
}

void PrintItemInIndex(int idx){
    item* ptr = hashTable[idx];
    if(ptr->name == "empty"){
        cout << "index " << idx << " is empty" << endl;
    }
    else{
        cout << "index " << idx << " contains the following item" << endl;
        while(ptr){
            cout << "--------------------\n";
            cout << ptr->name << endl;
            cout << ptr->drink << endl;
            cout << "--------------------\n";
            ptr = ptr->next;
        }
    }
}

void PrintTable(){
    int number;
    for(int i = 0;i < tablesize; i++){
        number = NumberOfItemsIndex(i);
        cout << "--------------------\n";
        cout << "index = " << i << endl;
        cout << hashTable[i]->name << endl;
        cout << hashTable[i]->drink << endl;
        cout << "number of items = " << number << endl;
        cout << "--------------------\n";

    }
}

int NumberOfItemsIndex(int idx){
    int count = 0;
    if(hashTable[idx]->name == "empty"){
        return 0;
    }
    else{
        item* ptr = hashTable[idx];
        while(ptr){
            count++;
            ptr = ptr->next;
        }
        return count;
    }
}

int Hash(string s){
    int hashVal = 0;
    int idx;
    int len = s.length();
    for(int i = 0; i < len; i++){
        hashVal = (hashVal + s[i])*17;
    }
    idx = hashVal % tablesize;

    return idx;
}

void AddItem(string name, string drink){
    int idx = Hash(name);
    if(hashTable[idx]->name == "empty"){
        hashTable[idx]->name = name;
        hashTable[idx]->drink = drink;
    }
    else{
        item* newItem = new item();
        newItem->name = name;
        newItem->drink = drink;
        newItem->next = NULL;

        item* ptr = hashTable[idx];
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = newItem;
    }
}

void Init(){
    for(int i = 0; i < tablesize; i++){
        hashTable[i] = new item();
    }
}

int main(){
    #ifndef ONLINE_JUDGE
        //freopen("in.txt", "r", stdin);
    #endif
    Init();
    
    AddItem("Paul", "Locha");
    AddItem("Kim", "Iced Mocha");
    AddItem("Emma", "Strawberry Smoothy");
    AddItem("Annie", "Hot Chocolate");
    AddItem("Sarah", "Passion Tea");
    AddItem("Pepper", "Caramel Mocha");
    AddItem("Mike", "Chai Tea");
    AddItem("Steve", "Apple Cider");
    AddItem("Sill", "Root Beer");
    AddItem("Marie", "Skinny Latte");
    AddItem("Susan", "Water");
    AddItem("Joe", "Green Tea");

    //PrintTable();
    //PrintItemInIndex(2);
    //FindDrink("Joe");
    /*
    string name;
    while(name != "exit"){
        cout << "Remove ";
        cin >> name;
        if(s != "exit");
        RemoveItem(name);
    }
    */

    return 0;
}