【集合】HashTable 源码分析

蔚落 2022-12-21 04:55 177阅读 0赞

# 前言 #

Github：[https://github.com/yihonglei/jdk-source-code-reading][https_github.com_yihonglei_jdk-source-code-reading]

主要分析 JDK8 版本源码。

# 一 概述 #

HashTable 是一种通过synchronized加锁实现的线程安全的散列表，散列表英文名“Hash Table”，也叫 “哈希表” 或 “hash 表”，

散列表用的是数组支持按照下标随机访问的特性，是数组的一种扩展，HashTable 使用**链表法**（chaining）解决 hash 冲突，

简单来说，就是基于数组 + 链表实现，跟 HashMap 不一样，HashMap 在 JDK8 增加了红黑树优化性能，

因为一但散列函数算的哈希值不够均匀分布，会导致数据集中在几个桶或一个桶里，退化到链表查询，

时间复杂度从理想O(1)退化到O(n)，估计是因为 HashTable 并发性较低，项目实战中很少用，所以在 JDK8

没有采用红黑树对 HashTable 进行优化，而是优化了更常用的 HashMap 和 ConcurrentHashMap。

# 二 实例 #

简单 Demo。

/**
     * synchronized 实现线程安全，并发度低
     *
     * @author yihonglei
     */
    public class HashTableTest {
        public static void main(String[] args) {
            Hashtable<String, String> hashTable = new Hashtable<>();
    
            hashTable.put("key1", "hello world!");
    
            System.out.println(hashTable.get("key1"));
        }
    }

**运行结果**

![20201130152802338.png][]

# 三 HashTable 底层实现 #

**重点分析 put() 和 get() 方法。**

## 散列表 ##

简单说下Java HashTable 散列表的数据结构，数组+链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70][]

数组是一个 Entry 对象数组，链表是一个 Entry 节点的单向链表。

## 类结构 ##

public class Hashtable<K,V>
        extends Dictionary<K,V>
        implements Map<K,V>, Cloneable, java.io.Serializable {
    
        /**
         * 存储数据的Hash表
         */
        private transient Entry<?,?>[] table;
    
        /**
         * hash表中元素个数
         */
        private transient int count;
    
        /**
         * 扩容阀值
         */
        private int threshold;
    
        /**
         * 负载因子
         */
        private float loadFactor;
    
        /**
         * 操作次数
         */
        private transient int modCount = 0;
    
        // ......
    }
    
    /**
     * Hashtable "桶"里面放的对象
     */
    private static class Entry<K,V> implements Map.Entry<K,V> {
        // hash 值
        final int hash;
        // 关键字 key
        final K key;
        // key对应的元素值
        V value;
        // 单向链表的对下一个节点的引用
        Entry<K,V> next;
    
        protected Entry(int hash, K key, V value, Entry<K,V> next) {
            this.hash = hash;
            this.key =  key;
            this.value = value;
            this.next = next;
        }
    
        // ......
    }

## 默认构造器 ##

public Hashtable() {
        // 数组容量，负载因子
        this(11, 0.75f);
    }
    
    public Hashtable(int initialCapacity, float loadFactor) {
        // 如果小于0，抛不合法异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        // 负载因子必须大于0，并且是一个 Float 浮点类型
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    
        // 如果初始容量传0个，默认变为1个
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        // 初始化散列表数组大小
        table = new Entry<?,?>[initialCapacity];
        // 扩容阀值，默认 11 * 0.75 = 8.25, 取整为8，即数组超个8个元素，则进行扩容操作，最大不能
        // 超过 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 + 1 个数组长度。
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

初始化长度为 11 的数组，负载因子为0.75。 负载因子 = 数组实际元素个数 / 数组的长度，

负载因子越大，表示散列表空闲位置越少，hash冲突也会增加，散列表的性能会下降，

合适的负载因子很重要，hashtable 默认是 0.75。

## HashTable\#put() ##

**put() 往散列表添加元素入口。**

public synchronized V put(K key, V value) {
        // value 不能为空
        if (value == null) {
            throw new NullPointerException();
        }
    
        // Entry数组
        Entry<?,?> tab[] = table;
        // key 计算 hash 值，默认用对象的 hashcode 值，如果key是一个对象，需要自己重写 hashCode()
        int hash = key.hashCode();
        // 计算 key 的 hash 值，计算数组下标位置
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        // 尝试获取index下标对应元素值
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        // 如果 entry 不为空，需要判断元素是否已经存在，如果存在，遍历链表，用新值覆盖旧值，并返回旧值
        for(; entry != null ; entry = entry.next) {
            // 如果添加的是重复元素，用新元素覆盖链表中元素，并返回旧元素
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        // 往 hashtable 添加元素
        addEntry(hash, key, value, index);
        return null;
    }

**addEntry()  往散列表添加元素实现。**

/**
     * 往 hashtable 添加元素
     */
    private void addEntry(int hash, K key, V value, int index) {
        // 链表操作次数加1
        modCount++;
        // Entry 数组
        Entry<?,?> tab[] = table;
        // 判断散列表实际元素个数是否超个阀值，超过则进行扩容操作
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();
    
            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
    
        // Creates the new entry.
        @SuppressWarnings("unchecked")
        // 获取数组里面的 Entry 节点，可能存在，也可能不存在
        Entry<K,V> e = (Entry<K,V>) tab[index];
        // 往数组里面添加元素，同时，如果 e 不为空，则通过 Entry成员属性next构建单向链表，一直在链表尾部添加节点，
        // 即新添加的元素在数组里面，作为链表的尾部节点
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

** rehash() 扩容操作。**

/**
     * 扩容操作
     */
    protected void rehash() {
        // 原散列表容量
        int oldCapacity = table.length;
        // 原散列表数据
        Entry<?,?>[] oldMap = table;
    
        // 新散列表容量 oldCapacity * 2 + 1
        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];
        // 散列表操作次数加1
        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        // 新的散列表覆盖旧的散列表
        table = newMap;
        // 循环旧的散列表，从新按照新的散列表计算hash值，每个元素重新放入新的散列表，完成扩容操作
        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;
            }
        }
    }

根据 key 计算散列值，求 index 数组下标，如果冲突了，通过链表法解决冲突。

当超过负载因子阀值，数组长度扩容为原来的两倍。

## HashTable\#get() ##

public synchronized V get(Object key) {
        // 散列表
        Entry<?,?> tab[] = table;
        // 计算 hash 值
        int hash = key.hashCode();
        // 计算数组下标位置
        int index = (hash & 0x7FFFFFFF) % tab.length;
        // 循环获取对应key的value值
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

get 过程比较简单，找到对应 hash 位置，找到对应的 key，返回相应的 value。

# 四 总结 #

1、HashTable 通过 synchronized 实现线程安全的散列表，基于数组 + 链表法实现；

2、并发性较低，实战用的少，实战中非线程安全一般用 HashMap，线程安全并发度高一般用 ConcurrentHashMap；

[https_github.com_yihonglei_jdk-source-code-reading]: https://github.com/yihonglei/jdk-source-code-reading
[20201130152802338.png]: /images/20221120/a78df380f88b40bb84e0e00a89375c60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70]: /images/20221120/3f37550ba46d4c27ba33d37d280b2ce2.png