Map接口的古老实现,详解线程安全的HashTable

1 概述

  • HashTable继承自抽象类Dictionary, 并实现了Map接口,实际上,Map接口就是用来代替Dictionary
  • 是一个线程安全的Map
  • key和value均不允许为null
  • 为了正确使用Hashtable存取key-value对,用作key的类必须实现hashcode()和equals()方法
  • 初始化用的 initial capacity 和 load factory(默认为0.75) 会影响HashTable的性能

2 底层实现

  • 五个私有变量
    • transient Entry[] table HashTable实际维护的容器,一个Entry数组
    • transient int count 容器存储key-value对的总数
    • int threshold 扩容标志, 当容器的size()大于这个值时,会进行rehash操作——扩容并重新组织table
    • float loadFactor 扩容因子,扩容相关
    • transient int modCount = 0 一个标志,每次修改容器内容modCount就会自增,主要用于遍历时判断是否容器是否在被其他对象修改, 如果modeCount在遍历时发生变化,就会抛出异常
  • 初始化
    • 基本的构造器HashTable(int initialCapacity, float loadFactor),
      table实际是HashTable里一个静态私有类Entry<K, V>数组,Entry<K, V> 实现了Map.Entry<K, V> 接口
public Hashtable(int initialCapacity, float loadFactor) { // 1. 判断参数是否合法 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load: "+loadFactor); // 2. 如果传入的初始容量为 0 时,设为 1 if (initialCapacity==0) initialCapacity = 1; this.loadFactor = loadFactor; // 3. 开辟一个初始容量为 initialCapacity的数组 table = new Entry<?,?>[initialCapacity]; // 计算触发扩容的容量 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); }
  • HashTable(int initialCapacity) 默认 loadFactory 为 0.75
  • HashTable() 默认 initialCapacity 为 11, loadFactory 为 0.75
  • HashTable(Map map) 默认 initialCapacity 为 max(2*map.size(),11), loadFactory 为0.75
  • 静态私有类 Entry<K, V>,不难看出实际上这是一个单向链表
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; } // 其他实现 Map.Entry<K, V>接口的代码 }
  • put(key, value)方法
public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; // hash & 0x7FFFFFFF 保证了index不会是负数 @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { // 遍历链表, 查看是否已存在相同的key, hash相等,且 equals 返回true if ((entry.hash == hash) && entry.key.equals(key)) { // 匹配到相同的key,替换value,并返回原value V old = entry.value; entry.value = value; return old; } } // 不存在这个key,直接添加,并返回null addEntry(hash, key, value, index); return null; } private void addEntry(int hash, K key, V value, int index) { Entry<?,?> tab[] = table; // 首先查看容量是否符合扩容的要求 if (count >= threshold) { // Rehash the table if the threshold is exceeded // 调用rehash方法, 并重新组织table rehash(); tab = table; hash = key.hashCode(); // 因为扩容了, 所以需要重新计算 index index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; // 把新的Entry设置为单向链表的开始节点 tab[index] = new Entry<>(hash, key, value, e); count++; modCount++; }
  • 扩容算法 rehash()
protected void rehash() { int oldCapacity = table.length; Entry<?,?>[] oldMap = table; /** *确定新容量 * 1. 假定newCapactity = oldCapacity * 2 + 1 * 2. 如果假定的newCapacity大于数组允的许最大长度Integer.MAX_VALUE-8, * a. 如果原长oldCapacity等于允许的最大长度, 无法扩容了, 跳出该方法不进行扩容 * b. 日过不相等,直接将扩容目标值设置为数组允许的最大长度 */ // 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 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; // 将已有的key-value对放到新的数组中,完成扩容 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; } } }
  • get(Object key) 实际上就是put(key,value)中的一段
public synchronized V get(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 (V)e.value; } } return null; }

3 总结

  • HashTable的主要方法都使用synchronized关键字修饰来保证其线程安全
  • 底层使用哈希表实现
  • 因为有 HashMap 和 ConcurrentMap的存在,被用得很少,但是我们常用的Properties类是通过继承HashTable来实现的
阅读(58)
评论(0)
updated@2020-11-02
评论区
目录