数据结构中的哈希表
数据结构中的哈希表·
哈希表(Hash Table)也叫散列表，在本文中，哈希表是一种数据结构，它提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)。因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表，例如拼音检查器。
哈希表也有自己的缺点，哈希表是基于数组的，我们知道数组创建后扩容成本比较高，所以当哈希表被填满时，性能下降的比较严重。
哈希函数·
而哈希表的关键，就是哈希函数。根据这个函数，查找关键字key，可以直接确定查找值所在位置，而不需要一个个比较。这样就**“预先知道”**key所在的位置，直接找到数据，提升效率。
即值地址=H（key）
我们所给的任何符合要求的关键字，代入进哈希函数中，即可得出它所对应的更详细的值或地址。
哈希函数应该满足的三个基本条件：
- 散列函数计算得到的散列值是一个非负整数
- 如果 key1 = key2，那 hash(key1) == hash(key2)
- 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)
第一点：因为数组的下标是从0开始，所以哈希函数生成的哈希值也应该是非负数
第二点：同一个key生成的哈希值应该是一样的，因为我们需要通过key查找哈希表中的数据
第三点：看起来非常合理，但是两个不一样的值通过哈希函数之后可能会产生相同的值，因为我们把巨大的空间转出成较小的数组空间时，不能保证每个数字都映射到数组空白处。所以这里就会才生冲突，在哈希表中我们称之为哈希冲突。
哈希冲突·
对于两个数据元素的关键字 k 和 j ，有k != j，但 Hash(k) == Hash(j)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
哈希冲突不一定出现，但也不可避免的，所以要有解决哈希冲突的方法。
解决哈希冲突的方法有：
- 开放地址法
- 线性探测
数据的插入是线性的查找空白单元，直到找到空白地方存放元素 - 再哈希法
如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个
双哈希的特殊要求：表的容量必须是一个质数
- 线性探测
- 链表法（主用）