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;
}