散列表 及其在 JDK 中的实现

语言: CN / TW / HK

哈希表在 JDK 中的演进实现

哈希表的原理

散列表Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将所需查询的数据映射到表中一个位置来供外部访问,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表

一个现实中的例子是,通讯录是一个以联系人名称首字母进行排序的表,我们可以快速定位到一个首字母上。类似索引的概念,索引的效率一般是 O(1) 的,效率非常高。

  • 若关键字为 k,则其值存放在 f(k) 的存储位置上。由此,不需比较便可直接取得所查记录。这个对应关系 f 为散列函数,按这个思想建立的表为散列表

  • 对不同的关键字可能得到同一散列地址,即 f(k1) != f(k2),而 f(k1)=f(k2) 种现象称为冲突。当存在冲突时,会将其放到同一个索引下的不同存储位置。

具有相同函数返回值的 Key 对该散列函数来说称做同义词。综上所述,根据散列函数 f(k) 理冲突的方法将一组关键字映射到一个同一个位置上,这个位置是一个有限的连续的地址集(区间)。并以 Key 为基础在这个地址集中分配一个存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。

  • 若对于关键字集合中的任一个关键字,经散列函数映射到地址集合中任何一个地址的概率是相等的,则称此类散列函数为 均匀散列函数(Uniform Hash function),这就使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

散列算法

  1. 直接定址法:取关键字或关键字的某个线性函数值为散列地址。即 hash(k)=khash(k)=a * k + b,其中 a、b 为常数(这种散列函数叫做自身函数)。
  2. 数字分析法:假设关键字是以 r 为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
  3. 平方取中法:取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
  4. 折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。
  5. 随机数法:直接取随机数。
  6. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 hash(k) = k mod p, p <= m 。不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对 p 的选择很重要,一般取素数或 m ,若 p 选择不好,容易产生冲突。

处理冲突算法

上面提到了元素通过散列函数处理好遇到冲突时,会通过一个处理冲突的方法进行处理,然后再分配到指定位置上。常见的处理算法有以下几种:

  • 开放地址法:遇到散列冲突时,往后续逐个查找空位置,将冲突对象存到第一个空位置中。
  • 单独链表法:将散列到同一个存储位置的所有元素保存在一个链表中。实现时,一种策略是散列表同一位置的所有冲突结果都是用栈存放的,新元素被插入到表的前端还是后端完全取决于怎样方便。
  • 双散列:https://zh.wikipedia.org/wiki/%E5%8F%8C%E6%95%A3%E5%88%97
  • 再散列:即在上次散列计算发生冲突时,利用该次冲突的散列函数值产生新的散列函数值,直到冲突不再发生。这种方法不易产生聚集,但增加了计算时间。

查找效率

散列表的查找过程基本上和元素添加到表中的过程相同。一些元素的 Key 可通过散列函数转换的地址直接找到,而另一些元素的 Key 在散列函数得到的地址产生了冲突,需要按处理冲突的方法进行查找。

在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与 Key 进行比较的过程。所以,对散列表查找效率的量度,依然用平均查找长度来衡量。

查找过程中,Key 的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高;产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:

  • 散列函数是否均匀
  • 处理冲突的方法
  • 散列表的载荷因子

载荷因子

散列表的载荷因子定义为:a = 填入表中的元素个数 / 散列表的长度 。

a 是散列表装满程度的标志因子。由于表长是定值,a 与“填入表中的元素个数”成正比,所以,a 越大,表明填入表中的元素越多,产生冲突的可能性就越大;反之,a 越小,标明填入表中的元素越少,产生冲突的可能性就越小。实际上,散列表的平均查找长度是载荷因子 a 的函数,只是不同处理冲突的方法有不同的函数。

在 Java 中,一般设置载荷因子为 0.75,超过此值会 resize 散列表。

为什么选择 0.75 呢?

通常,默认负载因子 (0.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销,但会增加查找条目的时间成本(这反映在大多数 Hashtable / HashMap 操作中,包括 get 和 put)。

JDK 中的哈希表结构

Hashtable

Hashtable 继承自 Dictionary 和 Map,Dictionary 接口已标记为过时,并引导使用 Map 接口进行替代。

Hashtable 是 JDK 中对散列表的实现,标准的散列表,散列算法是通过对象自身的 hashCode 取模后再用除留余数法处理。冲突处理算法是单独链表法。

它有以下特点:

  • 同步: put 、get、remove、containsKey 等操作方法都有 synchronized 修饰。

所以,他是把当前整个 Hashtable 结构进行了加锁。

  • 底层实现是数组 + 链表,不存在红黑树变种。

java // Hashtable 的 get 方法,内部是遍历链表 public synchronized V get(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; // 取模 + 除留余数 // Entry 链表结构 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return (V)e.value; } } return null; }

  • 不能存 null 值。

java public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // ... }

官方推荐,如果不需要线程安全,使用 HashMap 替代,如果需要线程安全,使用 ConcurrentHashMap 替代。基本上就是废弃的数据结构了。

HashMap

HashMap 继承自 AbstractMap 和 Map,它的操作方法没有进行同步处理,所以 HashMap 不是线程安全的。

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

这里的 putVal 是重点:

java 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; // 储存位置为空,创建一个新的节点进行保存 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 发生冲突, p 为原来已存在的 node Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 原有的元素与新的元素 key 相同,hash 值相同,直接覆盖 e = p; else if (p instanceof TreeNode) // 如果是树节点,通过 putTreeVal 处理 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); // 这里 TREEIFY_THRESHOLD = 8,当这个 bin 中的元素 >= 7 时,数据结构转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 在链表中找到了相同的元素,直接 break, 此时 e = p.next if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 因为 e = p.next, 所以这里是遍历到下一个节点 p = p.next } } // 更新找到的节点的值 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; }

在这个 put 方法中,基本上涵盖了所有的查找逻辑:

  1. 如果 HashMap 的 table 数组为空,resize 进行初始化。
  2. table 数组中的指定的存储位置为空,直接创建一个新的 Node 并保存到这里。
  3. 如果 table 中指定位置已经存在其他元素,发生冲突,分为三种情况:
  4. 原有的元素与新的元素 key 相同,hash 值相同,直接覆盖;
  5. 若此元素是一个 TreeNode 节点,是红黑树结构,通过 putTreeVal 方法进行处理。
  6. 剩下的情况开始遍历链表,遍历时进行两个步骤的处理
    1. 检查当前这个 bin 中元素数量,如果大于等于 7,调用 treeifyBin 方法进行红黑树变形。
    2. 在列表中查找到相同的元素,直接跳出遍历。
  7. 如果经过查找,能够找到已有的节点,直接覆盖成新的值。
  8. 最后检查载荷因子,判断是否需要进行 resize。

HashMap 的 get 方法内部调用的是 getNode 方法:

```java public V get(Object key) { Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; }

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

```

基本也是分为三个 case :

  • 检查第一个节点
  • 如果节点是树结构,通过 getTreeNode 去查找
  • 不是第一个节点也不是树结构,遍历链表查找

这里不管是 put 还是 set 都没有对 null 进行抛出 NPE 的处理,所以 HashMap 是可以存一个 null 的。

ConcurrentHashMap

最后是线程安全的 ConcurrentHashMap , 从名字就可以看出这是个可用于并发的 HashMap 。

它继承自 AbstractMap 并实现了 ConcurrentMap 。

它的内部数据结构和 HashMap 基本一致,不同的是,对 table 数组进行了一些同步的处理。并且不允许将 null 用作键或值。

读操作通过 CAS 和 volatile 进行处理;写操作通过 synchronized 遍历中的 node 处理,相比 Hashtable 锁整张表,大大提高了效率。

java final V putVal(K key, V value, boolean onlyIfAbsent) { // 不允许 null 为 key 或 value if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; // 空 table 进行初始化操作 if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); // 如果正在进行调整大小,则有助于传输。 else { V oldVal = null; synchronized (f) { // 加锁处理 if (tabAt(tab, i) == f) { // 存新的节点到链表中 if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } // 树结构 else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } // resize 检查 if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }