hash table（哈希表) 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。

其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。

hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：

  1. 得到key
  2. 通过hash函数得到hash值
  3. 得到桶号(一般都为hash值对桶数求模)
  4. 存放key和value在桶内。

其取值过程是:

  1. 得到key
  2. 通过hash函数得到hash值
  3. 得到桶号(一般都为hash值对桶数求模)
  4. 比较桶的内部元素是否与key相等，若都不相等，则没有找到。
  5. 取出相等的记录的value。
#include <cstdlib>
#include <iostream>
#include <cassert>
#include <vector>
#include <ctime>
#include <algorithm>

using namespace std;

class HashNode
{
public:
    int key;
    int value;
    HashNode *next;
    HashNode(int k, int v):key(k), value(v), next(NULL)
    {

    }
};

class HashTable
{
public:
    HashTable(int slot = 5);
    ~HashTable();
    void Insert(int key, int value);
    int Remove(int key);
    int Query(int key, int &value);
    void Print();
private:
    int m_slot;
    int m_length;
    vector<HashNode*> m_bucket;
};

HashTable::HashTable(int slot /* = 5 */):m_slot(slot), m_length(0)
{
    for (int i = 0; i < slot; i++)
    {
        m_bucket.push_back(0);
    }
}

HashTable::~HashTable()
{
    for (int i = 0; i < m_slot; i++)
    {
        if (m_bucket[i] != NULL)
        {
            HashNode *temp = m_bucket[i];
            HashNode *next = NULL;
            while (temp != NULL)
            {
                next = temp->next;
                delete temp;
                temp = next;
            }
        }
    }
}

void HashTable::Insert(int key, int value)
{
    int num = (unsigned int)key % m_slot;
    HashNode *temp = NULL;
    try
    {
        if (m_bucket[num] != NULL)
        {
            temp = m_bucket[num];
            while (temp->next != NULL)
            {
                temp = temp->next;
            }
            temp->next = new HashNode(key, value);
        }
        else
        {
            m_bucket[num] = new HashNode(key, value);
        }
    }
    catch (bad_alloc &ex)
    {
        cout << ex.what() << endl;
    }
    catch(...)
    {
        cout << "unkowned exception!" << endl;
    }
}

int HashTable::Query(int key, int &value)
{
    int num = (unsigned int)key % m_slot;
    HashNode *temp = NULL;
    if (m_bucket[num] != NULL)
    {
        temp = m_bucket[num];
        while (temp != NULL)
        {
            if (temp->key == key)
            {
                value = temp->value;
                return 0;
            }
            temp = temp->next;
        }
    }
    return -1;
}

int HashTable::Remove(int key)
{
    int num = (unsigned int)key % m_slot;
    HashNode *temp = m_bucket[num];
    HashNode *mPre = NULL;
    if (temp != NULL)
    {    
        while (temp != NULL)
        {    
            if (temp->key == key)
            {
                if (mPre != NULL)
                {                
                    mPre->next = temp->next;
                }
                else
                {
                    m_bucket[num] = temp->next;
                }
                delete temp;
                return 0;
            }
            mPre = temp;
            temp = temp->next;
        }
    }
    cout << "no elements with the specified key" << endl;
    return -1;
}

void HashTable::Print()
{
    for (int i = 0; i < m_slot; i++)
    {
        cout << "bucket" << i <<endl;
        HashNode *temp = m_bucket[i];
        if (temp != NULL)
        {
            while (temp != NULL)
            {
                cout << " <" << temp->key << "," << temp->value << "> ";
                temp = temp->next;
            }
        }
        else
        {
            cout << endl;
        }
        cout << endl;
    }
}

int main(int argc, char *argv[])
{
    HashTable h(10);
    int value;
    srand(unsigned int(time(NULL)));
    for (int i = 0; i < 24; i++)
    {
        int random = rand() % 100;
        h.Insert(random, random + 10);
    }
    h.Remove(56);
    h.Print();
    /*
        h.Query(13, value);
        cout << value << endl;
    */
    
    return 0;
}