HashTable 有什么奇怪的知识?

本文涉及的源码基于 JDK 1.8.0_101 。

1. HashTable

  1. 采用数组 + 链表(表头插入)方式解决哈希冲突。
  2. 所有的 public 方法都用 synchronized 修饰以保证线程安全。
  3. 在构造时就初始化槽数组(默认大小为 11)。
  4. 键、值 都不能为 null
  5. 指定 key 的目标槽的定位逻辑:(key.hashCode() & 0x7FFFFFFF) % table.length,掩码+求模。
  6. 槽数组的最大尺寸为 MAX_ARRAY_SIZE: Integer.MAX_VALUE - 8(减 8 是因为一些 JVM 会在数组里保留一些 header words)。
  7. 扩容逻辑为 两倍 + 1。
  8. 阈值为: (int)(capacity * loadFactor),但不能超过 MAX_ARRAY_SIZE + 1

1.1 put 方法逻辑

  1. 通过 key 计算出目标槽位 index ;
  2. 遍历 table[index] 链表,如果 key 存在,则替换 value,返回前值。
  3. 如果 key 不存在,继续。
  4. 判断元素数量是否达到阈值,达到的话进行扩容 rehash,然后重新计算目标槽位 index。
  5. 创建新的 Entry,把 Entry 插入到链表的头部。

1.2 rehash 逻辑

  1. 数组扩容至 oldCapacity * 2 + 1,但不能超过 MAX_ARRAY_SIZE 。
  2. 把旧 map 上的元素转移到新的 map:逐个槽位、逐个链表遍历 。
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

1.3 get 方法

  1. 计算 key 的目标槽位 index;
  2. 遍历 table[index] 上的链表以查找 key,找到返回 value、找不到返回 null 。

1.4 remove 方法

  1. 计算 key 的目标槽位 index;
  2. 遍历 table[index] 上的链表查找 key,初始化前驱 prev 为 null,找到 key 的 entry e 后,如果 prev 不为 null 则设置 prev.next = e.next,否则说明 e 就在链表的头部,设置 table[index] = e.next

欢迎关注我的微信公众号: coderbee笔记

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据