散列表与hash函数

深碍√TFBOYSˉ_ 2023-06-20 09:20 35阅读 0赞

散列表：  
hash冲突解决  
1）开放定址法 ：  
存入：冲突的 进行二次处理，加线性，平方等；以线性为例，会逐个向下找，直到找到一个空的位置然后放进去  
查找：与存入相似，先hash定位起始的查找位置，然后向下找等于的对象，如果遇到空的说明不存在  
删除：因为上面查找遇空则说明不存在，所以不可以直接删除，仅仅可以标记删除  
2）链表:  
3）再hash:产生冲突时，计算另一个哈希函数地址，到不冲突为止。使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。  
4）公共溢出区：把溢出的放到一起  
装载因子=填入表中的元素个数/散列表的长度

假设我们有 10万条URL 访问日志次数表，如何按照访问次数给 URL 排序？  
1：保存次数  
遍历 10 万条数据，以 URL 为 key，访问次数为 value，存入散列表，同时记录下访问次数的最大值 K，时间复杂度 O(N)。  
k不大可以使用桶排序，否则快排

有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？  
一个用来查，一个用来插入  
以第一个字符串数组构建散列表，key 为字符串，value 为出现次数。再遍历第二个字符串数组，以字符串为 key 在散列表中查找，如果 value 大于零，说明存在相同字符串。时间复杂度 O(N)。

work文档中的英文字母校验怎么实现的？  
hash结构，key存储hashcode，value存储多个单词，  
当需要校验一个单词是，先求hash，然后逐个比较，如果没有相等的，则说明单词错误

工业级水平的散列表：  
怎么设计散列函数？  
计算简单  
结果足够分散  
实例：  
1）数据分析法 如手机号，后四位重复可能性较小  
2）直接寻址法、平方取中法、折叠法、随机数法

装填因子过大处理？ 装填因子越大，越节约空间，但是查找等操作会耗时。  
扩容：散列函数重新计算所有装填因子的位置，并进行迁移

扩容压力过大的问题，怎么解决？  
达到装填因子的时候，先创建新的，同时将新的数据放入新的散列表，老散列表中数据每次迁移一个  
问题：查询麻烦，需要先到新的查，然后老的查

冲突解决？  
开放寻址和链表各适用什么场景：  
链表：适合于冲突较多，装填因子较大的场景。查询较慢，可以物理删除，难序列化。  
寻址：适合于冲突少，装填因子小的场景。查询较快，只能逻辑删除，易序列化

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

java HashMap：  
1）可初始化大小 默认16  
2）装载因子与动态扩容 0.75  
3）散列冲突解决，拉链法：链表或红黑树结构

为什么是拉链法不是开放定址？  
1） 无法支持大量数据，扩容过于频繁  
2） 删除仅仅可以逻辑删除，如果真实删除，以前放入的可能会丢失  
3） 难以优化

为什么开始是链表，后来是红黑树？  
红黑树需要维护平衡结构，少量数据的时候是不值得的。  
为什么是链表不是数组？  
链表增删该方便，查虽然会慢一点，但是一般长度有限，此时数组的优势查找快根本体现不出来。

那怎么设计工业级的散列表？  
特性：  
1）能快速查找  
2）省内存  
3）极端情况的稳定性

JDK HashMap源码中，是分两步走的：  
1. hash值的计算，源码如下：  
static final int hash(Object key) \{  
        int hash;  
        return key == null ? 0 : (hash = key.hashCode()) ^ hash >>> 16;  
 \}  
2. 在插入或查找的时候，计算Key被映射到桶的位置：  
int index = hash(key) & (capacity - 1)  
\----------------------------  
JDK HashMap中hash函数的设计，确实很巧妙：

首先hashcode本身是个32位整型值，在系统中，这个值对于不同的对象必须保证唯一（JAVA规范），这也是大家常说的，重写equals必须重写hashcode的重要原因。

获取对象的hashcode以后，先进行移位运算，然后再和自己做异或运算，即：hashcode ^ (hashcode >>> 16)，这一步甚是巧妙，是将高16位移到低16位，这样计算出来的整型值将“具有”高位和低位的性质

最后，用hash表当前的容量减去一，再和刚刚计算出来的整型值做位与运算。进行位与运算，很好理解，是为了计算出数组中的位置。但这里有个问题：  
为什么要用容量减去一？  
因为 A % B = A & (B - 1)，所以，(h ^ (h >>> 16)) & (capitity -1) = (h ^ (h >>> 16)) % capitity，可以看出这里本质上是使用了「除留余数法」

散列表和链表一起使用

为什么是拉链法 不是开放地址  
1）不能物理删除，占用空间，且减慢查询  
2） 开放发填空因子小，仅仅适合少量数据

LRU缓存淘汰算法：  
链表实现  
访问：已有，节点迁移到尾部  
新的：  
有空间，直接放到尾部  
无空间，删除头部，再插入新的  
因为链表需要先查找，而查找的时间复杂度是O(n),所以所有操作的时间复杂度都是O(n)

散列表 + 链表的实现  
散列表：能够快速查找、删除、插入，O(1)，但是数据无法按照特定规则有序  
链表：有某种顺序的数据，可以支持快遍历。  
散列表的每个节点都是双向链表

散列表节点是双向链表，链表单个节点：data，next，prev，hnext

特别指出：LinkedHashMap的结构就是上面的表结构，其中linked的含义就是双向链表

为什么散列表和链表经常一块使用？  
散列表这种数据结构支持非常高效的查找、插入和删除操作，但是存入散列表时因为hash的缘故，无法支持按照特定顺序的遍历操作。  
链表则可以保存这种顺序。

假设猎聘网有 10 万名猎头，每个猎头都可以通过做任务（比如发布职位）来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这 10 万个猎头 ID 和积分信息，让它能够支持这样几个操作：  
1）根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息；  
2）查找积分在某个区间的猎头 ID 列表；  
3）查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表；

根据id创建散列表；  
根据积分创建跳表。

Hash算法及其应用  
将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法。  
如md5算法。

hash算法的要求：  
1）快速计算  
2）hash值冲突应该小  
3）不能反向计算

hash值冲突应该小  
鸽巢原理（也叫抽屉原理）。这个原理本身很简单，它是说，如果有 10 个鸽巢，有 11 只鸽子，那肯定有 1 个鸽巢中的鸽子数量多于 1 个，换句话说就是，肯定有 2 只鸽子在 1 个鸽巢内。  
hash值结果是128位，也就是2的128次方个结果，如果是2的128次方+1个数据进行hash，必然存在重复的。

hash算法应用：  
1）安全加密：如密码，数据库中存储的是密码hash后的结果，检验密码是否正确，也是比较用户输入内容的hash结果来比较。  
2）唯一标识：  
在海量的图库中，搜索一张图是否存在，我们不能单纯地用图片的元信息（比如图片名称）来比对，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。  
我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。  
3）数据校验  
从多个机器上并行下载一个 2GB 的电影，这个电影文件可能会被分割成很多文件块（比如可以分成 100 块，每块大约 20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。网络传输是不安全的，下载的文件块有可能是被宿主机器恶意修改过的。怎么校验呢？  
通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。下载后，通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。  
4）散列函数 如应用到hashMap等中  
5）负载均衡  
通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。  
6）数据分片  
如何统计“搜索关键词”出现的次数？ 日志很多关键词很多，没办法放到一台机器中；一台机器处理数据时间会很久  
用 n 台机器并行处理。我们从搜索记录的，日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

如何快速判断图片是否在图库中？   
放到多个机器中，先hash，将图片所在每个机器中维护一个散列表，然后查找的时候也是先hash，然后到对应的表上判断是否已存在。

7）分布式存储  
假设原本有1亿数据，散列表存放于10台机器上，现在多了一台机器，怎么处理？  
如果直接修改hash逻辑，以12为例，原本存储于机器2，现在会到机器1上查找。整体可能导致雪崩的结果，压垮数据库。

合理的方式是使用一致性hash：  
k机器， hash结果为 0-M；  
每个机器负责 m/k 个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。  
这样每个机器对应的hash值都是一个区间，根据hash结果所在区间确定其所在机器；  
新加入的节点的hash值范围，可能是\[a,b\]\[c,d\]多个区间

密码如何存放安全：  
可以通过哈希算法，对用户密码进行加密之后再存储，不过最好选择相对安全的加密算法，比如 SHA 等。然后校验的时候，根据用户输入再次hash，比较两个hash值就可以认为一致。  
问题-字典攻击：  
维护一个常用密码的字典表，把字典中的每个密码用哈希算法计算哈希值，然后拿哈希值跟脱库后的密文比对。如果相同，基本上就可以认为，这个加密之后的密码对应的明文就是字典中的这个密码。  
解决：  
引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度。我们拿组合之后的字符串来做哈希算法加密，将它存储到数据库中，进一步增加破解的难度。