并發(fā)容器--ConcurrentHashMap常見面試題

首先說下什么是hash?hash是散列的意思，就是把任意長度的數(shù)據(jù)按照散列算法生成固定長度的輸出兆沙，該輸出就是散列值装悲。這種轉(zhuǎn)換是一種壓縮映射，也就是绽榛，散列的空間遠小于輸入的空間，不同的輸入可能散列成相同的輸出婿屹，所以不可能從散列之后的數(shù)據(jù)拿到原數(shù)據(jù)灭美，簡單來說，就是將一種將任意長度的消息壓縮到某一固定長度消息摘要的函數(shù)昂利。常用的HASH函數(shù)有：直接取余法届腐、乘法取整法铁坎、平分取中法。

下面來說一下jdk1.7里面HashMap在多線程下面可能引起的死循環(huán)問題

首先來聊一聊HashMap的實現(xiàn)犁苏，其中主要的方法有put和get方法厢呵，而引起死循環(huán)問題出現(xiàn)在put方法里面

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

在put方法里面，拿到hash值傀顾，計算在table的位置襟铭，然后遍歷table,如果hash值相同或者key相同，替換原值短曾，返回原值寒砖；如果沒有，需要新增嫉拐，調(diào)用addEntry()哩都；

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

addEntry方法判斷長度是否足夠，如果夠婉徘，就直接新增漠嵌，如果不夠需要擴容resize()，成原來的兩倍大懈呛簟儒鹿；

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

在resize方法里面，只是簡單的將table長度擴容了几晤，具體的實現(xiàn)在transfer方法里面约炎；

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

在transfer方法里面，遍歷原節(jié)點的table蟹瘾，將之前的數(shù)據(jù)放到新的table里面圾浅，使用了頭插法，將相同hash值的數(shù)據(jù)憾朴，插入到鏈表的頭部狸捕；具體看 e.next = newTable[i]；newTable[i] = e众雷；e = next灸拍；
HashMap的擴容操作是這樣的：
1.取當前table的兩倍大小作為新table的大小
2.根據(jù)算出的table大小，new出一個新的Entry數(shù)組报腔，命名為newTable
3.輪詢原table的每一個位置株搔，將每個位置上連接的Entry剖淀，計算出在新的table上的位置纯蛾，并以鏈表形式連接
4.原table上的所有Entry輪詢完畢，意味著原table的所有Entry都轉(zhuǎn)移到新table上纵隔，HashMap的table指向newTable

1.HashMap 和 HashTable 有什么區(qū)別翻诉？

HashMap 線程不安全的炮姨，HashTable 線程安全的；
HashMap 效率高碰煌，HashTable 效率低舒岸；
HashMap Key|value = null，HashTable key|value != null;
HashMap 初始化為16位芦圾，HashTable 初始化為11位;
HashMap 擴容長度為2n蛾派，HashTable 擴容長度為2n+1
HashMap 擴容時再hash一次計算位置，HashTable 繼續(xù)用以前的

2.Java 中的另一個線程安全的與 HashMap 極其類似的類是什么个少？同樣是線程安全洪乍，它與 HashTable 在線程同步上有什么不同？

ConcurrentHashMap;HashTable鎖了整個map夜焦，效率低壳澳，1.7使用分段鎖，1.8使用CAS茫经、分段鎖巷波、synchronized關(guān)鍵字；

3.HashMap & ConcurrentHashMap 的區(qū)別卸伞？

除了線程安全抹镊，其他的沒有大部分沒有差別；HashMap容許key荤傲、value =null髓考；ConcurrentHashMap不容許；HashMap TreeNode繼承的是LinkedHashMap.Entry,而ConcurrentHashMap TreeNode繼承的是Node(本身定義的數(shù)據(jù)節(jié)點)

4.為什么 ConcurrentHashMap 比 HashTable 效率要高弃酌？

HashTable使用一把鎖氨菇，鎖了整個結(jié)構(gòu)，多個線程使用一把鎖妓湘，會阻塞查蓉，影響效率；
而ConcurrentHashMap使用分段鎖榜贴，鎖的粒度降低豌研；

5.ConcurrentHashMap 鎖機制具體分析（JDK 1.7 VS JDK 1.8）？

1.7使用分段鎖的機制唬党，底層使用數(shù)組加鏈表的結(jié)構(gòu)鹃共，使用Segment、HashEntry數(shù)據(jù)結(jié)構(gòu)驶拱，Segment繼承ReentrantLock可重入鎖霜浴，使用它來保護HashEntry操作的數(shù)據(jù)原子性
1.8使用Node、CAS蓝纲、synchronized關(guān)鍵字來保證并發(fā)安全阴孟，取消了Segment這一層晌纫；同時使用了紅黑樹機制，紅黑樹可以和鏈表相互轉(zhuǎn)化永丝，以提升查詢性能锹漱；

6.ConcurrentHashMap 在 JDK 1.8 中，為什么要使用內(nèi)置鎖 synchronized 來代替重入鎖 ReentrantLock慕嚷？

synchronized性能優(yōu)化哥牍，基于虛擬機語言關(guān)鍵字的優(yōu)化更加關(guān)鍵和自然；
顯示鎖消耗內(nèi)存喝检，而synchronized內(nèi)存消耗小

7.1.8下ConcurrentHashMap 簡單介紹砂心？

常見數(shù)據(jù)結(jié)構(gòu)、put蛇耀、get實現(xiàn)
1）sizeCtl 來控制了初始化辩诞、擴容大小，是否正在進行初始化和擴容
2）Node 繼承至Entry纺涤，用于存儲數(shù)據(jù)译暂，是存儲的基本單元，同時在基于Node的基礎(chǔ)上撩炊，為了實現(xiàn)紅黑樹外永，擴展了TreeNode、TreeBin拧咳；TreeNode用于在紅黑樹存儲數(shù)據(jù)伯顶，TreeBin封裝了TreeNode，提供了讀寫鎖骆膝；
3）get方法：計算hash值祭衩，如果定位到table本身，直接返回阅签；如果不是掐暮，根據(jù)當前節(jié)點類型，分別按照鏈表和紅黑樹的方式去查找當前元素所在的位置
4）put方法：如果沒有初始化政钟，首先進行初始化路克；使用CAS無鎖方式插入，如果發(fā)現(xiàn)需要擴容养交，首先進行擴容精算；如果存在hash沖突，需要掛在table節(jié)點下面碎连，先將當前table節(jié)點加鎖灰羽，鏈表按照尾插入方式進行插入，紅黑樹按照紅黑樹的結(jié)構(gòu)進行插入，同時put在插入過程中谦趣，如果發(fā)現(xiàn)table里面的元素超過8個疲吸，就將鏈表改造成紅黑樹座每，并且還會進行元素個數(shù)的統(tǒng)計前鹅，并檢查是否需要擴容；
5）擴容方法：1.8里面峭梳，為了提高效率舰绘，工作線程會進行并發(fā)擴容，同時為了避免多個線程有并發(fā)沖突葱椭，每個線程會進行步長的方式在節(jié)點之間來進行操作捂寿；

8.ConcurrentHashMap 的并發(fā)度是什么？

1.7 默認的并發(fā)度為16孵运，可以在構(gòu)造函數(shù)進行設(shè)置秦陋，但是進行設(shè)置時，ConcurrentHashMap會使用一個 >=要改數(shù)字的2的最小次方數(shù)作為實際并發(fā)數(shù)治笨，比如設(shè)置為17驳概，實際并發(fā)度為 32；
1.8 并發(fā)度沒有實際意義旷赖，當我設(shè)置初始容量小于并發(fā)度時顺又，將容量提升至并發(fā)度大小