java Map及其实现类的底层原理

笔记来源： 尚硅谷

一、Map接口及其多个实现类的对比

首先看下Map及其实现类的类图关系：

Map：双列数据，存储key-value对的数据
|实现类 |含义 |
|:----|:----|:----|
|HashMap |一般来说作为Map的主要实现类， 线程不安全 ， 效率高 ， 可以存储null的key和value
① JDK7及以前：数组+链表
② JDK8：数组+链表+红黑树 |
|LinkedHashMap |保证在遍历map元素时，可以按照添加的顺序实现遍历。在原有的HashMap基础上，添加了一对指针，指向前一个和后一个元素。对于频繁的遍历操作，此类执行效率高于HashMap |
|Hashtable |古老的实现类【甚至命名都不规范】，现在已经不怎么用了， 线程安全，效率低，不能存储null的key和value |
|TreeMap |存储有序的键值对，实现排序遍历【按照key排】，底层使用红黑树 |
|Properties |Hashtable子类，常用来处理配置文件，key和value都是string类型 |

常见面试题：

• HashMap的底层实现原理

• HashMap 和 Hashtable异同

• ConcurrentHashMap 与 Hashtable区别

二、Map中存储的key-value特点

1. Map中的key是无序的，不可重复的 --> key所在的类要重写equals()和hashCode()方法【以HashMap为例】

2. Map中的value是无序的，可重复的 --> value所在类要重写equals()fangfa1

一个键值对：key-value构成了一个Entry对象，是无序不可重复的，用set存放

三、HashMap在JDK7中的底层原理

HashMap map = new HashMap(); 

在实例化以后，底层创建了长度是16的一维数组 Entry[] table.

map.put(key1,value1) 

调用key1 所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。

① 如果此位置数据为空，则key1-value1添加成功 【情况1】
② 如果此位置数据不为空，(意味者此位置上存在一个或多个数据(以链表形式存在))，比较key1与已经存在的一个或多个数据的哈希值，

• 如果key1的哈希值与已经存在的哈希值都不相同，此时添加成功 【情况2】
• 如果key1的哈希值与已经存在的哈希值都相同，继续比较，调用key1所在类的equals方 法，如果equals返回false，则key1-value1添加成功；如果equals返回true，则用value1替换相同key的value值 【情况3】

补充：关于 情况2 和 情况3 ：此时key1-value1 和原来的数据以 链表 的方式存储。【见下图】
在不断的添加过程中，会涉及到扩容问题，默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

四、HashMap在JDK8中的底层原理

jdk8相较于jdk7在底层实现方面的不同：

1. new HashMap()：底层没有创建一个长度为16的数组 
2. jdk8 底层的数组是：Node[]，而非Entry[] 
3. 首次调用put()方法时，底层创建长度为16的数组 
4. 原来jdk7底层结构只有数组+链表，jdk8是数组+链表+红黑树 
   当数组的某一个索引位置上的元素以链表形式存在的个数 > 8，且 
   当前数组的长度 > 64时，此时此索引位置上的所有数据改为使用红黑树 
   存储【方便查找】。 

五、HashMap在JDK7中的底层源码

面试题：
谈谈你对 HashMap 中 put/get 方法的认识？如果了解再谈谈HashMap的扩容机制？默认大小是多少？什么是负载因子（或填充比）？什么是吞吐临界值（或阈值、threshold）?

HashMap源码中的重要常量 
DEFAULT_INITIAL_CAPACITY: HashMap的默认容量，16 
MAXIMUM_ CAPACITY : HashMap的最大支持容量，2^30 
DEFAULT_LOAD_FACTOR: HashMap的默认加载因子 0.75 
TREEIFY_THRESHOLD: Bucket中链表长度大于该默认值 8，转化为红黑树 
UNTREEIFY_THRESHOLD: Bucket中红 黑树存储的Node小于该默认值，转化为链表 
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。(当桶中Node的 
数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行 
resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4 
倍。) 

table: 存储元素的数组，总是2的n次幂 
entrySet: 存储具体元素的集 
size: HashMap中 存储的键值对的数量 
modCount: HashMap扩 容和结构改变的次数。 
threshold: 扩容的临界值，=容量*填充因子 
loadFactor: 填充因子 

5.1 构造器

//DEFAULT_INITIAL_CAPACITY: HashMap的默认容量，16 
//DEFAULT_LOAD_FACTOR: HashMap的默认加载因子，0.75 
public HashMap() ( 
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 
} 
public HashMap(int initialCapacity, float loadFactor) { 
      if (initialCapacity < 0) 
          throw new IllegalArgumentException("Illegal initial capacity: " + 
                                             initialCapacity); 
      if (initialCapacity > MAXIMUM_CAPACITY) 
          initialCapacity = MAXIMUM_CAPACITY; 
      if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
          throw new IllegalArgumentException("Illegal load factor: " + 
                                             loadFactor); 
      // 找到一个大于等于initialCapacity并且是2的指数的值作为初始容量 
      // 所以你如果传进来15，那么容量为16 
      int capacity = 1; 
      while (capacity < initialCapacity) 
          capacity <<= 1; 

      this.loadFactor = loadFactor;//加载因子，默认0.75 
      // 初始化阈值【当占用到阈值的时候扩容】 
      threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 
      // 初始化Entry数组 
      table = new Entry[capacity]; 
      useAltHashing = sun.misc.VM.isBooted() && 
              (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 
      init(); 
  } 

5.2 put方法

解析都在代码里 ↓

public V put(K key, V value) { 
  //如果key为null，其实也往里面放了 
  if (key == null)  
      return putForNullKey(value); 
  //计算当前key的哈希值 
  int hash = hash(key); 
  // 查找对应的数组下标【hash & (length-1)】 
  int i = indexFor(hash, table.length); 
   
  for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
      //如果在i位置上已经有元素了，对比这个位置上的所有元素 
      Object k; 
      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
          //覆盖原有value 
          V oldValue = e.value; 
          e.value = value; 
          e.recordAccess(this); 
          return oldValue; 
      } 
  } 
  // 没有在相同hash值的链表中找到key相同的节点 
  modCount++; 
  addEntry(hash, key, value, i); // 在i位置对应的链表上添加一个节点 
  return null; 
} 

void addEntry(int hash, K key, V value, int bucketIndex) { 
    //如果数据大小已经超过阈值[16*0.75]并且数组对应的bucket不为空，则需要扩容 
    if ((size >= threshold) && (null != table[bucketIndex])) { 
        // 扩容2倍 
        resize(2 * table.length);  
        // key为null的时，hash值设为0 
        hash = (null != key) ? hash(key) : 0;  
        // 确定是哪一个链表（bucket下标） 
        bucketIndex = indexFor(hash, table.length);  
    } 
    createEntry(hash, key, value, bucketIndex); 
} 
//这里需要注意！！！ 
//使用的是头插法 
void createEntry(int hash, K key, V value, int bucketIndex) { 
      Entry<K,V> e = table[bucketIndex]; 
      table[bucketIndex] = new Entry<>(hash, key, value, e); 
      size++; 
  } 
private static class Entry<K,V> implements Map.Entry<K,V> { 
    final int hash; 
    final K key; 
    V value; 
    Entry<K,V> next; 
    protected Entry(int hash, K key, V value, Entry<K,V> next) { 
        this.hash = hash; 
        this.key =  key; 
        this.value = value; 
        this.next = next; 
    } 
    //略 
    } 

六、HashMap在JDK8的源码分析

重要常量：

DEFAULT_INITIAL_CAPACITY: HashMap的默认容量，16 
MAXIMUM_ CAPACITY : HashMap的最大支持容量，2^30 
DEFAULT_LOAD_FACTOR: HashMap的默认加载因子0.75 
TREEIFY_THRESHOLD: Bucket中链表长度大于该默认值，转化为红黑树 

面试题：为什么不在HashMap快满的时候再扩？

尽量让数组出现链表的情况少一些

6.1 构造器

/** 
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity 
 * (16) and the default load factor (0.75). 
 */ 
public HashMap() { 
    // all other fields defaulted 
    //底层并没有创建长度为16的数组 
    this.loadFactor = DEFAULT_LOAD_FACTOR;  
} 

在JDK8中已经不是Entry数组了，而是Node数组

transient Node<K,V>[] table; 

6.2 put

public V put(K key, V value) { 
    return putVal(hash(key), key, value, false, true); 
} 

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
               boolean evict) { 
    Node<K,V>[] tab; Node<K,V> p; int n, i; 
    if ((tab = table) == null || (n = tab.length) == 0) 
        //首次调用或者长度为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)))) 
            //hash值相等 
            e = p; 
        else if (p instanceof TreeNode) 
            //是否红黑树 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
        else { 
            //循环判断有没有hash相等的 
            for (int binCount = 0; ; ++binCount) { 
                if ((e = p.next) == null) { 
                    //尾插法 
                    p.next = newNode(hash, key, value, null); 
                    //当链表长度超过8时，变成红黑树 
                    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; 
} 
//当数组某个位置链表超过8时，且当前数组长度超过64时，做成红黑树 
final void treeifyBin(Node<K,V>[] tab, int hash) { 
    int n, index; Node<K,V> e; 
    //MIN_TREEIFY_CAPACITY=64 
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 
        resize(); 
    else if ((e = tab[index = (n - 1) & hash]) != null) { 
        TreeNode<K,V> hd = null, tl = null; 
        do { 
            TreeNode<K,V> p = replacementTreeNode(e, null); 
            if (tl == null) 
                hd = p; 
            else { 
                p.prev = tl; 
                tl.next = p; 
            } 
            tl = p; 
        } while ((e = e.next) != null); 
        if ((tab[index] = hd) != null) 
            hd.treeify(tab); 
    } 
} 

七、LinkedHashMap的底层实现

LinkedHashMap 没有重写 put 和 putVal，而是重写了 putVal 中调用的 newNode 方法：

//专门用了一个数据结构 LinkedHashMap.Entry<K,V> 存储节点，并且存储了前一个和下一个元素 
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { 
    LinkedHashMap.Entry<K,V> p = 
        new LinkedHashMap.Entry<K,V>(hash, key, value, e); 
    linkNodeLast(p); 
    return p; 
} 
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); 
    } 
}