散列表
TableSize:表的大小,习惯于让表从 0 到TableSize-1
变化
散列函数:映射,用于将每个关键字映射到从 0 到 TableSize-1 这个范围中的某个数,并放到适当的单元中
理想情况下,不同的关键字映射到不同的单元;但实际上不可能实现,单元个数有限
冲突:不同的关键字由散列函数得到一致的 hash,导致插入的位置一致所产生的冲突
分离链接法和开放定址法解决
分离链接法
将元素的关键字进行散列,根据散列,将元素保存到对应位置的链表中,STL 中有相关实现方法,重点看一下 HashTable 的原理
search:
- 计算散列
- 得到适当的链表
- 在链表中查找
insert:
- 计算散列
- 得到适当的链表
- 头插
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
| #ifndef HASHTABLE_HASHTABLE_H #define HASHTABLE_HASHTABLE_H
#include "../include/Hash.h" #include <vector> #include <list>
template<typename HashEdObj> class HashTable { public: explicit HashTable(int size = 101);
bool contains(const HashEdObj &x) const;
void makeEmpty();
bool insert(const HashEdObj &x);
bool insert(HashEdObj &&x);
bool remove(const HashEdObj &x);
private: std::vector<std::list<HashEdObj>> theLists; int currentSize;
void rehash();
size_t myhash(const HashEdObj &x) const; };
template<typename HashEdObj> inline size_t HashTable<HashEdObj>::myhash(const HashEdObj &x) const { static hash<HashEdObj> hf; return hf(x) % theLists.size(); }
template<typename HashEdObj> inline void HashTable<HashEdObj>::makeEmpty() { for (auto &thisList:theLists) thisList.clear(); }
template<typename HashEdObj> inline bool HashTable<HashEdObj>::contains(const HashEdObj &x) const { auto &whichList = theLists[myhash(x)]; return find(begin(whichList), end(whichList), x) != end(whichList); }
template<typename HashEdObj> inline bool HashTable<HashEdObj>::remove(const HashEdObj &x) { auto &whichList = theLists[myhash(x)]; auto itr = find(begin(whichList), end(whichList), x);
if (itr == end(whichList)) return false;
whichList.erase(itr); --currentSize; return true; }
template<typename HashEdObj> inline bool HashTable<HashEdObj>::insert(const HashEdObj &x) { auto &whichList = theLists[myhash(x)];
if (find(begin(whichList), end(whichList), x) != end(whichList)) return false;
if (++currentSize > theLists.size()) rehash();
return true; }
template<typename HashEdObj> inline bool HashTable<HashEdObj>::insert(HashEdObj &&x) { auto &whichList = theLists[myhash(x)];
if (find(begin(whichList), end(whichList), x) != end(whichList)) return false;
if (++currentSize > theLists.size()) rehash();
return true; }
#endif
|
开放定址法
将元素的关键字进行散列,根据散列,将元素保存到对应的位置(定址);如果对应位置发生冲突,寻找空闲的位置保存(开放)
线性探测法
冲突解决方法:
:放置的位置
:冲突次数
根据散列探测表中的空闲位置,直接放置;发生冲突时查找下一个位置,如果下一个位置空闲则防止,否则继续查找下一个位置
对于一个较大且较空的表,也可能会存在这样一种情况:很多元素聚集在一些区块,称为一次聚集
例:插入{89,18,49,58,69},冲突解决方法:
平方探测法
冲突解决方法:
:放置的位置
:冲突次数
- 根据散列探测表中的空闲位置(此时冲突 ),如果成立则直接放置()
- 发生冲突时查找下一个位置(冲突为 ),如果空闲,则根据 ,得到放置的位置是散列位置的下一个单元
- 如果再次冲突(冲突为 ),则查找 ,第四个位置,空闲则放置,得到放置的位置是散列位置后的第四个单元
- 再次冲突(冲突为 ),则查找 ,第九个位置,空闲则放置
例:插入{89,18,49,58,69},冲突解决方法:
再散列
当元素综述超过表的固定大小时,重置表,进行扩展,再将所有元素重新计算散列,存入相应位置
1 2 3 4 5 6 7 8 9 10 11 12 13
| template<typename HashEdObj> inline void HashTable<HashEdObj>::rehash() { std::vector<std::list<HashEdObj>> oldLists = theLists; theLists.resize(nextPrime(2 * theLists.size())); for (auto &thisList:theLists) thisList.clear();
currentSize = 0; for (auto &thisList:oldLists) for (auto &x:thisList) insert(std::move(x)); }
|