二次探测是避免哈希冲突的一种常见手段,思想是:
插入:
找到哈希位置(serch)->如果不冲突就插入,冲突就进行第一次探测
第1次探测:
哈希位置变为原有哈希位置加上1*1的偏移->进行插入
....
....
第i次探测:
哈希位置变为原有哈希位置加上i*i的偏移->进行插入
知道插入完成为止。
如图所示:
哈希类代码如下:
#pragma once #include<vector> #include<string> enum Status { DELETE, EMPTY, EXIST, }; template<class K, class V> struct KV { KV() {} KV(K _key, V _value) :key(_key) , value(_value) {} Status s; K key; V value; }; template<class K> struct DefaultHash { size_t operator()(const K& k) { return k; } }; template<> struct DefaultHash<string> { size_t operator()(const string&k) { size_t ret = 0; for (size_t i = 0; i < k.size(); ++i) { ret *= 10; ret += k[i]; } return ret; } }; template<class K,class V, class Hash = DefaultHash<K> > class HashTable { public: HashTable(size_t capacity) :tables(new KV<K,V>[capacity]) ,_size(0) , _capacity(capacity) { for (size_t i = 0; i < _capacity; ++i) { tables[i].s = EMPTY; } } HashTable() :_size(0) , _capacity(0) {} void Push(const KV<K,V> &x) { size_t index = search(x.key); tables[index].s = EXIST; tables[index].key = x.key; tables[index].value = x.value; ++_size; } void Print() { for (size_t i = 0; i < _capacity; ++i) { cout << i << ":"; if (tables[i].s == EXIST) cout <<"["<<tables[i].key<<","<< tables[i].value<<"]"; else cout << "NULL"; cout << endl; } cout << endl; } int Find(const K& key) { Hash Search; int index = Search(key) % _capacity; size_t i = 0; while (tables[index].s != EMPTY) { if (tables[index].key == key&&tables[index].s == EXIST) return index; i++; index += 2*i-1; if (index >= _capacity) index %= _capacity; } return -1; } void Pop(const K& key) { int index = Find(key); if (index > 0) { tables[index].s = DELETE; _size--; } } ~HashTable() { if (tables) delete[]tables; _size = 0; _capacity = 0; } protected: size_t search(K key) { if (_size * 2 >= _capacity) { HashTable tmp(_capacity * 2 + 10); for (size_t i = 0; i < _capacity; ++i) { if (tables[i].s == EXIST) tmp.Push(tables[i]); } std::swap(tables, tmp.tables); std::swap(_size, tmp._size); std::swap(_capacity, tmp._capacity); } Hash Search; size_t index = Search(key)%_capacity; size_t i = 0; while (tables[index].s == EXIST) { i++; index += i*i; if (index >= _capacity) index %= _capacity; } return index; } protected: KV<K,V>* tables; size_t _size; size_t _capacity; };
如有疑问希望提出,有不足也希望指正
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。