Java容器解析——Hashtable

前言

Hashtable 是一个散列表，它存储的内容是键值对(key-value)映射。对于散列与映射可以参考哈希表（散列表）原理详解

1 Hashtable类定义

    public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    
    }
    
    //内部静态类HashtableEntry，HashtableEntry为存储的节点
    //HashtableEntry本质为链表
    private static class HashtableEntry<K,V> implements Map.Entry<K,V> {
        //哈希值
        final int hash;
        //键值
        final K key;
        //存储的数据值
        V value;
        //指向下一个节点
        HashtableEntry<K,V> next;

        protected HashtableEntry(int hash, K key, V value, HashtableEntry<K,V> next) {
            this.hash = hash;
            this.key =  key;
            this.value = value;
            this.next = next;
        }

        @SuppressWarnings("unchecked")
        protected Object clone() {
            return new HashtableEntry<>(hash, key, value,
                                  (next==null ? null : (HashtableEntry<K,V>) next.clone()));
        }

       
        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的数组,支持泛型 
    // Hashtable同样采用链表解决冲突，每一个Entry本质上是一个单向链表    
    private transient HashtableEntry<?,?>[] table; 
   
    // Hashtable中键值对的数量    
    private transient int count;    
   
    // 阈值，用于判断是否需要调整Hashtable的容量
    private int threshold;    
   
    // 负载因子，当元素个数count大于总容量 * 负载因子时，扩容
    private float loadFactor;    
   
    // Hashtable被改变的次数，用于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 HashtableEntry<?,?>[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 核心方法

方法名	含义	时间复杂度
get(Object key)	根据key值获取元素	O(1)
put(K key, V value)	添加元素	O(n)
putAll()	添加集合中元素	O(n)
contains(Object value)	判断是否包含元素	O(n)
containsValue(Object value)	判断是否包含元素	O(n)
containsKey(Object key)	判断是否包含key	O(1)
replace(K key, V oldValue, V newValue)	替换元素值	O(1)
size()	获取元素数目	O(1)
isEmpty()	判断集合是否为空	O(1)
remove(Object key)	根据键值删除元素	O(n)
clear()	清空集合	O(n)

5 get()方法

    public synchronized V get(Object key) {
        
        HashtableEntry<?,?> tab[] = table;
        //得到key的hashcode
        int hash = key.hashCode();
        //根据hashcode计算索引值
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //根据index找到key对应HashtableEntry链表，遍历链表找到哈希值与键值均与key相同的元素
        for (HashtableEntry<?,?> 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();
        }

        HashtableEntry<?,?> tab[] = table;
        //根据键值获取索引index
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //采用for循环方式解决哈希冲突，如果出现冲突则放在链表末尾。
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> entry = (HashtableEntry<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++;

        HashtableEntry<?,?> tab[] = table;
        
        //判断当前数目是否超过阈值
        if (count >= threshold) {
            // 数目超过阈值，扩容
            rehash();

            //更新扩容后的数组信息
            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // 没有超过阈值，则添加至数组中
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> e = (HashtableEntry<K,V>) tab[index];
        tab[index] = new HashtableEntry<>(hash, key, value, e);
        
        //增加元素数目
        count++;
    }
    
    //扩容方法
    protected void rehash() {
     
        //获取旧数组大小
        int oldCapacity = table.length;
        HashtableEntry<?,?>[] oldMap = table;

        // 创建新容量大小的HashtableEntry数组，数组容量大小为原数组的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;
        }
        HashtableEntry<?,?>[] newMap = new HashtableEntry<?,?>[newCapacity];

        modCount++;
        
        //重新计算阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;

        //将原数组中元素拷贝至新数组
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (HashtableEntry<K,V> old = (HashtableEntry<K,V>)oldMap[i] ; old != null ; ) {
                HashtableEntry<K,V> e = old;
                old = old.next;

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

8 replace()方法

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

9 remove()方法

    //根据键值删除元素，返回被删除元素值
    public synchronized V remove(Object key) {
    
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
        //for遍历链表查找元素
        for(HashtableEntry<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 (Iterator<T>) emptyIterator;    
        } else {    
            return new Enumerator<T>(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<K,V> entry = null;    
        Entry<K,V> lastReturned = null;    
        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<K,V> 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。    
        public T nextElement() {    
            Entry<K,V> 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<K,V> e = lastReturned = entry;    
                entry = e.next;    
                return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);    
            }    
            throw new NoSuchElementException("Hashtable Enumerator");    
        } 
    }

11 小结

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

Java容器解析——Hashtable

Java容器解析——Hashtable

Java容器解析——ArrayList

Java容器解析——LinkedList

Java容器解析——Hashtable

前言

1 Hashtable类定义

2 属性值

3 构造方法

4 核心方法

5 get()方法

6 put()方法

7 contains()方法

8 replace()方法

9 remove()方法

10 elements()方法

11 小结

推荐阅读更多精彩内容