《Java源码解析》集合框架Map之HashTable

超、凢脫俗 2022-07-13 04:11 197阅读 0赞

时间：2016-12-24 11:01

> 今天是2017届研究生入学考试第一天，虽然已经与我没什么关系，但还是会想去去年入学考试的今天，往事已随风逝去，具体的2016生活与技术的总结还是写一个专门的博客吧。难得的周六，难得的早起，陪着2017的考生一起吧，所以也早起写了一片博客，时间也差不多刚刚好吧，算是提前交卷了。

Hashtable类的实现也是基于“数组和链表”来实现的，这个HashMap是一样的。

# HashTable #

## 1. HashTable的继承体系 ##

![HashTable的继承体系][HashTable]

HashMap主要是继承自Dictionary，实现了Cloneable和Serializable接口使得HashMap具有克隆和序列化的功能、实现了Map接口因此具有Map的性质。

> 注意：这也是Hashtable和HashMap第一个不同的地方，HashMap实现的是AbstractMap类。

## 2.HashTable的重要属性 ##

//存储键值对的table数组
        private transient Entry<K,V>[] table;
        //数组中已存数据的容量
        private transient int count;
        //table扩容的阈值
        private int threshold;
        //阈值的加载因子
        private float loadFactor;
        //Map操作的计数
        private transient int modCount = 0;
        //扩容阈值默认的最大值
        static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

> 注意：这是Hashtable与HashMap第二个不同的地方，Hashtable的默认容量大小为11，HashMap的默认容量大小为16且扩容的大小必须一直是2的幂次方。

注意：HashTable和HashMap的存储结点类型是一样的，都是基于Entry，这个类的结构和HashMap中的属性一样：用图表示就是这样的数据结构：  
![Entry 数据结构][Entry]

## HashTable的构造器 ##

HashTable的构造器最后都会调用  
`Hashtable(int initialCapacity, float loadFactor)`  
这个构造器中默认的初始容量是11，默认的loadFactor是0.75.  
源码如下：

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);
        //当initialapacity输入为0时，默认设置成1
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        //这里就是和hashMap不同的地方，hashMap是延迟加载，在第一次put的时候才new对象，HashTable这里是在构造器中直接new了。
        table = new Entry[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        initHashSeedAsNeeded(initialCapacity);
    }

<table> 
 <thead> 
  <tr> 
   <th>关注点</th> 
   <th align="center">结论</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>集合底层实现的数据结构</td> 
   <td align="center">数组+链表</td> 
  </tr> 
  <tr> 
   <td>集合中元素是否允许为空</td> 
   <td align="center">key允许为空，Value不允许为空</td> 
  </tr> 
  <tr> 
   <td>是否允许重复的数据</td> 
   <td align="center">Key会被覆盖，但是Value 允许重复</td> 
  </tr> 
  <tr> 
   <td>是否有序</td> 
   <td align="center">无序，特别说明这个无序指的是遍历HashTable的时候，得到的元素的顺序基本不可能是put的顺序</td> 
  </tr> 
  <tr> 
   <td>是否线程安全。</td> 
   <td align="center">线程安全（同步原语synchronized实现）</td> 
  </tr> 
 </tbody> 
</table>

## HashTable常用的几个方法 ##

> 注意：在Hashtable中所有的方法都是用synchronized关键字进行了同步，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。

### 1. put(K key, V 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 = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }
    
        modCount++;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();
    
            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
    
        // Creates the new entry.
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }

很明显方法用synchronized修饰了，即是一个同步的方法，所以HashTable是线程安全的。  
1. 首先value是不能为空的，如果Value为空就会抛出异常。这是与HashMap的区别，hashMap的key和value是都允许为null的。  
2. 判断当前key是否已经在table表中(通过key计算出hash值，再通过hash值计算出index，判断index位置的table数据单链表)，如果已经在table表中，就直接更新value值就可以了。  
3. 这个时候就是key是新的，也就是要存入table表中的键值对。首先就是判断count是否已经超过了扩容的阈值（`if (count >= threshold)`）,如果超过了就扩容；扩容主要是调用了  
`rehash();` 方法，这个方法源码如下：  
主要实现了两点：  
(1). 首先将table扩容大小为原来容量的两倍加一  
(2). 然后新建一个newCapacity的数组，将原来的table数组的元素拷贝到新的数组中去即可。

protected void rehash() {
        int oldCapacity = table.length;
        Entry<K,V>[] oldMap = table;
    
        //扩容大小为原来容量的 两倍加一
        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<K,V>[] newMap = new Entry[newCapacity];
    
        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        boolean rehash = initHashSeedAsNeeded(newCapacity);
    
        table = newMap;
        //将原来table的数据拷贝到新的数组table中
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;
    
                if (rehash) {
                    e.hash = hash(e.key);
                }
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = newMap[index];
                newMap[index] = e;
            }
        }
    }

这里有一个需要注意的是rehash()函数扩容，涉及到数组的拷贝，所以当HashTable的容量很大的时候，会比较耗费时间。  
4. put()最后的一步就是创建新的Entry实体并插入到table表中。

自此put()函数就已经分析完毕。

### 2.get()方法： ###

先看源码和注释再说话：

public synchronized V get(Object key) {
        Entry tab[] = table;
        //根据可以计算出hash值
        int hash = hash(key);
        //根据hash值获取索引值
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //根据table数组的index判断table[index]位置是否有key，如果有就返回value，否则返回value
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

两个比较重要的方法已经写完了，其余的remove()等函数都比较简单了，上面两个函数的解析已经足以说明HashTable的运行原理。

[HashTable]: /images/20220713/04f0656d9a8c410eaabb31e72968ace6.png
[Entry]: /images/20220713/418bc7a6f5884e0c877e333bcd2f323e.png