并发容器--ConcurrentHashMap常见面试题

首先说下什么是hash?hash是散列的意思，就是把任意长度的数据按照散列算法生成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列的空间远小于输入的空间，不同的输入可能散列成相同的输出，所以不可能从散列之后的数据拿到原数据，简单来说，就是将一种将任意长度的消息压缩到某一固定长度消息摘要的函数。常用的HASH函数有：直接取余法、乘法取整法、平分取中法。

下面来说一下jdk1.7里面HashMap在多线程下面可能引起的死循环问题

首先来聊一聊HashMap的实现，其中主要的方法有put和get方法，而引起死循环问题出现在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相同，替换原值，返回原值；如果没有，需要新增，调用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长度扩容了，具体的实现在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方法里面，遍历原节点的table，将之前的数据放到新的table里面，使用了头插法，将相同hash值的数据，插入到链表的头部；具体看 e.next = newTable[i]；newTable[i] = e；e = next；
HashMap的扩容操作是这样的：
1.取当前table的两倍大小作为新table的大小
2.根据算出的table大小，new出一个新的Entry数组，命名为newTable
3.轮询原table的每一个位置，将每个位置上连接的Entry，计算出在新的table上的位置，并以链表形式连接
4.原table上的所有Entry轮询完毕，意味着原table的所有Entry都转移到新table上，HashMap的table指向newTable

1.HashMap 和 HashTable 有什么区别？

HashMap 线程不安全的，HashTable 线程安全的；
HashMap 效率高，HashTable 效率低；
HashMap Key|value = null，HashTable key|value != null;
HashMap 初始化为16位，HashTable 初始化为11位;
HashMap 扩容长度为2n，HashTable 扩容长度为2n+1
HashMap 扩容时再hash一次计算位置，HashTable 继续用以前的

2.Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同？

ConcurrentHashMap;HashTable锁了整个map，效率低，1.7使用分段锁，1.8使用CAS、分段锁、synchronized关键字；

3.HashMap & ConcurrentHashMap 的区别？

除了线程安全，其他的没有大部分没有差别；HashMap容许key、value =null；ConcurrentHashMap不容许；HashMap TreeNode继承的是LinkedHashMap.Entry,而ConcurrentHashMap TreeNode继承的是Node(本身定义的数据节点)

4.为什么 ConcurrentHashMap 比 HashTable 效率要高？

HashTable使用一把锁，锁了整个结构，多个线程使用一把锁，会阻塞，影响效率；
而ConcurrentHashMap使用分段锁，锁的粒度降低；

5.ConcurrentHashMap 锁机制具体分析（JDK 1.7 VS JDK 1.8）？

1.7使用分段锁的机制，底层使用数组加链表的结构，使用Segment、HashEntry数据结构，Segment继承ReentrantLock可重入锁，使用它来保护HashEntry操作的数据原子性
1.8使用Node、CAS、synchronized关键字来保证并发安全，取消了Segment这一层；同时使用了红黑树机制，红黑树可以和链表相互转化，以提升查询性能；

6.ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

synchronized性能优化，基于虚拟机语言关键字的优化更加关键和自然；
显示锁消耗内存，而synchronized内存消耗小

7.1.8下ConcurrentHashMap 简单介绍？

常见数据结构、put、get实现
1）sizeCtl 来控制了初始化、扩容大小，是否正在进行初始化和扩容
2）Node 继承至Entry，用于存储数据，是存储的基本单元，同时在基于Node的基础上，为了实现红黑树，扩展了TreeNode、TreeBin；TreeNode用于在红黑树存储数据，TreeBin封装了TreeNode，提供了读写锁；
3）get方法：计算hash值，如果定位到table本身，直接返回；如果不是，根据当前节点类型，分别按照链表和红黑树的方式去查找当前元素所在的位置
4）put方法：如果没有初始化，首先进行初始化；使用CAS无锁方式插入，如果发现需要扩容，首先进行扩容；如果存在hash冲突，需要挂在table节点下面，先将当前table节点加锁，链表按照尾插入方式进行插入，红黑树按照红黑树的结构进行插入，同时put在插入过程中，如果发现table里面的元素超过8个，就将链表改造成红黑树，并且还会进行元素个数的统计，并检查是否需要扩容；
5）扩容方法：1.8里面，为了提高效率，工作线程会进行并发扩容，同时为了避免多个线程有并发冲突，每个线程会进行步长的方式在节点之间来进行操作；

8.ConcurrentHashMap 的并发度是什么？

1.7 默认的并发度为16，可以在构造函数进行设置，但是进行设置时，ConcurrentHashMap会使用一个 >=要改数字的2的最小次方数作为实际并发数，比如设置为17，实际并发度为 32；
1.8 并发度没有实际意义，当我设置初始容量小于并发度时，将容量提升至并发度大小