HashTable哈希/散列表

哈希表充分体现了算法设计领域的经典思想：空间换时间

哈希函数

不管是散列还是哈希，这都是中文翻译的差别，英文其实就是 “Hash” 。所以，我们常听到有人把 “散列表 ” 叫作 “哈希表”“Hash 表 ” ，把 “哈希算法 ” 叫作 “Hash 算法” 或者 “散列算法 ” 键转换成索引,同时键通过哈希函数得到的索引分布越均匀越好。

原则

1一致性 如果a==b 则hash(a)==hash(b) 2 高效性 计算高效简单 3 均匀性 哈希值均匀分布

hashcode

整型 小范围正整数直接使用 小范围负整数进行偏移 大整数 通常做法取模，也就是取大整数的后几位，容易出现分布不均匀。模一个素数 字符串 转换成整数处理

image.png

哈希函数与余数

余数总是在一个固定的范围内。 整数是没有边界的，它可能是正无穷，也可能是负无穷。但是余数却可以通过某 一种关系，让整数处于一个确定的边界内。 计算星期 2019年的6月3号是周一 那么30天之后的2019年7月3日是星期几 拿 30 除以 7（因为一个星期有 7 天），然后余 2，最后在今天的基础上加2天，这样你就能知道 30 天之后是星期三了。 同余定理 两个整数 a 和 b，如果它们除以正整数 m 得到的余数相等，我们就可以说 a 和 b 对于模 m 同余。 同余定理的用途：同余定理其实就是用来分类

哈希算法用途

1.安全加密 哈希算法是MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA （Secure Hash Algorithm，安全散列算法）。

2数据校验 通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。我们在前面讲过，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一 丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后 跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

image.png

3唯一标示 我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字 节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5 ），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库 中，这样就可以减少很多工作量。

4负载均衡 会话粘滞（session sticky），在一次会话中的所有请求都路由到同一个服务器上。 通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进 行取模运算，最终得到的值就是应该被路由到的服务器编号。 这样，我们就可以把同一个IP过来的所有请求，都路由到同一个后端服务器上。

5数据分片 统计 “ 搜索关键词 ” 出现的次数？ 1搜索日志很大，没办法放到一台机器的内存中。 2如果只用一台机器来处理这么巨大的数据，处理时间会很长。 具体的思路是这样的：为了提高处理的速度，我们用n台机器并 行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。处理过程也是MapReduce 的基本设计思想。 给这1亿张图片构建散列表大约需要多少台机器。 散列表中每个数据单元包含两个信息，哈希值和图片文件的路径。假设我们通过 MD5 来计算哈希值，那长度就是 128 比特，也就是 16 字节。文件路径长度的上限 是 256 字节，我们可以假设平均长度是 128 字节。如果我们用链表法来解决冲突，那还需要存储指针，指针只占用 8 字节。所以，散列表中每个数据单元就占 用 152 字节（这里只是估算，并不准确）。 假设一台机器的内存大小为 2GB ，散列表的装载因子为 0.75 ，那一台机器可以给大约 1000 万（ 2GB*0.75/152 ）张图片构建散列表。所以，如果要对 1 亿张图片构建 索引，需要大约十几台机器。在工程中，这种估算还是很重要的，能让我们事先对需要投入的资源、资金有个大概的了解，能更好地评估解决方案的可行性。 实际上，针对这种海量数据的处理问题，我们都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、 CPU 等资源的限制。

6分布式存储 一致性哈希算法 假设我们有k个机器，数据的哈希值的范围是 [0, MAX] 。我们将整个范围划分成 m 个小区间（ m 远大于 k ），每个机器负责 m/k 个小区间。当有新机器加入的时候， 我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。`