1.底层结构
顺序结构以及平衡中，元素关键码与其存储位置之间没有相对应的关系，因此在查找一个元素时，要经过关键码的多次比较。顺序查找的时间复杂度为O(N)。
理想的搜索方法：可以不经过比较，依次直接从表中直接搜索到指定元素，如果构造一种数据结构，通过某种函数使元素的存储位置与它的关键码之间能够建立----映射关系，就可以很快的查找到指定的元素。
插入元素：根据插入元素的关键码，用函数计算出这个元素的存储位置并存放
查找元素：对元素的关键码进行计算，得到的函数值去取出此位置的存储元素，并把输入的元素与此元素进行比较，若关键码相等，则查找成功
该方式为哈希(散列)方法，哈希方法中的转换函数为哈希函数，构造出来的结构为哈希表
一般是用关键码膜上该结构的总容量，得到的值就为映射后的位置下标。
2.哈希冲突
对于俩个数据元素的关键码通过哈希函数后得到的值一样，不同关键字通过相同哈希函数计算出相同的哈希值地址，该现象称为哈希冲突或哈希碰撞。
3.哈希函数
引起哈希冲突的原因可能：哈希函数设计不够合理
哈希函数设计原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，则值域必须在[0 m-1]之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数形式相对简单
除留余数法
设散列表中允许存储的地址数位m个，取一个不大于m的数p，且p最接近或者等于m的质数作为除数，Hush(key)=key%p(p<m) ,将关键码转换为哈希地址
补充：
key%2^16表示的是取后十六位，然后key>>（32-n）（假设n=16）是把前16位移到后16位，最后把前16位和后16位异或的结果作为哈希值(key的前16位和后16位都到同一位置也就是后16位上了)，把key的每一位都参与到计算，这样得出的哈希值冲突会更少一些。
哈希冲突解决
闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被填满，说明哈希表中心必然还有空位置，那么可以把key存放到冲突位置的下一个位置去。
找到空位置
1.线性探测
如下图要插入元素44，先通过哈希函数计算出哈希地址，44%10=4，应在4的位置，但是这个位置已经放了数据了，所以要从发生冲突的位置开始依次向后找，直到寻找到空位置为止
2.删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其它元素的搜索，比如删除4，那么查找44时根据计算的哈希地址就是4的位置，当44不在4位置在后面。所以通过枚举用标记的方式来删除元素。
enum State
{
EMPTY,
EXIST,
DELETE
};
3.哈希表扩容
散列表的载荷因子定义：a=填入表中的个数/散列表的长度
对于开放定址法， 载荷因子应该限制在0.7~0.8以下，
线性探测优点：实现简单
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据堆积，在查找时需要进行多次比较，导致搜索效率降低。
二次探测
线性探测的缺陷是产生冲突的数据堆积到一块，这与其找找的下一个位置有关，从发生冲突的位置向后找空位置可能会发生的问题，二次探测就是为了避免该现象的出现。
hash=hash0+i^2 or hash=hash0+i^2
代码实现
1.枚举定义状态
设置三个状态存在，空，删除
enum State
{EXIST,EMPTY,DELETE
};
2.定义存在哈希表里面的数据
pair模板，first表示键值，second表示值
template<class K,class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};
3.哈希表的构造
内联函数里面提供的数字就是质数，有28个，这里lower_bound是选一个大于等于n的数字，这里的n也就是哈希表的存储个数，返回处使用了三目操作符，如果不是最后一个就是pos，如果是最后一个就要返回最后一个的前一个。
HashTable():_tables(__stl_next_prime(0)),_n(0)
{}
inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}4.哈希表的插入
首先要判断插入的元素是否已经存在，接着是判断载荷因子是否超过0.7，这里把_n*10所以和7比较，如果大于7就要扩容了，哈希表扩容则原来的存储位置在新的里面是不一样的，因为之前的存储是旧的size，扩容后是新的size，哈希函数得出的值改变了，所以存储位置要重新计算，这里newht的空间还是去之前的28个里面选，这里+1是因为28个数字对应不同区间，所以只需要加一就会到下一个区间，还要判断旧表每一个位置的状态是否是存在的，说明之前是由元素在这个位置上，则把此处的元素再作为Insert的参数重新插入，最后交换地址，如果没超过0.7，则就正常插入，通过模来得到哈希值，然后还要线性检测是否此位置为空位置，while循环后就找到了空位置，则插入并改变状态为存在，并把已经存储的个数n++。
bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;if (_n * 10 / _tables.size() >= 7){HashTable<K, V> newht;newht._tables.resize(__stl_next_prime(_tables.size() + 1));for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hash0 = kv.first % _tables.size();size_t hashi = hash0;size_t i = 1;int flag = 1;while (_tables[hashi]._state == EXIST){hashi = (hash0 + i) % _tables.size();++i;///二次探测////// hashi=(hash0+(i*i*flag))%_tables.size();/// ///}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}5.哈希表的查找
这里查找需要注意的是位置被占了，可能在哈希函数得出的值的后面或者前面，先得到要查找的键的哈希值，然后用循环来寻找，先看是否为空，空说明不存在，如果不为空还要判断键值是否一样，不一样就线性检测去遍历，找到就返回此处的地址。
HashData<K, V>* Find(const K& key)
{size_t hash0 = key % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi = (hash0 + i) % _tables.size();++i;}return nullptr;
}6.哈希表的删除
前面已经提到不能删除，只改变状态为删除状态就行，先用Find去找到指定位置，判断是否找到，找到就只改变状态变量。
bool Erase(const K& key)
{HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;return true;}else{return false;}
}总代码
HashTable.h
#pragma once#include<vector>enum State
{EXIST,EMPTY,DELETE
};template<class K,class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K,class V>
class HashTable
{
public:HashTable():_tables(__stl_next_prime(0)),_n(0){}inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;if (_n * 10 / _tables.size() >= 7){HashTable<K, V> newht;newht._tables.resize(__stl_next_prime(_tables.size() + 1));for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hash0 = kv.first % _tables.size();size_t hashi = hash0;size_t i = 1;int flag = 1;while (_tables[hashi]._state == EXIST){hashi = (hash0 + i) % _tables.size();++i;///二次探测////// hashi=(hash0+(i*i*flag))%_tables.size();/// ///}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){size_t hash0 = key % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi = (hash0 + i) % _tables.size();++i;}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n;
};
test.c
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<set>
#include<unordered_set>using namespace std;
#include"HashTable.h"
int main()
{//int a[] = { 19,30,52,63,11,22 };int a[] = { 19,30,5,36,13,20,21,12 };HashTable<int, int> ht;for (auto e : a){ht.Insert({ e, e });}//ht.Insert({ 15, 15 });ht.Erase(30);if (ht.Find(20)){cout << "找到了" << endl;}if (ht.Find(30)){cout << "找到了" << endl;}else{cout << "没有找到" << endl;}return 0;
}