好玩的网站列表

1. Intro

散列表 - Hash Table, 又被称为哈希表或者Hash表。散列表用的是数组支持按照下标来随机访问数据的特性，因此散列表实际上是数组的一种扩展，由数组演化而来。

散列的思想就是对于key值，通过hash function，对应到table上来进行存储

2. 散列函数

散列函数就是实现输入到存储的对应的函数，因为最终是要存储到数组当中，故而其基本要求有：

1. 散列函数计算得到的散列值是一个非负整数
2. 如果Key1 = Key2,那么hash(key1) == hash(key2)
3. 如果key1 != key2, 那么hash(key1) != hash(key2)

条件3 即如何应对散列冲突的问题，首先本身是必须的，而且客观是存在散列冲突的情况的，针对于散列冲突，我们一般会使用开放寻址法和链表法。

3. 如何解决散列冲突

3.1 开放寻址法

• 核心思想
  • 出现了散列冲突，就重新探测一个空闲位置，将其插入
• 探测方法
  • 线性探测
  • 二次探测
    • 探测步长为二次方的增长
  • 双重散列
    • 使用第一个散列函数进行尝试
    • 如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推直到找到空闲的存储位置
• 装载因子
  • 引入装在引资的概念来表示空位的多少
  • 装载因子 = 填入表中的元素个数/散列表的长度

3.2 链表法

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。我们来看这个图，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

4. 工程上使用的散列表

首先我们需要思考下实际应用场景当中的散列表，虽然我们说散列表的查询效率是O(1), 实质上他的真实数据时和散列函数，装载因子，散列冲突都有关系的。如果散列函数设计的不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，从而导致查询的效率下降。

因此对于在工程上使用的散列表，首先要考虑的就是需要能够应对各种异常情况，来避免散列冲突的情况下散列表性能的急剧下降，并且需要能够抵抗散列碰撞攻击。

4.1 如何设计散列函数

• 需求
  • 散列函数的设计不能太复杂
    • 会消耗很多计算时间
    • 即会影响到散列表的性能
  • 散列函数生成的值需要尽可能随机并且均匀分布
• 如何解决装载因子过大的问题
  • 针对散列表，当装载因子过大的时候，我们也可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到这个新的散列表当中。
  • 同时也有装载因子太小的情况下，我们可以做动态缩容的工作
• 如何避免低效扩容
  • 所谓低效的扩容指的是如果我们在装载因子超过阈值的时候一下子进行扩容，即数据的搬运和最终的新数据的插入，那针对这一个数据，其时间复杂度变成了O(n).
  • 为了解决这个问题，我们在需要进行扩容的时候，将扩容的操作穿插在插入操作的过程当中，分批次来完成。当装载因子触达阈值的时候，只申请新空间，但是没有将老的数据搬移到新的散列表当中。
  • 当有新数据插入的时候，就将新数据放到新的散列表当中，并且从老的散列表当中拿一个数据放到新的散列表当中
  • 而查询操作，为了兼顾，我们会先从新的散列表当中查找，如果没有找到，再去老的散列表当中查找

4.2 如何解决冲突？

4.2.1 开放寻址法

• 优势
  • 数据都存储在数组当中，可以有效利用CPU缓存加快查询速度
  • 序列化比较简单
• 缺陷
  • 删除数据比较麻烦，需要特殊标记已经删除的数据
  • 冲突代价高，导致装载因子的上限不能太大

当数据量比较小，装载因子小的时候，适合使用开放寻址法。

4.2.2 链表法

• 优势
  • 对内存的利用率相对比较高，因为链表结点可以在需要的时候再创建，不需要提前申请好
  • 可以允许很高的装载因子
• 劣势
  • 因为要存储指针，对于小的对象的存储，是更加耗内存的
  • 因为结点零散分布在内存当中，不是连续的，所以对CPU缓存不友好，对执行效率会造成一定的影响

4.3 Java HashMap举例

• 初始大小 - 16
  • 如果大概知道数据量的大小，可以修改默认，来减少动态扩容的次数
• 装载因子和动态扩容
  • 默认 load factor 0.75
  • 每次扩容大小变为两倍
• 散列冲突解决方法
  • 采用链表法
  • 1.8以后当链表长度超过8以后，链表就会自动转化为红黑树
• 散列函数

int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
} 

&(capacity - 1) means % capacity

因为hashcode本身是个32位的整型值，获得其hash值以后，将高16位移到低16位，就相当于拿到了高16位和低16位的feature。用自己的高半区和低半区做异或，为的是加大低位的随机性。这样子哪怕是高位的变化也可以反映到低位当中，保证了最终进bin的随机性

5. 散列表实际应用

散列表和链表经常是共同使用的,这一部分会walk through一些常用的场景，看看是如何来共同使用的。

5.1 LRU缓存淘汰算法

最基础的LRU实现，我们可以通过链表来做.维护一个按照访问时间从大到小有序排列的链表结构，因为缓存大小有限，当缓存空间不够，需要淘汰一个数据的时候，我们就直接将链表头部的结点删除。

我们可以选择使用散列表和双向链表一起来实现LRU cache。要实现的操作有：

• 往缓存中加入数据
• 从缓存中删除数据
• 在缓存中查找数据

如图所示，我们相当于在维护两条链表，一条是在哈希表的每个entry上的链，在这上面的链是为了解决哈希冲突的；另外一个点，我们在使用的是维护LRU cache的链表。

链表当中的每个结点保存了：

• prev
• next
• data
• hnext
  • 散列表上碰撞问题的解决的

5.2 Java LinkedHashMap

LinkedHashMap能够实现按照数据的插入顺序来进行打印，是因为他也是通过散列表和链表组合在一起的方式实现的。它支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据

// 10是初始大小，0.75是装载因子，true是表示按照访问时间排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);

m.put(3, 26);
m.get(5);

for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());
}
// print out: 1, 2, 3, 5

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com