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。

      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    
    #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;
    }