HashMap , HashTable , ConcurrentHashMap 源码比较__v1.0

简介: HashMap , HashTable , ConcurrentHashMap 源码比较

                   首先,HashMap , HashTable 与 ConcurrentHashMap 里面用的 都是 数组(Node<K,V>[] table; 与 Entry<?,?>[] table;),而且它们都是 transient 的,对于 transient ,效果如下:


/**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;                                      HashMap

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;


/**
     * The hash table data.
     */
    private transient Entry<?,?>[] table;                             HashTable

    /**
     * The total number of entries in the hash table.
     */
    private transient int count;

    /**
     * The table is rehashed when its size exceeds this threshold.  (The
     * value of this field is (int)(capacity * loadFactor).)
     *
     * @serial
     */
    private int threshold;

    /**
     * The load factor for the hashtable.
     *
     * @serial
     */
    private float loadFactor;


/**
     * The array of bins. Lazily initialized upon first insertion.
     * Size is always a power of two. Accessed directly by iterators.
     */
    transient volatile Node<K,V>[] table;                             ConcurrentHashMap

    /**
     * The next table to use; non-null only while resizing.
     */
    private transient volatile Node<K,V>[] nextTable;

    /**
     * Base counter value, used mainly when there is no contention,
     * but also as a fallback during table initialization
     * races. Updated via CAS.
     */
    private transient volatile long baseCount;

                              1)一旦变量被transient修饰,变量将不再是对象持久化的一部分,该变量内容在序列化后无法获得访问。

                              2)transient关键字只能修饰变量,而不能修饰方法和类。注意,本地变量是不能被        transient关键字修饰的。变量如果是用户自定义类变量,则该类需要实现Serializable接口。

                              3)被transient关键字修饰的变量不再能被序列化,一个静态变量不管是否被transient修饰,均不能被序列化。

                        且  ConcurrentHashMap 中的table同时被声明为 volatile,意义如下:

                                   1)一个变量声明为volatile,就意味着这个变量是随时会被其他线程修改的,因此不能将它cache在线程memory中。

                                   2)Volatile一般情况下不能代替sychronized,因为volatile不能保证操作的原子性,即使只是i++,实际上也是由多个原子操作组成:read i; inc; write i,假如多个线程同时执行i++,volatile只能保证他们操作的i是同一块内存,但依然可能出现写入脏数据的情况。如果配合Java 5增加的atomic wrapper classes,对它们的increase之类的操作就不需要sychronized。 


                           HashMap 与 ConcurrentHashMap 继承的是 AbstractMap,而 HashTable 继承的是 Dictionary;它们是有区别的: 1,Dictionary 允许空键和空值,keys()函数返回的是一个迭代器; 2,AbstractMap的keySet返回的是一个 set,Dictionary的方法没有AbstractMap丰富。


                   其次,HashTable与ConcurrentHashMap是线程安全的,但是方式上不一样: HashTable 是直接在方法上加 synchronized ; 而ConcurrentHashMap是在table的node上加synchronized,更加细致,也更有效率。

public synchronized V put(K key, V value) {            HashTable的put方法
        // 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;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

public V put(K key, V value) {                 ConcurrentHashMap的put方法
        return putVal(key, value, false);
    }

    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

                   最后,对于 HashMap 中 冲突后 链地址法 的实现(HashTable中用的是 rehash法,对于这一点,从其使用的是 Entry<?,?>[] table; 也可以看出),记得在1.7版本看到的是直接加到table中当前节点的前边添加新冲突的node;但是对于1.8的实现,发现不是直接添加,而是使用 红黑树(根据value进行构造) 进行处理

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,     1.8 版本 插入 key-value
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)         // 不冲突就直接插入
            tab[i] = newNode(hash, key, value, null);
        else {                                             // 冲突,
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)                // 是 红黑树 节点,直接插入树中
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {                                         // 满足 TREEIFY_THRESHOLD 才变成树
for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 构造红黑树 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }




目录
相关文章
|
13天前
|
安全 存储 Java
HashMap和Hashtable区别是什么?
HashMap和Hashtable区别是什么?
16 4
|
1月前
|
安全 算法
HashMap和Hashtable 的区别
HashMap和Hashtable 的区别
23 0
|
1月前
|
存储 安全 Java
HashMap和HashTable的区别
HashMap和HashTable的区别
26 0
|
9月前
|
存储 安全 算法
HashMap和ConcurrentHashmap
大家好,我是苍何。最近思考了一个问题,为什么会出现公司面试造火箭,工作扭螺丝的现象,包括各种八股文的连环大绝杀问到你不会为主,其实这是考察你的知识面以及掌握的深度,而为什么需要这样呢?归其原因,无非是通过筛选找到那些会思考的人,他们需要的并不是CRUD的工具人,而是会思考能创新的工程师。
26 0
|
11月前
|
安全
Hashtable与ConcurrentHashMap的区别
Hashtable与ConcurrentHashMap的区别
|
11月前
|
安全
HashMap 和 HashTable 的区别
HashMap 和 HashTable 的区别
94 0
|
存储 安全 Java
HashMap和Hashtable以及ConcurrentHashMap的区别
HashMap是在JDK1.2中引入的Map的实现类。
282 0
|
存储 安全
HashTable 与HashMap区别
HashTable 与HashMap区别
84 0
|
存储 安全 算法
HashMap和Hashtable的联系与区别
HashMap和Hashtable的联系与区别
143 0
HashMap和Hashtable的联系与区别
|
安全 Java
HashMap与HashTable的区别
HashMap与HashTable的区别
93 0

热门文章

最新文章