哈希表
哈希表是一种数据结构，它使用哈希函数组织数据，以支持快速插入和搜索。
哈希表的原理
哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说：
1.当我们插入一个新的键时，由哈希函数决定这个键应该分配到哪个桶中，并将键存放在该桶中。
2.当我们想要搜索一个键时，我们通过哈希函数确定该键所在的桶，并在桶中对数据进行搜索。
例子：
简单的来说，哈希表是键对桶的一种结构，将两者连接起来的桥梁是哈希函数。
设计哈希表
在设计哈希表中，我们应该注意这两个基本因素：
1.哈希函数
哈希函数(散列函数)是哈希表中最重要的组件，哈希表用于将键映射到桶上，因此哈希函数决定了哈希表如何映射。下面我们给出哈希函数需要满足的特性：
1.确定性
对于每个键，哈希函数不能给出两个桶来装这个键。即如果两个散列值是不同的，则键肯定是不同的。
2.冲突碰撞
哈希函数的输入和输出不是一一对应的，即无法构成满射，对于一个哈希值，可能有两个值与之对应，也可能有一个值与之对应。也无法构成单射。
3.不可逆性
典型的散列函数都有非常大的定义域，同时散列函数具有有限的值域，在某些情况下，散列函数可以设计成具有相同定义域和值域的单射，散列函数必须具有不可逆性。
4.混淆性
输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。（这个适用于MAC，常用于加密方面，而常用的数据结构并没有满足）
2.冲突解决
理想情况下，如果我们的哈希函数满足一一映射，给定一个键就可以找到一个不被其他键值占用的桶，我们将不需要去处理冲突。然而， 这种是种乌托邦式的了，当我们的数据量非常大的时候，对应值也非常大。因此，在大多数情况下，冲突是不可避免的，这也是哈希函数的特性。比如，我们给定这样一个哈希函数y=x%10，显而易见，10和20都分配给了桶0，因此构成了一个冲突。
解决冲突的算法应该解决以下问题：
如何组织在同一个桶中的值？
如果为同一个桶分配了太多的值，该怎么办？
如何在特定的桶中搜索目标值？
根据我们的哈希函数，这些问题与桶的容量和可能映射到同一个桶的键的数目有关。让我们假设存储最大键数的桶有 N 个键。
通常，如果 N 是常数且很小，我们可以简单地使用一个数组将键存储在同一个桶中。如果 N 是可变的或很大，我们可能需要使用高度平衡的二叉树来代替.。
通常的冲突解决方法有三种：
开放定址法（闭散列）：
开放定址法又称为再哈希法， 如果我们当前的键为p,但是Hash(p)位置已存在值，因此我们需要换个位置。此时我们利用该公式找到位置:
解决冲突思想：为每个桶提供若干备用桶，他们之间构成一条查找链。
那么根据i值选择的不同，开发定址法又可以分为：
线性试探，平方试探，双向平方试探，随机试探。
封闭定址策略（开散列法）
开放定地法的思想也很简单，每个桶存放一个指针，指向存放在该桶的冲突值，组成链表。即通过数组+链表的方式解决冲突
下面给出两个哈希函数构造的练习题，可以通过开散列法解决冲突：
