我们在哈希第一弹中提到了避免哈希冲突的三种方法，在本篇博文中我们对他们进行更加详细的了解
哈希冲突的解决方法 闭散列（开放定址法）： 当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把关键字存放到冲突位置中的“下一个”空位置中去。
如何寻找下一个空位置呢？
线性探测： 从发生冲突的位置开始，依次向后探测，直到寻找下一个空位置为止
二次探测： 从发生冲突的位置开始，找下一个空位置，查找空位置的方法为 （+i^2）%m，i=1,2,3........；m是哈希表大小，是经过关键字计算后的出的哈希地址
开散列（链地址法、开链法） 对关键字集合用散列函数计算散列地址，具有相同地址的关键码归于同一个子集合，每一个子集和称为一个桶，各个桶中的元素通过一个单链表连接起来，各链表的头结点存储在哈希表中。 ———————————————— 版权声明：本文为博主「书生Qyuan」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/weixin_43519514/article/details/107101794
我们在之前了解了线性探测如何解决哈希冲突，实现和理解都很简单，通过哈希函数算出所在位置，如果没有存放数据，则直接存放；如果存放了数据，则去找下一个没有存放数据的位置，进行存放该数据。但这里好像又出现了一个比较头疼的问题，看下图，散列表在插入一个5，经过计算我们应该插入5的位置，但是此时444占据了这个位置，我们就需要找下一个位置了。这可以完成，且不是太大问题。关键是我们要查找的时候，就有可能要遍历整张表，效率可能为O（N），此时我们设为哈希表的意义就不太大了。
而出现这个问题，最主要的是一旦某处发生了哈希冲突，所有的冲突可能连在一起；不同关键码占据了可利用的空位置，是寻找某关键码的位置需要许多次比较，导致搜索效率降低。
线性探测使产生冲突的数据堆积在一起，这与线性探测一次查找下一个空位置有关。二次探测，为了解决这个问题采用了不同的查找下一个空位置的方法。但由此也产生了一个问题：空间利用率不太高。
总之，闭散列的这两种方法都有一定的缺陷，下面我们通过粗略的实现，来理解一下；
不过，在代码的实现之前我们先达成一些共识：怎么插入数据、怎么查找数据、怎么删除数据；我们也主要实现这三个功能。
插入数据比较简单：我们先通过哈希函数算出散列地址，这个位置没有存放有效数据，我们就可以直接存放数据，倘若此处有数据了，我们往后找空位置，存放数据。
怎么查找数据呢？如果我们遍历整张表的话，那么效率极低，我们也就完全没有必要实现哈希表了，直接vector搞定；所以，为了效率我们不能遍历整张表。那么怎么办呢？我们刚才插入的时候，就往后找空位置插入，这就意味着如果我们通过哈希函数计算出散列地址，而该地址没有存放我们想要的数据，我们就可以往后找，如果找的了空位置呢？肯定这张表中没有我们想要的数据，查找也就可以到此结束了。
怎么删除数据呢？还是通过哈希函数算出散列地址，直接删除吗？这个想法，对我们来说是绝对不可能的方案。倘若我们这样删除了，按照刚才我们查找的想法，查找与之冲突的元素时，得知此处为空，我们便会认为那个数据没有在此表中，而实际可能在后面。如下图，我们删除了44，在查找444的时候就会出现问题。所以我们在删除的时候，关键的一步是建立数据的状态，具体时间什么样，我们代码中见
namespace CloseHash{ //标记当前表中位置的状态 Empty表示这个位置没有数据，Delete表示该位置的数据已经被删除了，Exit表示当前位置存有数据 enum status{ Empty, Delete, Exit, }; template<class T> struct HashData{ T _data; status _status; }; template <class K,class T,class KeyofValue> class Hashtable{ typedef HashData<T> Data; private: std::vector<Data> _table; //哈希表，用来存放数据 size_t _num=0 ; //记录哈希表中有效数据的个数 public: //插入的时候我们什么时候需要进行扩容呢？等到满的时候是不可能的？ //我们需要一个空的位置，进行判断是否还要继续进行查找 //因此我们需要一个负载因子，等负载因子到达一个值或高于这个值的时候，我们就进行扩容 bool insert(const T& data) { KeyofValue kofv; if ( _table.size() == 0 || (_num * 10) / _table.size() >= 7 ) { std::vector<Data> newtable; size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2; newtable.resize(newsize); for (size_t i = 0; i < _table.size(); ++i) { if (_table[i]._status == Exit) { size_t newIndex = kofv(_table[i]._data) % newsize; while (newtable[newIndex]._status == Exit) { ++newIndex; if (newIndex == newtable.size()) { newIndex = 0; } } newtable[newIndex] = _table[i]; } } _table.swap(newtable); } //线性探测 size_t index = kofv(data) % _table.size(); while (_table[index]._status == Exit) { if (kofv(_table[index]._data) == kofv(data)) return false; ++index; if (index == _table.size()) index = 0; } _table[index]._data = data; _table[index]._status = Exit; ++_num; return true; } T* find(const T& data) { KeyofValue kofv; size_t index = kofv(data) % _table.size(); while (_table[index]._status != Empty) { if (_table[index]._status != Empty&&kofv(_table[index]._data) == kofv(data)) { if (_table[index]._status == Exit) return &(_table[index]._data); else if (_table[index]._status == Delete) return nullptr; } else { ++index; if (index == _table.size()) index = 0; } } return nullptr; } bool erase(const T& data) { Data* ret = find(data); if (ret != nullptr) { ret->_staus = Delete; --_num; return true; } return false; } }; }
缺点：
一旦某处发生了哈希冲突，所有的冲突可能连在一起；不同关键码占据了可利用的空位置，是寻找某关键码的位置需要许多次比较，导致搜索效率降低。
发现二次探测一定程度上改善了线性探测的缺点。但由于查找位置的方法，造成了一定量的空间浪费。
开散列的情况我们留在哈希第三弹！
本片博文就此，就结束了！
