数据结构与算法-哈希表

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

题目一

认识哈希函数和哈希表

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

特征:

  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个来。

哈希表的经典结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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来将大任务化简成小任务,小任务化简成巨小的任务。

思想:相同输入产生相同输出;不同输入均匀分布。


持续更新中!!!

-------------The End-------------

本文标题:数据结构与算法-哈希表

文章作者:Naqin

发布时间:2020年01月20日 - 13:01

最后更新:2020年02月24日 - 22:02

原始链接:https://chennq.top/数据结构/20200120-data-struct-hash-table.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Naqin wechat
欢迎看官加我微信!
坚持原创技术分享,您的支持将鼓励我继续创作!
0%