JDK1.8 Hashtable详解

向右看齐 2023-06-20 06:21 7阅读 0赞

Hashtable 是一个散列表，它存储的内容是键值对(key-value)映射。

### 1 Hashtable类定义 ###

public class Hashtable<K,V>
        extends Dictionary<K,V>
        implements Map<K,V>, Cloneable, java.io.Serializable {
        
        }
        
        //内部静态类Entry，Entry为存储的节点
        //Entry本质为链表
            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;
            }
    
            @SuppressWarnings("unchecked")
            protected Object clone() {
                return new Entry<>(hash, key, value,
                                      (next==null ? null : (Entry<K,V>) next.clone()));
            }
    
            // Map.Entry Ops
    
            public K getKey() {
                return key;
            }
    
            public V getValue() {
                return value;
            }
    
            public V setValue(V value) {
                if (value == null)
                    throw new NullPointerException();
    
                V oldValue = this.value;
                this.value = value;
                return oldValue;
            }
    
            public boolean equals(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    
                return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
                   (value==null ? e.getValue()==null : value.equals(e.getValue()));
            }
    
            public int hashCode() {
                return hash ^ Objects.hashCode(value);
            }
    
            public String toString() {
                return key.toString()+"="+value.toString();
            }
        }

> 1）Hashtable继承于Dictionary抽象类，Dictionary中定义了对于容器操作的多种抽象方法。  
> 2）实现Map接口，Hashtable实现了Map接口中定义的方法,具体的方法将在后文中分析。  
> 3）实现Cloneable接口。  
> 4）实现Serializable接口，可序列化。

### 2 属性值 ###

Hashtable的属性值含义已在代码注释中说明

// 保存key-value的数组,支持泛型 
        // Entry同样采用链表解决冲突，每一个Entry本质上是一个单向链表    
        private transient Entry<?,?>[] table;
       
        // Entry中键值对的数量    
        private transient int count;    
       
        // 阈值，用于判断是否需要调整Entry的容量
        private int threshold;    
       
        // 负载因子，当元素个数count大于总容量 * 负载因子时，扩容
        private float loadFactor;    
       
        // Entry被改变的次数，用于fail-fast机制的实现    
        private transient int modCount = 0;

### 3 构造方法 ###

1）无参构造方法

//无参构造方法
        public Hashtable() {
            //默认容量大小为11，负载因子设置为0.75
            this(11, 0.75f);
        }

2）初始化容量大小为initialCapacity

//带有初始化容量大小的构造方法
        public Hashtable(int initialCapacity) {
            this(initialCapacity, 0.75f);
        }

3） 初始化容量为initialCapacity，负载因子为 loadFactor

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 = new Entry<?,?>[initialCapacity];
    
          
            //计算阈值，取初始化容量与可分配的最大容量中的最小值。
            threshold = (int)Math.min(initialCapacity, MAX_ARRAY_SIZE + 1);
        }

4） 使用Map集合初始化

//使用Map集合初始化
        public Hashtable(Map<? extends K, ? extends V> t) {
            // 若集合t元素大于5，则初始化容量为集合t中元素数目的2倍
            // 否则初始化容量为11
            // 负载因子设置为0.75
            this(Math.max(2*t.size(), 11), 0.75f);
            //将集合t中元素全部存储
            putAll(t);
        }
        
    
        public synchronized void putAll(Map<? extends K, ? extends V> t) {
            // for循环遍历集合t，将t中元素存储到this集合中
            for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
                //将键值对添加至集合中
                put(e.getKey(), e.getValue());
        }

### 4 核心方法 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <th>方法名</th> 
   <th>含义</th> 
   <th>时间复杂度</th> 
  </tr> 
  <tr> 
   <td>get(Object key)</td> 
   <td>根据key值获取元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>put(K key, V value)</td> 
   <td>添加元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>putAll()</td> 
   <td>添加集合中元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>contains(Object value)</td> 
   <td>判断是否包含元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>containsValue(Object value)</td> 
   <td>判断是否包含元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>containsKey(Object key)</td> 
   <td>判断是否包含key</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>replace(K key, V oldValue, V newValue)</td> 
   <td>替换元素值</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>获取元素数目</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>isEmpty()</td> 
   <td>判断集合是否为空</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>remove(Object key)</td> 
   <td>根据键值删除元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>clear()</td> 
   <td>清空集合</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

### 5 get()方法 ###

public synchronized V get(Object key) {
            
            Entry<?,?> tab[] = table;
            //得到key的hashcode
            int hash = key.hashCode();
            //根据hashcode计算索引值
            int index = (hash & 0x7FFFFFFF) % tab.length;
            //根据index找到key对应Entry链表，遍历链表找到哈希值与键值均与key相同的元素
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    return (V)e.value;
                }
            }
            // 若没有找到，则返回null
            return null;
        }

### 6 put()方法 ###

public synchronized V put(K key, V value) {
        
            // 检验数据值的合法性
            if (value == null) {
                throw new NullPointerException();
            }
    
            Entry<?,?> tab[] = table;
            //根据键值获取索引index
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            //采用for循环方式解决哈希冲突，如果出现冲突则放在链表末尾。
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            for(; entry != null ; entry = entry.next) {
                 //当前键值key已存在，更新key的映射值value，并返回旧值
                if ((entry.hash == hash) && entry.key.equals(key)) {
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
    
            //若没有找到重复键值key，则将key和value添加链表末尾
            addEntry(hash, key, value, index);
            return null;
        }
        
        //添加元素
        private void addEntry(int hash, K key, V value, int index) {
        
        
            modCount++;
    
            Entry<?,?> tab[] = table;
            
            //判断当前数目是否超过阈值
            if (count >= threshold) {
                // 数目超过阈值，扩容
                rehash();
    
                //更新扩容后的数组信息
                tab = table;
                hash = key.hashCode();
                index = (hash & 0x7FFFFFFF) % tab.length;
            }
    
            // 没有超过阈值，则添加至数组中
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) tab[index];
            tab[index] = new Entry<>(hash, key, value, e);
            
            //增加元素数目
            count++;
        }
        
        //扩容方法
        protected void rehash() {
         
            //获取旧数组大小
            int oldCapacity = table.length;
            Entry<?,?>[] oldMap = table;
    
            // 创建新容量大小的Entry数组，数组容量大小为原数组的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];
    
            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;
                }
            }
        }

### 7 contains()方法 ###

//判断是否含有value
        public boolean containsValue(Object value) {
            return contains(value);
        }
        
        public synchronized boolean contains(Object value) {
        
            //检查参数的合法性
            if (value == null) {
                throw new NullPointerException();
            }
    
            // 双重for循环，外循环遍历数组，内循环遍历链表
            Entry<?,?> tab[] = 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;
        }
        
        // 判断是否包含键值key
       public synchronized boolean containsKey(Object key) {
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            // index定位数组位置，for遍历链表查找元素
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    return true;
                }
            }
            return false;
        }

### 8 replace()方法 ###

public synchronized V replace(K key, V value) {
            Objects.requireNonNull(value);
            //根据键值查找元素
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for (; e != null; e = e.next) {
                 //查找成功，替换元素值
                if ((e.hash == hash) && e.key.equals(key)) {
                    V oldValue = e.value;
                    e.value = value;
                    return oldValue;
                }
            }
            return null;
        }

### 9 remove()方法 ###

//根据键值删除元素，返回被删除元素值
    public synchronized V remove(Object key) {
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
             //for遍历链表查找元素
            for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
                //查找到元素进行链表的节点删除操作
                if ((e.hash == hash) && e.key.equals(key)) {
                    modCount++;
                    if (prev != null) {
                        prev.next = e.next;
                    } else {
                        tab[index] = e.next;
                    }
                    count--;
                    V oldValue = e.value;
                    e.value = null;
                    return oldValue;
                }
            }
            return null;
        }

### 10 elements()方法 ###

public synchronized Enumeration<V> elements() {
            return this.<V>getEnumeration(VALUES);
        }
    
        // 获取Hashtable的枚举类对象    
        // 若Hashtable的实际大小为0,则返回“空枚举类”对象；    
        // 否则，返回正常的Enumerator的对象。
    private <T> Enumeration<T> getEnumeration(int type) {
            if (count == 0) {
                return Collections.emptyEnumeration();
            } else {
                return new Enumerator<>(type, false);
            }
        }
    
        // 获取Hashtable的迭代器    
        // 若Hashtable的实际大小为0,则返回“空迭代器”对象；    
        // 否则，返回正常的Enumerator的对象。(Enumerator实现了迭代器和枚举两个接口) 
    private <T> Iterator<T> getIterator(int type) {
            if (count == 0) {
                return Collections.emptyIterator();
            } else {
                return new Enumerator<>(type, true);
            }
        }
    
    
    // Enumerator的作用是提供了“通过elements()遍历Hashtable的接口” 和 “通过entrySet()遍历Hashtable的接口”。    
    private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
            // 指向Hashtable的table   
            Entry<?,?>[] table = Hashtable.this.table;
            // Hashtable的总的大小  
            int index = table.length;
            Entry<?,?> entry;
            Entry<?,?> lastReturned;
            int type;
    
            // Enumerator是 “迭代器(Iterator)” 还是 “枚举类(Enumeration)”的标志    
            // iterator为true，表示它是迭代器；否则，是枚举类。
            boolean iterator;
    
            // 在将Enumerator当作迭代器使用时会用到，用来实现fail-fast机制
            protected int expectedModCount = modCount;
    
            Enumerator(int type, boolean iterator) {
                this.type = type;
                this.iterator = iterator;
            }
    
            // 从遍历table的数组的末尾向前查找，直到找到不为null的Entry。  
            public boolean hasMoreElements() {
                Entry<?,?> e = entry;
                int i = index;
                Entry<?,?>[] t = table;
                /* Use locals for faster loop iteration */
                while (e == null && i > 0) {
                    e = t[--i];
                }
                entry = e;
                index = i;
                return e != null;
            }
    
            // 获取下一个元素    
            // 注意：从hasMoreElements() 和nextElement() 可以看出“Hashtable的elements()遍历方式”    
            // 首先，<span style="color:#ff0000;">从后向前的遍历table数组</span>。table数组的每个节点都是一个单向链表(Entry)。    
            // 然后，依次向后遍历单向链表Entry。    
            @SuppressWarnings("unchecked")
            public T nextElement() {
                Entry<?,?> et = entry;
                int i = index;
                Entry<?,?>[] t = table;
                /* Use locals for faster loop iteration */
                while (et == null && i > 0) {
                    et = t[--i];
                }
                entry = et;
                index = i;
                if (et != null) {
                    Entry<?,?> e = lastReturned = entry;
                    entry = e.next;
                    return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
                }
                throw new NoSuchElementException("Hashtable Enumerator");
            }
    
            // Iterator methods
            public boolean hasNext() {
                return hasMoreElements();
            }
    
            public T next() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                return nextElement();
            }
    
            public void remove() {
                if (!iterator)
                    throw new UnsupportedOperationException();
                if (lastReturned == null)
                    throw new IllegalStateException("Hashtable Enumerator");
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
    
                synchronized(Hashtable.this) {
                    Entry<?,?>[] tab = Hashtable.this.table;
                    int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
    
                    @SuppressWarnings("unchecked")
                    Entry<K,V> e = (Entry<K,V>)tab[index];
                    for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
                        if (e == lastReturned) {
                            modCount++;
                            expectedModCount++;
                            if (prev == null)
                                tab[index] = e.next;
                            else
                                prev.next = e.next;
                            count--;
                            lastReturned = null;
                            return;
                        }
                    }
                    throw new ConcurrentModificationException();
                }
            }
        }

### 11 小结 ###

Hashtable是一个散列表，它存储的内容是键值对(key-value)映射。Hashtable不允许null对象。Hashtable中的方法使用了synchronized关键字修饰，因此Hashtable是线程安全的。