Java 集合框架系列十五：JDK 1.8 Hashtable 详解

港控/mmm° 2022-12-04 07:56 266阅读 0赞

## Hashtable 继承关系 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]  
Hashtable 是 JDK 1.0 提供的类，继承了 Dictionary 类，Dictionary 类现在已经标记为过时了，Hashtable 实现了 Map 接口，这是在 JDK 1.2 时改动的，还实现了 Cloneable 和 Serializable 接口，Hashtable 默认支持浅拷贝、序列化与反序列化。具体的实现可以查看 Hashtable 的 clone()、writeObject()、readObject() 方法。

public class Hashtable<K,V> extends Dictionary<K,V>
        implements Map<K,V>, Cloneable, java.io.Serializable { 
    }

通过阅读 Hashtable 的类文档可以得到如下信息：

1.  Hashtable 是一个哈希表的实现，将 key-value 已键值对的形式存储，不允许 key 和 value 为 null。Hashtable 要求存储的 key 对象必须实现了 hashCode 方法和 equals 方法。
2.  影响 Hashtable 性能的参数有两个：初始容量和负载因子。初始容量就是创建 Hashtable 时哈希桶的数量，初始容量不应该设置过高，否则可能会浪费空间，因为哈希桶实际就是数组，数组是一块连续的内存，开辟了内存空间但是没有使用就是浪费，如果确定需要存储大量元素，建议使用足够大的初始容量创建 Hashtable 避免后续频繁扩容。负载因子是度量哈希桶扩容需要达到的程度。默认的负载因子是 0.75，是在时间和空间成本之间的折衷。较高的负载因子会减少空间开销但是降低查找的性能，因为哈希冲突的概率增加。
3.  Hashtable 的 keys 和 elements 返回的枚举不是 fail-fast 策略的。
4.  Hashtable 是同步的实现，如果需要使用非线程安全实现建议使用 HashMap，如果需要使用线程安全实现建议使用 ConcurrentHashMap。

## Hashtable API ##

### 静态常量 ###

// 最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

### 成员变量 ###

// 哈希桶 是 Entry[] 数组
        private transient Entry<?,?>[] table;
    
        // key-value 键值对的数量
        private transient int count;
    
        // 触发 rehash（扩容） 的阈值 = (int)(capacity * loadFactor)
        private int threshold;
    
        // 负载因子
        private float loadFactor;
    
        // 结构修改次数
        private transient int modCount = 0;

### 单链表数据结构 ###

Hashtable 底层使用的 Entry\[\] 数组存储键值对，也把 Entry\[\] 叫做哈希桶，一个 Entry 存储了 key 和 value 映射，且包含一个指向下个 Entry 的 next 引用，可见这是一个单链表。

private static class Entry<K,V> implements Map.Entry<K,V> { 
            final int hash;
            final K 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;
            }
    }

### 构造方法 ###

// 使用默认的初始容量 11 和默认的负载因子 0.75
    	public Hashtable() { 
            this(11, 0.75f);
        }
    	// 自定义初始容量和使用默认的负载因子 0.75
    	public Hashtable(int initialCapacity) { 
            this(initialCapacity, 0.75f);
        }
    	// 自定义初始容量和负载因子
    	public Hashtable(int initialCapacity, float loadFactor) { 
    	    // 有效性检查
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    	    // 如果初始容量是 0 设置初始容量是 1 
            if (initialCapacity==0)
                initialCapacity = 1;
            // 设置负载因子
            this.loadFactor = loadFactor;
            // 初始化 table[] 
            table = new Entry<?,?>[initialCapacity];
            // 计算阈值 initialCapacity * loadFactor 和 MAX_ARRAY_SIZE + 1 选择最小值
            threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        }
    	// JDK 1.2 提供的构造方法 如果 t 是 null 抛出 NullPointerException
        public Hashtable(Map<? extends K, ? extends V> t) { 
            // 在 11 和 2 倍的 Map t 的数量中选择一个最大值作为初始容量
            // 使用默认的负载因子 0.75
            this(Math.max(2*t.size(), 11), 0.75f);
            // 把 Map t 中的元素添加到当前 Hashtable 中
            putAll(t);
        }
    		
    	public synchronized void putAll(Map<? extends K, ? extends V> t) { 
    	    // 遍历 entrySet
            for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
                // 调 put(K key, V value) 方法
                put(e.getKey(), e.getValue());
        }

### put(K key, V value) ###

public synchronized V put(K key, V value) { 
            // value 不能为 null
            if (value == null) { 
                throw new NullPointerException();
            }
    
            // tab 表示当前 table[] 数组
            Entry<?,?> tab[] = table;
            // 如果 key 为 null 此处会抛出 NullPointerException
            int hash = key.hashCode();
            // 计算在 table[] 中的索引位 
            // 0x7FFFFFFF 就是 Integer 的最大值
            // 0x7FFFFFFF 用来处理 hash 是负数的情况 负数的二进制标志是最高位，则和 0x7FFFFFFF 做与操作即将负数变成正数
            // 对当前容量进行取模运算得到索引位
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            // 定位到 index 位置
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            // 遍历链表判断是否存在相同的 key 存在则需要覆盖并返回旧的 value
            // tab[index] 必须已存在元素
            for(; entry != null ; entry = entry.next) { 
                if ((entry.hash == hash) && entry.key.equals(key)) { 
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
    		// 插入新的节点
            addEntry(hash, key, value, index);
            return null;
        }
    	
    	private void addEntry(int hash, K key, V value, int index) { 
         	// 结构修改次数 + 1
            modCount++;
    		// 代表当前 table[]
            Entry<?,?> tab[] = table;
            // 如果插入新元素之前元素数量 >= 阈值
            if (count >= threshold) { 
                // 扩容
                rehash();
    			// 更新 tab 为当前的 table[]
                tab = table;
                hash = key.hashCode();
                // 定位新的索引位
                index = (hash & 0x7FFFFFFF) % tab.length;
            }
    
            // Creates the new entry.
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) tab[index];
            // 这里 e 一定存在，将新元素插入到链表头节点，e 元素作为当前元素的 next 节点
            // 头插法 ，避免迭代浪费性能
            tab[index] = new Entry<>(hash, key, value, e);
            // 数量 + 1
            count++;
        }
    	// 扩容
    	protected void rehash() { 
    	    // 旧容量
            int oldCapacity = table.length;
            // 旧哈希桶
            Entry<?,?>[] oldMap = table;
    
            // 新容量 = 2 倍的旧容量 + 1
            int newCapacity = (oldCapacity << 1) + 1;
            // 边界控制
            if (newCapacity - MAX_ARRAY_SIZE > 0) { 
                // 如果旧容量达到了 MAX_ARRAY_SIZE 则保持不变
                if (oldCapacity == MAX_ARRAY_SIZE)
                    return;
                newCapacity = MAX_ARRAY_SIZE;
            }
            // 创建一个新的哈希桶
            Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    		// 结构修改 + 1
            modCount++;
            // 计算新的阈值
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            // table引用指向新的哈希桶
            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 = null
                    e.next =1 (Entry<K,V>)newMap[index];
                    // index 索引位引用指向 e
                    newMap[index] = e;
                }
            }
        }

### putIfAbsent(K key, V value) ###

// 重新 Map 的默认方法
        // 如果 key 不存在才插入，不能覆盖
    	@Override
        public synchronized V putIfAbsent(K key, V value) { 
            Objects.requireNonNull(value);
    
            // Makes sure the key is not already in the hashtable.
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            for (; entry != null; entry = entry.next) { 
                if ((entry.hash == hash) && entry.key.equals(key)) { 
                    V old = entry.value;
                    // 只有 old value 是 null才会进行覆盖操作，但是 Hashtable 是不允许 null value 的
                    // 所以此方法只支持插入新的 key value
                    if (old == null) { 
                        entry.value = value;
                    }
                    return old;
                }
            }
    
            addEntry(hash, key, value, index);
            return null;
        }

### remove(Object key) ###

public synchronized V remove(Object key) { 
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            // 计算索引位
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            // 定位到索引位 e 是链表的头节点
            Entry<K,V> e = (Entry<K,V>)tab[index];
            // prev 代表前一个节点 e 代表当前节点
            for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { 
                // 如果找到了节点
                if ((e.hash == hash) && e.key.equals(key)) { 
                    // 结构修改 + 1
                    modCount++;
                    // e 不是链表的头节点
                    if (prev != null) { 
                        prev.next = e.next;
                    } else { 
                        // 将 e.next 变为头节点
                        tab[index] = e.next;
                    }
                    // 元素数量 - 1
                    count--;
                    // 旧值
                    V oldValue = e.value;
                    // gc
                    e.value = null;
                    return oldValue;
                }
            }
            return null;
        }

### clear() ###

public synchronized void clear() { 
            Entry<?,?> tab[] = table;
            // 结构修改 + 1
            modCount++;
            for (int index = tab.length; --index >= 0; )
                // 数组每个元素设置为 null
                tab[index] = null;
            // 元素数量为 0 
            count = 0;
        }

### contains(Object value) ###

public synchronized boolean contains(Object value) { 
    	    // value 不允许 null
            if (value == null) { 
                throw new NullPointerException();
            }
    	
            Entry<?,?> tab[] = table;
            // 倒序遍历 table 数组
            for (int i = tab.length ; i-- > 0 ;) { 
                // 遍历链表
                for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) { 
                    if (e.value.equals(value)) { 
                        return true;
                    }
                }
            }
            return false;
        }

### containsValue(Object value) ###

// 相当于调 contains 方法
    	public boolean containsValue(Object value) { 
    	    // 调 contains 方法判断
            return contains(value);
        }

### containsKey(Object key) ###

public synchronized boolean containsKey(Object key) { 
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            // 定位到索引位
            int index = (hash & 0x7FFFFFFF) % tab.length;
            // 遍历链表
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 
                if ((e.hash == hash) && e.key.equals(key)) { 
                    return true;
                }
            }
            return false;
        }

### 迭代器 ###

Hashtable 是通过 Enumeration 进行迭代的，无论是重写的 Dictionary 类的 keys 和 elements 方法。

public synchronized Enumeration<K> keys() { 
            return this.<K>getEnumeration(KEYS);
        }		
    		
    	public synchronized Enumeration<V> elements() { 
            return this.<V>getEnumeration(VALUES);
        }
    	
    	private <T> Enumeration<T> getEnumeration(int type) { 
            if (count == 0) { 
                return Collections.emptyEnumeration();
            } else { 
                return new Enumerator<>(type, false);
            }
        }

还是 JDK 1.2 后实现 Map 定义的 keySet、values、entrySet 方法。都是返回的 Enumerator。

public Set<K> keySet() { 
            if (keySet == null)
                keySet = Collections.synchronizedSet(new KeySet(), this);
            return keySet;
        }
        private class KeySet extends AbstractSet<K> { 
            public Iterator<K> iterator() { 
                return getIterator(KEYS);
            }
        }
    	
    	public Collection<V> values() { 
            if (values==null)
                values = Collections.synchronizedCollection(new ValueCollection(),
                                                            this);
            return values;
        }
    
        private class ValueCollection extends AbstractCollection<V> { 
            public Iterator<V> iterator() { 
                return getIterator(VALUES);
            }
        }
    	
    	public Set<Map.Entry<K,V>> entrySet() { 
            if (entrySet==null)
                entrySet = Collections.synchronizedSet(new EntrySet(), this);
            return entrySet;
        }
    
        private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 
            public Iterator<Map.Entry<K,V>> iterator() { 
                return getIterator(ENTRIES);
            }
    	}        
    	
    	private <T> Iterator<T> getIterator(int type) { 
            if (count == 0) { 
                return Collections.emptyIterator();
            } else { 
                return new Enumerator<>(type, true);
            }
        }

KEYS、VALUES、ENTRIES 是 Hashtable 的静态常量。

private static final int KEYS = 0;
        private static final int VALUES = 1;
        private static final int ENTRIES = 2;

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/cf02112afe4d40f99c8de79323873671.png