美文网首页java
Java集合-Hashtable实现原理源码分析

Java集合-Hashtable实现原理源码分析

作者: Misout | 来源:发表于2017-08-27 20:11 被阅读196次

    前面介绍了HashMap,ConcurrentHashMap,我们再来介绍Hashtable的实现原理,也可以先看笔者写的如下文章学习学习。

    1、Java集合-类的继承组合关系
    2、Java集合-HashMap源码实现深入解析
    3、Java集合-LinkedHashMap工作原理
    4、Java集合-ConcurrentHashMap工作原理和实现JDK7
    5、Java集合-ConcurrentHashMap工作原理和实现JDK8
    6、ConcurrentHashMap与红黑树实现分析Java8

    Hashtable与HashMap的区别

    Hashtable与HashMap都是用来存储key-value类型数据的,两者有如下区别:

    1、Hashtable不允许null key和null value,HashMap允许。
    2、Hashtable是线程安全的,HashMap不是线程安全的。
    3、HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。
    4、Hashtable继承自Dictionary,HashMap继承自AbstractMap。
    5、两者都实现了Map接口。

    Hashtable的继承关系

    从继承图来看,Hashtable继承自Dictionary,这点与HashMap不同。同时从所拥有的属性也能看出Hashtable的数据结构。

    Hashtable的继承关系UML类图
    public class Hashtable<K,V> extends Dictionary<K,V> implements 
                        Map<K,V>, Cloneable, java.io.Serializable {
        // 省略
    }
    

    Hashtable的数据结构

    在Java6中HashMap中采用table数组+链表的方式来实现(Java8中采用数组+链表+红黑树)。Hashtable的数据结构也采用这种结构。

    我们先看一段Java代码:

    Hashtable<String, String> hashtable = new Hashtable<String, String>();
    hashtable.put("语文", "1");
    hashtable.put("数学", "2");
    hashtable.put("英语", "3");
    hashtable.put("物理", "4");
    hashtable.put("化学", "5");
    hashtable.put("生物", "6");
    hashtable.put("政治", "7");
    hashtable.put("地理", "8");
    hashtable.put("历史", "9");
    
    for (Map.Entry<String, String> entry : hashtable.entrySet()) {
        System.out.println(entry.getKey() + " --> " + entry.getValue());
    }
    

    想想输出结果会是什么?输出结果如下:

    英语 --> 3
    地理 --> 8
    物理 --> 4
    数学 --> 2
    历史 --> 9
    化学 --> 5
    语文 --> 1
    政治 --> 7
    生物 --> 6
    

    从输出结果来看,Hashtable put的顺序与读取的顺序和HashMap一样不保证一致。

    Hashtable的数据结构如下图所示,和HashMap一样,采用Entry数组+链表的方式实现。

    Hashtable数据结构图

    根据数据结构图看下源码中支持此数据结构的重要属性:

    public class Hashtable<K,V> extends Dictionary<K,V> implements 
                        Map<K,V>, Cloneable, java.io.Serializable {
        
        // 存储元素的table,Entry节点采用内部类实现
        private transient Entry[] table;
    
        // 已存放元素的计数器
        private transient int count;
        
        // 扩容阈值=table长度 * loadFactor
        // table表的元素(不包含链表中的元素)超过这个阈值将扩容
        private int threshold;
        
        // 负载因子
        private float loadFactor;
        
        // 其他省略
    }
    

    其中table中存储的是Entry节点,Entry节点直接采用内部类的方式实现,实现了Map.Entry类,其数据结构源码如下:

    private static class Entry<K,V> implements Map.Entry<K,V> {
        int hash;
        K key;
        V value;
        Entry<K,V> next;// 链接的下一个节点,构成链表
    }
    

    Entry节点中存储了元素的hash值,key, value,next引用。至此Hashtable的数据结构从源码就能看出来是数组+链表的方式实现了。

    Hashtable的初始化

    来看下Hashtable的默认构造方法是怎么初始化Hashtable的。

    public Hashtable() {
        this(11, 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);
    
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int)(initialCapacity * loadFactor);
    }
    

    在默认构造方法中,调用了Hashtable(int initialCapacity, float loadFactor)方法,初始Hashtable的容量为11,负载因子为0.75,那么初始阈值就是8。这点和HashMap很不同,HashMap在初始化时,table的大小总是2的幂次方,即使给定一个不是2的幂次方容量的值,也会自动初始化为最接近其2的幂次方的容量。

    Hashtable的put方法的实现

    源码实现步骤和HashMap没有任何区别,知识put方法上增加了synchronized关键字,保证线程安全。

    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;
        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;
                index = (hash & 0x7FFFFFFF) % tab.length;
        }
    
        // Creates the new entry.
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<K,V>(hash, key, value, e);
        count++;
        return null;
    }
    

    实现步骤和思路:

    1、禁止null value插入。
    2、根据key的hashCode值 与 0x7FFFFFFF求与后得到新的hash值,然后计算其在table中的索引下标。
    3、在索引下标下遍历链表,查找key是否已存在,存在则更新value值。
    4、如果不存在,判断table.count是否超过阈值,超过则重新rehash,将原元素全部拷贝到新的table中,并重新计算索引下标。rehash后,容量是以前的2倍+1的大小,这点也和HashMap不同,HashMap是2倍。
    5、插入元素时直接插入在链表头部。
    6、更新元素计数器。

    至于rehash方法的实现还请读者自行阅读源码,比较简单。get等其他方法也不做过多介绍,都比较简单。

    Hashtable如何保证线程安全

    前面提到的put方法中是通过synchronized来保证线程安全的。查看源码,发现对外提供的public方法,几乎全部加上了synchronized关键字。如下:

    public synchronized int size(){}
    public synchronized boolean isEmpty() {}
    public synchronized Enumeration<K> keys() {}
    public synchronized Enumeration<V> elements() {}
    public synchronized boolean contains(Object value) {}
    public synchronized boolean containsKey(Object key) {}
    public synchronized V get(Object key) {}
    public synchronized V put(K key, V value) {}
    public synchronized V remove(Object key) {}
    public synchronized void putAll(Map<? extends K, ? extends V> t) {}
    public synchronized void clear() {}
    public synchronized Object clone() {}
    public synchronized String toString() {}
    public synchronized boolean equals(Object o) {}
    public synchronized int hashCode() {}
    

    所以从这个特性上看,Hashtable是通过简单粗暴的方式来保证线程安全的额。所以Hashtable的性能在多线程环境下会非常低效。前面介绍的ConcurrentHashMap其实就是Java开发团队为了替换他而开发的,性能提高了不少。笔者也建议大家在多线程环境下抛弃Hashtable,改用ConcurrentHashMap,或者用HashMap配合外部锁,例如ReentrantLock来提高效率。

    大概是Java团队已经开发出替代者ConcurrentHashMap,所以Hashtable从源码的实现来看,和JDK5相比,没有什么提升,大概是Java团队放弃了这个类的维护了。

    相关文章

      网友评论

        本文标题:Java集合-Hashtable实现原理源码分析

        本文链接:https://www.haomeiwen.com/subject/utridxtx.html