哈希桶:建一个存放指针的数组,将hash出的key跟数组的下标进行对应,将对应的数据链接到该位置。
eg:要存11 22 24 34 54 36
利用模除算出位置:
11%10=1
21%10=1
24%10=4
34%10=4
54%10=4
36%10=6
- 代码实现:
- #define _CRT_SECURE_NO_WARNINGS
- #include<iostream>
- using namespace std;
- #include<string>
- #include<vector>
-
-
- template<class K,class V>
- struct KeyValue
- {
- K _key;
- V _value;
- KeyValue<K, V>* _next;
- KeyValue(const K& key, const V& value)
- :_key(key),
- _value(value),
- _next(NULL)
- {}
- };
-
-
- template<class K>
- struct HashFuncDefault
- {
- size_t operator()(const K& key)
- {
- return key;
- }
- };
-
-
- static size_t BKDRHash(const char * str)
- {
- unsigned int seed = 131; // 31 131 1313 13131 131313
- unsigned int hash = 0;
- while (*str)
- {
- hash = hash * seed + (*str++);
- }
- return (hash & 0x7FFFFFFF);
- }
-
-
- template<>
- struct HashFuncDefault<string>
- {
- size_t operator()(const string& key)
- {
- return BKDRHash(key.c_str());
- }
- };
-
-
- template<class K, class V, class HF = HashFuncDefault<K>>
- class HashBucket
- {
- typedef KeyValue<K, V> KV;
- public:
- HashBucket()
- :_size(0)
- {}
-
-
- bool Insert(const K& key, const V& value)
- {
- _CheckCapacity();
- size_t index = HashFunc(key, _table.size());
- KV* cur = _table[index];
- while (cur)
- {
- if (cur->_key != key)
- {
- cur = cur->_next;
- }
- else
- {
- return false;
- }
- }
- KeyValue<K, V>* tem = new KeyValue<K, V>(key, value); //用头插法插入节点
- tem->_next = _table[index];
- _table[index] = tem;
- _size++;
- return true;
- }
-
-
- size_t HashFunc(const K& key, size_t capacity)
- {
- HF hashFunc;
- return hashFunc(key) % capacity;
- }
-
-
- KV* Find(const K& key)
- {
- size_t index = HashFunc(key, _table.size());
- KV* cur = _table[index];
- while (cur)
- {
- if (cur->_key == key)
- {
- return cur;
- }
- cur = cur->_next;
- }
- return NULL;
- }
- void Print()
- {
- size_t size = _table.size();
- for (size_t i = 0; i < size; i++)
- {
- if (_table[i])
- {
- KV* cur = _table[i];
- while (cur)
- {
- cout << "key:" << cur->_key << " value:" << cur->_value << " -> ";
- cur = cur->_next;
- }
- cout << "NULL";
- cout << endl;
- }
- }
- }
-
-
- void Remove(const K& key)
- {
- size_t index = HashFunc(key, _table.size());
- KV* cur = _table[index];
- if (cur == NULL)
- {
- return;
- }
- if (cur->_key == key)
- {
- _table[index] = cur->_next;
- }
- KV* prev = cur;
- while (cur->_next)
- {
- cur = cur->_next;
- if (cur->_key == key)
- {
- prev->_next = cur->_next;
- delete cur;
- cur = NULL;
- _size--;
- return;
- }
- prev = cur;
- }
- }
- ~HashBucket()
- {
- size_t size = _table.size();
- for (size_t i = 0; i < size; i++)
- {
- if (_table[i])
- {
- KV* cur = _table[i];
- while (cur)
- {
- KV* del = cur;
- cur = cur->_next;
- delete del;
- }
- }
- }
- }
- protected:
-
- void _CheckCapacity()
- {
- size_t newCapacity = 0;
- if (_table.size() == _size)
- {
- newCapacity = _GetSize(_size);
- vector<KV*> tmp;
- tmp.resize(newCapacity);
- for (size_t i = 0; i < _size; i++)
- {
- KV* cur = _table[i];
- while (cur)
- {
- KeyValue<K, V>* move = cur;
- cur = cur->_next;
- size_t index = HashFunc(move->_key, tmp.size());
- move->_next = tmp[index]; //用头插法更方便
- tmp[index] = move;
- }
- }
- _table.swap(tmp);
- }
- }
-
-
-
- size_t _GetSize(const size_t size)
- {
- const int _PrimeSize = 28;
- static const unsigned long _PrimeList[_PrimeSize] =
- {
- 53ul, 97ul, 193ul, 389ul, 769ul,
- 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
- 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
- 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
- 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
- 1610612741ul, 3221225473ul, 4294967291ul
- };
- size_t i = 0;
- for (; i < _PrimeSize; i++)
- {
- if (_PrimeList[i] <= size && i != _PrimeSize - 1)
- {
- i++;
- }
- else
- {
- break;
- }
- }
- return _PrimeList[i];
- }
-
-
- private:
- vector<KV*> _table;
- size_t _size;
- };
-
-
-
- void test()
- {
- //HashBucket<string, string> hs;
- //hs.Insert("hello", "你好");
- //hs.Insert("world", "世界");
- HashBucket<int, int> s;
- s.Insert(1, 2);
- s.Insert(2, 2);
- s.Insert(54, 1);
- s.Insert(53, 44);
- //s.Remove(1);
- //s.Remove(53);
- s.Print();
- }
-
-
- int main()
- {
- test();
- return 0;
- }