散列表(一)

发表于   |   更新于 | | 阅读数
字数统计 4k 字 | 阅读时长 14 分钟

散列表

概念:

  • 我们知道数组中的数据存放在指定下标位置，预先知道下标，可以直接访问到该数据。而散列表也是基于数组的随机访问特性，根据需要存储的数据的键(key)，使用特定的散列函数(hash(key))计算出该键值对应存储的下标位置

  • 散列函数可以联想一下HashMap的hash函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

//hash函数
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//put方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//内部的putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //调用hash函数的结果值和length-1进行与操作
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

  • 在HashMap中存放元素时，需要先通过hash函数确定元素的key映射出来的下标位置，JDK1.8中HashMap的hash函数是通过 key 的hashCode 和自身右移16位之后的值进行异或 ， 得出一个新的hashCode作为key对应的下标位置

  • 将 key.hashCode()的值和自身右移16位进行异或，也就是将自身的高位和低位进行异或运算(相同为1，不同为0)，加大低位的随机性

  • 在HashMap的put方法中，计算下标位置还需要 (n - 1) & hash 的运算过程，这里也可以顺便解释一下为什么HashMap的容量要求为2的倍数：

    不论HashMap的最终容量是多大，为2的倍数说明至少是2，n-1 转化成二进制数1位大幅增加(1000 -> 0111) ，和计算出来的 hash 进行与运算，则运算后的最低位的值会由hashCode的低位的值决定，也增加了最终确定的存储位置的随机性

散列函数

  1. 从上面的例子可以看出散列函数的十分重要，设计优良的散列函数可以确保对于不同的key尽量计算出不同的hash值用来代表不同的存储位置

  2. 散列函数有三点要求:

    1. has(key) > 0
    2. if key1 == key2 , hash(key1) == hash(key2)
    3. if key1 != key2 , hash(key1) != hash(key2)

  3. 其实从散列函数的作用来看（将key映射为在数组中的存储位置），对于这三点要求比较好理解：

    1. 数组中存储位置 > 0
    2. 相同的键存储在同一位置，可以确保再次通过hash(key)可以定位到该元素
    3. 不同的键hash(key)的值不同，避免不同的key存储位置冲突

  4. 不过对于第三点是没有办法绝对保证的，假设数组容量很有限，插入过多数据最终hash出来的结果一定会发生散列冲突，解决散列冲突的方式通常有：开放寻址，链表法，选择哈希，参考WIKI的 Collision resolution

    1. 开放寻址(Open Addressing) ：
      1. 哈希表中所有的数据都存储在单独的hash桶中，当插入一个新数据，hash函数映射到一个已经存在数据的桶时，会以该桶为起点继续向后查找空的桶存储数据；
      2. 搜索一个数据也是一样：扫描所有的桶，定位到存储该key的hash值的桶时表明数据存在，否则表明数据不存在该hash表中
      3. 开放寻址的意思是：元素的存储位置不再由hash值决定(因为已经冲突了)
      4. 开放寻址由三种常用的方法：线性探测，二次探测和双重hash：
        1. 线性探测(Linear probing) : 以固定的的步长( 通常是1 )探测空余的插入位置，由于对CPU缓存的优良利用率和高效的算法表现，这种方式被广泛应用在现代计算机架构的hash表实现中
        2. 二次探测(Quadratic probing)：以连续增加步长的方式探测，通过将二次多项式的连续输出与给定的起始值相加来增加探针之间的间隔，也就是hash(key) + 0 , hash(key)+1^2 ,hash(key) + 2^2 这种递增的方式进行探测
        3. 双重哈希 (Double Hashing)：探测的间隔位置由另一个hash方法决定
      5. 缺陷：
        1. 这些开放寻址的缺点是存储的元素不能超过桶的数量( 如果存储了超过桶数量的数据，意味着哈希碰撞一定会发生，而且还得考虑扩容 )
        2. 除此之外，开放寻址方法除了要求hash算法将key值均匀地分散在桶中，还要求最小化按线性探测顺序的hash值的聚集 — 我对这句话的理解是，反过来思考，假设存在多次hash碰撞导致线性探测，每次探测结果都刚好落在连续的hash值之后，会导致后续因为hash碰撞而需要进行探测的时间消耗线性增长 — 也就是说要求数据分布均匀且hash碰撞的情况下，保证线性探测不会消耗太多的时间
        3. 而在链表法中，唯一需要关心的就是太多的key 哈希到了同一个位置（会导致该位置的拉链边长，数据结构从散列表退化成单链表，性能优势丧失）
      6. 实际上，即便是设计优良的hash算法，在容器的负载因子超过0.7的时候，使用性能都会下降。在很多hash的应用场景中，0.7 的负载因子默认作为了动态扩容的依据（例如JAVA HashMap 的 0.75）

    1. 链表法(Spearate chaining) : 直译是分离链表

      1. 如同名称所代表的含义那样：链表结构的hash表中，每个桶都是独立的，各自维护一条有序的数据集合，在其中查找一个数据的时间 = 查找桶的时间 + 查找桶中元素的时间

      2. 最理想的情况下，每个桶中的元素基本是12个，有时候是34个，但是不会更多，在这种分布方式下，数据结构具备十分优良的时间，空间性能表现，如果不符合这种情况，hash算法可能需要修正

      3. 链表法有几种实现方式：使用链表存储桶数据，仅存储链头节点，使用其他数据结构存储桶数据

        1. 使用链表存储桶数据：

          1. 即在每一个桶中维护一条完整的链表，因为链表本身应用的算法比较简单(插入，删除，遍历)，而且链表可以使用比较简单的hash算法(开放寻址要求存储的元素不能超过桶插槽的数量)，因此这种实现方式比较流行

          2. 在这种结构中的时间消耗，基本上就是在的指定的链表中操作的时间消耗。而且在数据在桶中分布足够均匀的情况下—每个桶的链长度相近—在散列表中查找元素的平均时间消耗仅仅取决于每个桶的元素数量，恰好与负载因子成正比

          3. 基于以上两点，链式桶结构的散列表即便存储了大大超过桶数量的数据，仍然比普通的有序列表高效。

          4. 对于链式桶结构的散列表来说，最坏的情况是所有的key都hash到了同一个桶，这意味着散列表会退化成链表结构，也就不存在性能优势，因为几乎要遍历整条链表

          5. 通常链式桶都是依据数据存储的顺序进行查找定位，当负载因子很大而且某些key的访问频率明显高于其他key时，通过 Move to front method 方式进行链表的重新排序会提高遍历的效率 。在某些更加复杂的数据结构中，例如平衡查找树，只需要在负载因子极大或者数据分布及其不均匀又或者即便在数据分配不均匀的情况下好需要保证操作的性能，才考虑进行数据的重排序。实际上通过散列表扩容或者使用更加优良的hash函数也能满足这些需求。

            1. Move to front method (MTF) :

              将已访问的元素移动至列表头部的一种方式。这种方式比较易于实现而且不要求额外的内存空间，很能适应在查询操作中快速变化。

              从另一方面来说，这种方式也可能将不常访问的数据移动到列表的头部，例如只被访问了一次的数据，这种情况下对这个数据的过分照顾就会破坏列表的最佳排序并且增加查找其他元素的时间消耗。

              另一个缺点就是由于这种快速的变更存储顺序，即便是访问列表中的不常用元素，也能立刻破坏列表本身的最佳排序状态

          6. 当然这种链式散列表也继承了链表本身的缺点：

            1. 当存储的key和value都很小的时候，它们所携带的指针内存开销反而是最大的
            2. 另一个缺点就是遍历链表的性能表现是比较差的，缓存不友好(链表内存空间不连续) （参考维基百科访问局部性）

        2. 仅存储链表头节点：这里的头节点是实际意义的业务数据，不是哨兵节点

          1. 和存储整条链表不同，仅存储每条链表的第一个节点(对象)（存储整条链表时桶里最先存储的是第一个节点的引用），因此在大部分场景下需要遍历的指针数量减少至1。而且存储对象本身的信息而不是指针，可以有效利用CPU缓存机制
          2. 缺点就是空桶也会占用和存储了一个对象的桶一样的存储空间（数组的特性？），为了节省内存空间，这种类型的散列表几乎含有和存储数据一样多的桶数量，意味着每个桶至少包含了两个对象数据

        3. 使用其他数据结构代替链表：

          1. 常见的是自平衡二叉查找树，拥有和散列表一样的优秀的性能表现，就是实现起来比较复杂，而且在数据量比较小的散列表中使用时，在树中插入数据和将自身平衡的时间消耗甚至会超过在线性表中的操作时间，以这种方式实现的一个例子是 JDK1.8的HashMap

  5. 从这些情况来考虑实现一个比较完美的散列函数还是比较困难，散列表属于动态的数据结构，随着数据不断添加，发生碰撞的可能性也会增加，因此还得考虑如何实现动态扩容。在散列表中**负载因子(load factory)**作为扩容依据，根据不同的散列表存储结构，选择的负载因子也是不一样的；

    1. 在使用开放寻址的方式解决哈希冲突的方案中，负载因子尽可能不超过1，也就是存储的元素不能超过的桶的数量，才能保证数据均匀分配的可能性
    2. 而在链表法解决哈希冲突的方案中，因为链表结构本身的结构比较简单，尤其是在插入删除的场景，复杂度较低；而链表法的遍历低效，可以通过将链表结构转化成树结构来解决；因此负载因子即便大大超过桶的数量，也比同等数量的线性表高效

动态扩容

  1. 散列函数影响数据的分布，当数据分布均匀但是数据量和桶数量的比例过大时，需要动态扩容，避免哈希冲突时增加插入数据的时间消耗
  2. 给散列表预先定义一个负载因子作为扩容的标准，负载因子 = 数据的个数/桶的数量 ， 当这个比例超过一定值(例如JDK 的HashMap是0.75)，进行散列表的扩容；因为散列表单纯的遍历，插入和删除已经是高效实现了，但是如果插入数据时碰上需要先扩容再进行插入的情况，时间复杂度就会因此而提高，对n长的散列表进行扩容复制桶数据，时间复杂度是O(n)
  3. 避免低效扩容就得考虑非一次性扩容的方案，也就是将扩容操作分散，避免某次插入的等待，这种思路和前面数组的数据删除有点类似：数组的数据删除为了避免每次删除都进行数据移动，都是先对要删除的数据进行标记，当插入数据发现空间不足时进行一次整体的数据删除
  4. 因此在动态扩容的操作中，当负载因子超过阈值，可以定义两倍( 或者指定的扩容倍数 )长的散列表接收新插入的数据，并且每次插入时从旧散列表中复制一个数据重新进行哈希插入到新散列表，这样n长的散列表负载因子为0.75的话，在0.75*n 次的新数据插入之后，整个散列表的扩容也就完成了；但是这里还得注意：当使用两个散列表存储数据，数据的查找就得考虑遍历两个散列表

小结：

  1. 散列表是通过散列函数将不同长度的键值映射成固定长度的值作为索引位置存储的数据结构，因此散列函数的实现十分重要，设计优良的散列函数，可以最大程度保证数据均匀分布，确保散列表的高效操作
  2. 散列冲突是不避免的，当存储的数据量超过了散列表中桶的数量，那么必定有一个桶需要存储超过一个数据，这也就会导致散列冲突；解决这种情况下的散列冲突要么是提前扩容，要么使用链表或者其他数据结构存储桶中的数据，后者在数据结构的选择上要求选择的数据结构，在存储了远超过桶数量的的数据时，依旧具有高效的表现
  3. 散列表本身的操作效率比较高，但是当碰到需要扩容的情况时，如果散列表本身的数据量已经足够大，需要对全部数据重新计算哈希决定分配位置是比较耗时的操作；因此可以考虑将一次性扩容的操作分散到每一次的数据插入中：当到达扩容的临界点，创建指定大小的新散列表，每一次新数据都插入新散列表中，并且从旧散列表移动一个数据到新的散列表，这样n次数据插入之后，旧散列表中的数据也就全部移动到了新散列表，完成了扩容