一篇文章带您读懂Map集合（源码分析）

今天要分享的Java集合是Map，主要是针对它的常见实现类HashMap进行讲解（jdk1.8）

什么是Map核心方法源码剖析1.文档注释2.成员变量3.构造方法4.put()5.get()

什么是Map

  Map是非线性数据结构的主要实现，用来存放一组键-值型数据，我们称之为散列表。在其他语言中，也被称为字典。
  HashMap是一个非常重要的数据结构，在我们的项目中有大量的运用，或充当参数，或用于缓存。而在面试中，HashMap也几乎成为了一个“必考项”，所以今天我们就从源码的角度，对这种数据结构进行剖析。
  首先我们先就使用上，给出几个先入为主的概念。有了概念，再去看源码就会容易很多。
  HashMap的查询速度是O(1)，它为什么会这么快呢？因为散列表利用的是数组支持按下标随机访问的特性，所以散列表其实是对数组的一种扩充，是由数组演化而来的。
  我们来举一个例子，A班一共有64个学生，学号是唯一的9位数。在一场期末考试中，如果我们想知道一个学生的成绩，那么就可以通过学号来定位学生，然后获取所有的考试信息。为了便于存储和查询，我们将学生的学号，通过编码映射到下标从1-63的数组中。

  将例子和HashMap中的概念对应起来：学号就是键(key),也叫做关键字，学生的信息就是值,将学号转换成数组下标的映射方法就叫做散列函数（散列函数是散列表的核心），散列函数计算得到的值就叫作散列值，也叫做Hash值或哈希值。
  如果这个班扩充到了100个人，存储成绩的方法不变，那么一定会有至少2个同学的成绩经过散列函数计算出的值相同。这种现象叫做散列冲突。为了解决散列冲突，不出现数据相互覆盖的情况，散列表会将这两个学生的信息组成一个链表，存储在数组中，从而保存多个同学的考试信息，这种解决散列冲突方法叫做链表法。（解决散列冲突的方法不止这一种，还有其他的方法，比如线性探测法）。
  对这些只要有一个大致的印象就可以，接下来我们会通过剖析源码的方式，对散列表的工作原理进行深入的分析。

 

核心方法源码剖析

  这一部分，选取了HashMap的一些核心内容进行讲解。分别是：文档注释,成员变量,构造方法，put()、hash()、get()、remove()。

1.文档注释

  permits null values and the null key
  允许存储null值和null键

  The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.
  HashMap近似于Hashtable，除了它不同步并且允许null值

  This class makes no guarantees as to the order of the map
  这个类存储数据是无序的

  An instance of HashMap has two parameters that affect its performance: initial capacity and load factor
  一个散列表有两个影响其性能的参数：初始值和负载因子

  so that the hash table has approximately twice the number of buckets
  每次扩容2倍

2.成员变量

 1// 默认容量
 2static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
 3
 4// 最大容量
 5static final int MAXIMUM_CAPACITY = 1 << 30;
 6
 7// 负载因子：已用空间 / 总空间，负载因子平衡了时间和空间成本，如果负载因子过高，导致空间成本减少，查找成本增加，反之亦然。
 8static final float DEFAULT_LOAD_FACTOR = 0.75f;
 9
10// 一个哈系桶存储的元素超过8，就会将链表转换成红黑二叉树
11static final int TREEIFY_THRESHOLD = 8;
12
13// 一个哈希桶存储的元素小于6，并且是红黑二叉树存储，那么此时就会将红黑二叉树重新转换成链表
14static final int UNTREEIFY_THRESHOLD = 6;
15
16// 数据量阈值，数据量只有大于这一个值，才会发生树化
17static final int MIN_TREEIFY_CAPACITY = 64;

3.构造方法

HashMap的构造方法有4种,我们一般不会修改它的负载因子，常用的构造方法只有无参构造和传入初始值的构造方法。

1HashMap()
2HashMap(int initialCapacity)
3HashMap(int initialCapacity, float loadFactor)
4HashMap(Map<? extends K,? extends V> m)

4.put()

  put中有一个核心的方法，hash()，即散列方法

1public V put(K key, V value) {
2   return putVal(hash(key), key, value, false, true);
3}
4
5static final int hash(Object key) {
6    int h;
7    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
8}

  从hash方法中可以看出，如果传入的key是null，就会固定的返回0位置。如果传入的key不是null，那么就会取key的hashCode方法的返回值，记做h，返回h与h高16位的异或值。
  hash()方法的这段代码，又被称为扰动函数，我们可以思考一下，h的值是一个int,它的范围是[-2147483648, 2147483647],大概包含了40亿的映射空间。如果直接存到内存中，肯定是存不下的，而且HashMap的初始值只有16，那么我们就需要将h映射到这16个哈希桶中，可以直接取模，但是这样的效率不是很高，所以这里jdk使用了位与的方法，代码抽象如下：

1private int getIndex(int length, int h){
2    return h & (length - 1);
3}

  这里可以解释一下，为什么HashMap要求初始值是2的整次幂？，这样length - 1正好相当于一个低位掩码，只截取了低位的值.

  但是这里有一个问题，即使我们的散列函数设计的再松散，那么当屏蔽掉高位，只看低位的时候，还是会容易发生散列冲突。此时扰动函数的价值就体现出来了，它将自身的高半区(32bit)和低半区(32bit)做异或，这样既增加了随机性，又将高位的信息变相的参杂了进来。
  这里的getIndex函数除了位运算性能高，还有一个好处，这里扩容前后，h的值是不变的，只跟key有关。那么length - 1的值，只会增加一个高位1，所以经过getIndex计算的值，有一定几率保持不变（增加的高位，对应h的位是0），扩容时，就会少进行一些数据的搬运，即扩容时数据是黏性的。
  讲完了hash()，put()方法的核心思想就差不多讲完了，接下来我们将屏蔽一些实现细节，来讲一下剩下的putVal()。

 

 1final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
 2    Node<K,V>[] tab;
 3    Node<K,V> p;
 4     int n, i;
 5    // 当散列表为null的时候，调用resize()进行初始化
 6    if ((tab = table) == null || (n = tab.length) == 0)
 7        n = (tab = resize()).length;
 8    // 如果没有发生哈希碰撞，直接将元素存进哈希桶
 9    if ((p = tab[i = (n - 1) & hash]) == null)
10        tab[i] = newNode(hash, key, value, null);
11    else {
12        // 如果发生了哈希碰撞
13        Node<K,V> e; K k;
14        if (p.hash == hash &&
15            ((k = p.key) == key || (key != null && key.equals(k))))
16            // 记录要插入的元素
17            e = p;
18        else if (p instanceof TreeNode)
19            // 如果是树结构，就调用树的插入方法
20            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
21        else {
22            // 如果是链表结构，就调用链表的插入方法
23            for (int binCount = 0; ; ++binCount) {
24                if ((e = p.next) == null) {
25                    p.next = newNode(hash, key, value, null);
26                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
27                        treeifyBin(tab, hash);
28                    break;
29                }
30                if (e.hash == hash &&
31                    ((k = e.key) == key || (key != null && key.equals(k))))
32                    break;
33                p = e;
34            }
35        }
36        if (e != null) { // 覆盖元素
37            V oldValue = e.value;
38            if (!onlyIfAbsent || oldValue == null)
39                e.value = value;
40            afterNodeAccess(e);
41            return oldValue;
42        }
43    }
44    ++modCount;
45    if (++size > threshold)
46        resize();
47    afterNodeInsertion(evict);
48    return null;
49}    

  这里的扩容方法是resize()，每次扩容2倍，采用的也是数据搬运的方式，所以我们要尽可能的去避免HashMap的扩容。

5.get()

 1public V get(Object key) {
 2    Node<K,V> e;
 3    return (e = getNode(hash(key), key)) == null ? null : e.value;
 4}
 5
 6final Node<K,V> getNode(int hash, Object key) {
 7    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 8    if ((tab = table) != null && (n = tab.length) > 0 &&
 9        (first = tab[(n - 1) & hash]) != null) {
10        // 如果在桶的首位就可以找到，那么就直接返回（提升效率，哈希冲突并不那么容易出现）
11        if (first.hash == hash && // always check first node
12            ((k = first.key) == key || (key != null && key.equals(k))))
13            return first;
14        if ((e = first.next) != null) {
15            // 根据节点类型，在红黑二叉树或者链表中查询数据
16            if (first instanceof TreeNode)
17                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
18            do {
19                if (e.hash == hash &&
20                    ((k = e.key) == key || (key != null && key.equals(k))))
21                    return e;
22            } while ((e = e.next) != null);
23        }
24    }
25    return null;
26}

  get()的思想和put()类似，根据不同的Node类型，进行查找

  最后，期待您的订阅和点赞，专栏每周都会更新，希望可以和您一起进步，同时也期待您的批评与指正！