数据结构与算法-哈希表

本篇介绍哈希表相关的基础题目。

题目一

认识哈希函数和哈希表

哈希函数：传入字符串返回哈希码。

特征：

1. 输入的域是无穷大的；
2. 输出的域是有限的；
3. 输入一样，输出一样（不含任何随机成分）；
4. 当输入不一样的时候存在输出一样的可能性；（哈希碰撞）
5. 虽然会存在两个不同的输入得到了相同的输出，但是当不同的输入特别多时，将在整个S域中均匀的出现它们的返回值（均匀分布）；（哈希函数的离散型）
6. 与输入的规律是没有关系的；（所以哈希函数也可用来打乱输入样本的规律）（雪崩效应）

推论：

• 在有很多很多input点，在hash后 %m，最终的返回会在0 ~ m-1这个范围，在这个范围中也均匀分布。

需要1000个函数，且要求相对独立，有一个hash函数，该怎么做出1000个呢？

• 把一个hash函数拆成两个（两个种子）（如果返回值为16个字符，前8个字符为h1；后8个字符为h2）(每个位置上的字符较其它位置上的字符都是独立的)；
• h1 + 1*h2 = h3
• h1 + 2*h2 = h4
• h1 + 3*h2 = h5
• 这样改变系数可以做出1000个来。

哈希表的经典结构：

0
1
2 -> (B,3)
3
...
10 -> (A,17) -> (左,31)   重复的key将覆盖value，不重复将挂在上一个key的后面
11
...
16

经典结构中是一个桶 + 单链表

常用的操作：
put(key1,value1)   ->  key1 -> (hash) -> hashcode1 -> %17 = 0~16 
get(key1)
remove(key1)

• 桶 + 单链表
• 特点：当我们不断地加入key，这个表中每个节点的内容（链表中的节点）是均匀增加的。
• 这样当一条链中的数量到达了上限，那我们可以认为每条链都将达到上限，这样将经历扩容
• 增删改查都是O(1)

扩容：

• 将每个值取出用它的哈希值重新mod一个数，然后放入新的哈希表中。

为什么扩容还能做到O(1)？

• 首先这是一个平均复杂度，虽然每次扩容的代价可能会很高，但需要扩容的频率可以压得很低，如O(logaN)，这个底数a可以很大很大（每一次扩容得过程中长度增加a-1倍，扩到N需要logaN次）。
• 在实际使用中还可以离线扩容（等用完旧哈希表得时候，新哈希表已经建好并替换了旧哈希表了）

在jvm中，桶后接得是红黑树。

例子：有一个很大的文本文件中（100T），每一行是一个字符串，找出重复的字符串并打印。（大数据问题）（使用哈希来进行分流）

1. 直接问你可以给我多少台机器?
   • 给每一台机器编号 0 1 2 … 999
2. 读出每一行，利用hash函数计算出一个hashcode，然后mod1000，值是多少，就放在相应的那个机器中。
3. 这样相同的字符串会分配到相同的机器上。
4. 这样对于100T文件，如果有m种字符串的话，会将这m种字符串均匀的分配到这1000台机器中，这样的话大大的降低了单机的样本（1000台机器并发）。如果还是太大，就再次使用hash来分成多个小文件，来让单机跑多个并行任务。

利用hash来将大任务化简成小任务，小任务化简成巨小的任务。

思想：相同输入产生相同输出；不同输入均匀分布。

---

持续更新中！！！