1. HashMap简介

HashMap采用key/value存储结构，每个key对应唯一的value，查询和修改的速度都很快，能达到O(1)的平均时间复杂度。它是非线程安全的，且不保证元素存储的顺序。HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。

2. HashMap存储结构

在Java中，HashMap的实现采用了（数组 + 链表 + 红黑树）的复杂结构，数组的一个元素又称作桶。

在添加元素时，会根据hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把元素以链表的形式放置在链表的尾部。

当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则把链表转化为红黑树，从而提高效率。

数组的查询效率为O(1)，链表的查询效率是O(k)，红黑树的查询效率是O(log k)，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率。

（1）属性

//默认的初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大的容量为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当一个桶中的元素个数大于等于8时进行树化
static final int TREEIFY_THRESHOLD = 8;
//当一个桶中的元素个数小于等于6时把树转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//当桶的个数达到64的时候才进行树化
static final int MIN_TREEIFY_CAPACITY = 64;
//数组，又叫作桶（bucket）
transient Node<K,V>[] table;
//作为entrySet()的缓存
transient Set<Map.Entry<K,V>> entrySet;
//元素的数量
transient int size;
//修改次数，用于在迭代的时候执行快速失败策略
transient int modCount;
//当桶的使用数量达到多少时进行扩容，threshold = capacity * loadFactor
int threshold;
//装载因子
final float loadFactor;

• 容量：为数组的长度，亦即桶的个数，默认为16，最大为2的30次方，当容量达到64时才可以树化。
• 装载因子：用来计算容量达到多少时才进行扩容，默认装载因子为0.75。
• 树化：当容量达到64且链表的长度达到8时进行树化，当链表的长度小于6时反树化。

（2）Node

Node[] table，即哈希桶数组，它是一个Node的数组。Node是HashMap的一个内部类，实现了Map.Entry接口，本质是一个映射(键值对)，也是一个典型的单链表节点。上图中的每个小框框就是一个Node对象。

static class Node<K,V> implements Map.Entry<K,V> {
    //存储key计算得来的hash值
    final int hash;
    //键
    final K key;
    //值
    V value;
    ////链表的下一个node
    Node<K,V> next;
}

（3）TreeNode

TreeNode继承自LinkedHashMap中的Entry类，是一个典型的树型节点。
// 位于HashMap中
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent; 
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    //prev是链表中的节点，用于在删除元素的时候可以快速找到它的前置节点
    TreeNode<K,V> prev;
    boolean red;
}
// 位于LinkedHashMap中，典型的双向链表节点
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

（4）红黑树简介

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)

红黑树具有以下5种性质：

• 节点是红色或黑色。
• 根节点是黑色。
• 每个叶节点（NIL节点，空节点）是黑色的。
• 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的时间复杂度为O(log n)，与树的高度成正比。

红黑树每次的插入、删除操作都需要做平衡，平衡时有可能会改变根节点的位置，颜色转换，左旋，右旋等。

3. Hash算法

（1）链地址法与哈希碰撞

HashMap是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。例如：

map.put("Java","coco");

系统将调用”酸奶”这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算）来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，需要根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。好的Hash算法和扩容机制可以使得Hash碰撞的概率小，哈希桶数组（Node[] table）占用空间少。

（2）hash算法

下面是HashMap的hash算法：

方法一：
//jdk1.8 & jdk1.7
static final int hash(Object key) {   
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
//jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
static int indexFor(int h, int length) { 
     //第三步 取模运算
     return h & (length-1);  
}

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

4. 扩容机制

扩容(resize)就是重新计算容量，向HashMap对象里不停地添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。

（1）扩容步骤

• 扩容：创建一个新的Entry空数组，长度是原数组的2倍。
• ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

为什么要重新计算hash呢？

是因为长度扩大以后，Hash的规则也随之改变。比如原来长度（Length）是8，位运算出来的值是2，新的长度是16，则位运算出来的值明显不一样了。

（2）扩容方法

jdk1.7中HashMap的扩容（transfer）函数如下：
void transfer(Entry[] newTable) {
      //src引用了旧的Entry数组
      Entry[] src = table;                   
      int newCapacity = newTable.length;
      //遍历旧的Entry数组
      for (int j = 0; j < src.length; j++) { 
          //取得旧Entry数组的每个元素
          Entry<K,V> e = src[j];             
          if (e != null) {
              //释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
              src[j] = null;
              do {
                 Entry<K,V> next = e.next;
                 //重新计算每个元素在数组中的位置
                 int i = indexFor(e.hash, newCapacity); 
                 //当前元素指向table对应索引地址的值
                 e.next = newTable[i]; 
                 //将元素放在数组上
                 newTable[i] = e;    
                 //访问下一个Entry链上的元素
                 e = next;             
             } while (e != null);
         }
     }
 }

在对table进行扩容到newTable后，需要将原来数据转移到newTable中，注意do-while内的代码，这里可以看出在转移元素的过程中，使用的是头插法，也就是链表的顺序会翻转，这里是多线程环境下扩容时形成死循环的关键点。

使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了，这也是jdk1.8所做的改动。

由于java8使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

下面是与扩容有关的属性值：

//所能容纳的 key-value对极限 
     int threshold;  
     //负载因子
     final float loadFactor; 
     //记录变化次数
     int modCount;
     //实际存在的键值对数量
     int size;

首先，Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

4. HashMap的put与get方法

（1）put方法

HashMap的put方法执行过程可以通过下图来理解：

流程描述如下：

（2）get方法

5. HashMap为什么是线程不安全的？

• 在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失

扩容时采用头插法复制老数据，导致不同线程操作下容易形成无限循环的环形链以及数据丢失。

• 在jdk1.8中，在多线程环境下，会发生数据覆盖的情况

java8的HashMap源码中看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。

6. 以HashMap举例，重写equals方法的时候为什么需要重写hashCode方法

equals方法和hashCode方法都是Object类中的方法

//equals
public boolean equals(Object obj) {
        return (this == obj);
    }
//hashcode
public native int hashCode();

equals方法在其内部是调用了"=="，所以说在不重写equals方法的情况下，equals方法是比较两个对象是否具有相同的引用，即是否指向了同一个内存地址。而hashCode是一个本地方法，他返回的是这个对象的内存地址。

因为在java中，所有的对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。

在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样

• 对于值对象，==比较的是两个对象的值
• 对于引用对象，比较的是两个对象的地址

如果我们以一个自定义的类作为HashMap的键，比如Person，并重写equals方法

static class Person {
        private String name;
        public Person(String name) {
            this.name = name;
        }
        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Person) {
                Person person = (Person) obj;
                return name.equals(person.name);
            }
            return false;
        }
    }

在我们调用HashMap的相关方法时，可能会产生不符合预期的效果

Person person1 = new Person("小白");
        Person person2 = new Person("小白");
        Map<Person, Integer> hashMap = new HashMap<>();
        hashMap.put(person1, 1);
        System.out.println(person1.equals(person2));//true
        System.out.println(person1.get(person2));//null

主观上，我们规定相同name的Person就应该是相等的，equals方法由于已经重写过，则返回true。当我们用与person1相同的person2去HashMap取值时，应该能取回对应的person1代表的“小白”的值1，结果是没能取回。

因为HashMap是通过key的hashCode去寻找index的，由于Person的HashCode方法没有重写，所以调用get（person2）时，调用的是Object类的HashCode方法，返回的是person2的内存地址，而HashMap中该地址对应的index处肯定没有放入任何数据值，所以会返回null。结果就导致了获取相同name的person值失败的情况，不符合我们的预期。而重写Person的HashCode方法则可以解决这个问题：

@Override
    public int hashCode() {
        return name.hashCode();
    }

7. 如何处理HashMap在多线程环境下存在线程安全问题？

一般在多线程的场景，以下几种方式是线程安全的：

• 使用Collections.synchronizedMap(Map)创建线程安全的map集合
• Hashtable
• ConcurrentHashMap

不过出于线程并发度的原因，应该使用最后的ConcurrentHashMap，他的性能和效率明显高于前两者。

8. Collections.synchronizedMap

在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁mutex，代码如下：

private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;
        private final Map<K,V> m;     // Backing Map
        final Object  mutex;        // Object on which to synchronize
        //构造器1
        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNonNull(m);
            mutex = this;
        }
        //构造器2
        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }
        //...
     }

在调用这个方法的时候就需要传入一个Map，可以看到有两个构造器，如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。

如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象，就是上面的Map。

创建出synchronizedMap之后，再操作map的时候，就会对方法上锁，比如下列方法：

public int size() {
            synchronized (mutex) {return m.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        }
        public boolean containsKey(Object key) {
            synchronized (mutex) {return m.containsKey(key);}
        }
        public boolean containsValue(Object value) {
            synchronized (mutex) {return m.containsValue(value);}
        }
        public V get(Object key) {
            synchronized (mutex) {return m.get(key);}
        }
        public V put(K key, V value) {
            synchronized (mutex) {return m.put(key, value);}
        }
        public V remove(Object key) {
            synchronized (mutex) {return m.remove(key);}
        }
        public void clear() {
            synchronized (mutex) {m.clear();}
        }l

9. HashTable

Hashtable 是使用 synchronized来实现线程安全的，给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争激烈的多线程场景中性能就会非常差。

跟HashMap相比Hashtable是线程安全的，适合在多线程的情况下使用。但是Hashtable在对数据操作的时候都会上锁，所以效率比较低下，比如下面的put（）方法：

public synchronized V put(K key, V value) {
        //Hashtable是不允许值为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;
    }

HashMap与HashTable有什么不同？

Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。

Hashtable在put空值的时候会直接抛空指针异常（如上面的代码所示），但是HashMap却做了特殊处理：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这是因为Hashtable使用的是安全失败机制（fail-safe），这种机制会使你此次读到的数据不一定是最新的数据。如果你使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，ConcurrentHashMap同理。

安全失败机制（fail-safe）

• java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

当需要对集合进行遍历的时候，会先将当前的 map 复制一份，然后遍历的就是这个集合，当其他线程对这个集合做操作时，并不会影响遍历过程。当两个线程，一个线程在读，一个线程在操作集合，就会出现读出来的数据和集合中实际的数据不一致的问题。

快速失败机制（fail—fast）

• java.util包下的容器都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

Tip：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

HashMap与HashTable还有其他区别：

• 实现方式不同

Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。

• 初始化容量不同

HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。

• 扩容机制不同

当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。

• 迭代器不同

• HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。所以，当其他线程改变了HashMap 的结构，如：增加、删除元素，将会抛出异常，而 Hashtable 则不会。

10. ConcurrentHashMap

（1）jdk1.7中的ConcurrentHashMap

1.数据结构

JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即 ConcurrentHashMap 把哈希桶数组切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。

如下图所示，首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。

Segment 是 ConcurrentHashMap 的一个内部类。主要的组成如下：

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    private static final long serialVersionUID = 2249069246763182397L;
    //和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
    transient volatile HashEntry<K,V>[] table;
    
    transient int count;
    //记得快速失败（fail—fast）么？
    transient int modCount;
    // 大小
    transient int threshold;
    //负载因子
    final float loadFactor;
}

其中，用 volatile 修饰了 HashEntry 的数据 value 和 下一个节点 next，保证了多线程环境下数据获取时的可见性。Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。Segment 默认为 16，也就是并发度为 16。

2.高并发度的保证

原理上来说，ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。如果容量大小是16他的并发度就是16，可以同时允许16个线程操作16个Segment而且还是线程安全的。

3.put逻辑

public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();//这就是为啥他不可以put null值的原因
    int hash = hash(key);
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          
         (segments, (j << SSHIFT) + SBASE)) == null) 
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

先定位到Segment，然后再进行put操作

• 加锁
• 首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，下一步
• 尝试利用 scanAndLockForPut() 自旋获取锁
• 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。
• 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry
• 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value
• 否则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容
• 释放锁

4.get逻辑

get 逻辑比较简单，只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。

由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。

ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。

Segment并发访问的问题

由于jdk1.7是数组加链表的方式，在去查询的时候，需要遍历链表，效率很低。

（2）jdk1.8中的ConcurrentHashMap

在数据结构上， JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的Node数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用 CAS + synchronized实现更加细粒度的锁。

将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点（红黑树的根节点），就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。

1.put逻辑

• 根据 key 计算出 hashcode 。
• 判断是否需要进行初始化。
• 定位到 Node，拿到首节点 f，判断首节点 f： 如果为 null ，则通过 CAS 的方式尝试添加； 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容； 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入
• 当在链表长度达到 8 的时候，将链表转换为红黑树

2.get逻辑

j.k1.8的get 方法同样不需要加锁。因为 Node 的元素 value 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。

• 根据 key 计算出 hash 值，判断数组是否为空；
• 如果是首节点，就直接返回；
• 如果是红黑树结构，就从红黑树里面查询；
• 如果是链表结构，循环遍历判断。

get方法不需要加锁与 volatile 修饰的哈希桶数组有关吗？

没有关系。哈希桶数组table用 volatile 修饰主要是保证在数组扩容的时候保证可见性。

（3）JDK1.8 中为什么使用内置锁synchronized替换可重入锁ReentrantLock？

在 JDK1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。

减少内存开销 。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承 AQS 来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。

（4）ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？

1.value不能为 null

我们先来说value 为什么不能为 null。因为 ConcurrentHashMap 是用于多线程的 ，如果ConcurrentHashMap.get(key)得到了 null ，这就无法判断，是映射的value是 null ，还是没有找到对应的key而为 null ，就有了二义性。

而用于单线程状态的 HashMap 却可以用containsKey(key) 去判断到底是否包含了这个null。

2.key不能为 null

作者Doug的观点：不管容器是否考虑了线程安全问题，都不应该允许null值的出现。他觉得在现有的某些集合里面允许了null值的出现，是集合的设计问题。所以ConcurrentHashMap在设计之初就不允许了 null的key存在，源码不支持key为null。

（5）ConcurrentHashMap 的并发度是什么？

并发度可以理解为程序运行时能够同时更新 ConccurentHashMap且不产生锁竞争的最大线程数。在JDK1.7中，实际上就是ConcurrentHashMap中的分段锁个数，即Segment[]的数组长度，默认是16，这个值可以在构造函数中设置。

如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度，也就是比如你设置的值是17，那么实际并发度是32。

如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPU cache命中率会下降，从而引起程序性能下降。

在JDK1.8中，已经摒弃了Segment的概念，选择了Node数组+链表+红黑树结构，并发度大小依赖于数组的大小。

（6）JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别？

数据结构：取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。

保证线程安全机制：JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+synchronized 保证线程安全。

锁的粒度：JDK1.7 是对需要进行数据操作的 Segment 加锁，JDK1.8 调整为对每个数组元素加锁（Node）。

链表转化为红黑树：定位节点的 hash 算法简化会带来弊端，hash 冲突加剧，因此在链表节点数量大于 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储。

查询时间复杂度：从 JDK1.7的遍历链表O(n)， JDK1.8 变成遍历红黑树O(logN)。

（7）ConcurrentHashMap 和 Hashtable 的效率哪个更高？为什么？

ConcurrentHashMap 的效率要高于 Hashtable，因为 Hashtable 给整个哈希表加了一把大锁从而实现线程安全。而ConcurrentHashMap 的锁粒度更低，在 JDK1.7 中采用分段锁实现线程安全，在 JDK1.8 中采用CAS+synchronized实现线程安全。

11. HashMap与其他Map的区别

(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

看到这里的小伙伴，给个关注+点赞呀！！！