Hashmap是Java中非常常用的容器，在网上看见很多源码分析都是以前版本的，本文章结合JDK1.8的源码对HashMap进行简单的分析，在学习的过程中发现HashMap的源码远比前面的List要复杂的多，花了好长时间才理清关系。

O、哈希函数的构造方法与冲突处理

在面试的时候经常见到哈希冲突的解决方法，所以在分析HashMap之前，加入了这部分。

哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表。这种方法的基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为f(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=f(k)，从而达到按关键字直接存取元素的目的。

1、哈希函数的构造方法

构造哈希函数的原则是：

函数本身便于计算
计算出来的地址分布均匀，即对任一关键字k，f(k) 对应不同地址的概率相等，目的是尽可能减少冲突。

主要有一下集中方法：

数字分析法
平方取中法
分段叠加法
除留余数法
伪随机数法

1.1、数字分析法

如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。例如，有80个记录，关键字为8位十进制整数d1d2d3…d7d8，如哈希表长取100，则哈希表的地址空间为：00~99。假设经过分析，各关键字中 d4和d7的取值分布较均匀，则哈希函数为：h(key)=h(d1d2d3…d7d8)=d4d7。例如，h(81346532)=43，h(81301367)=06。相反，假设经过分析，各关键字中 d1和d8的取值分布极不均匀， d1 都等于5，d8 都等于2，此时，如果哈希函数为：h(key)=h(d1d2d3…d7d8)=d1d8，则所有关键字的地址码都是52，显然不可取。

1.2、平方取中法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址

关键字	内部编码	内部编码的平方值	H(k)关键字的哈希地址
KEYA	11050201	122157778355001	778
KYAB	11250102	126564795010404	795
AKEY	01110525	001233265775625	265
BKEY	02110525	004454315775625	315

1.3、分段叠加法

这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有折叠法与移位法。移位法是将分割后的每部分低位对齐相加，折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。例如：key=12360324711202065,哈希表长度为1000，则应把关键字分成3位一段，在此舍去最低的两位65，分别进行移位叠加和折叠叠加，求得哈希地址为1105和907

1 2 3 1 2 3

6 0 3 3 0 6

2 4 7 2 4 7

1 1 2 2 1 1

+) 0 2 0 +) 0 2 0

————————            —————————

      1   1   0   5                         9   0   7

(a)移位叠加 (b) 折叠叠加

1.4、除留余数法

假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为

h（k）=k % p ，其中%为模p取余运算。

例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有

h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   

h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   

h(46)=46 % 7=4

此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：

h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    

h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   

h(46)=46 % 13=7

1.5、伪随机数法

采用一个伪随机函数做哈希函数，即h(key)=random(key)。

在实际应用中，应根据具体情况，灵活采用不同的方法，并用实际数据测试它的性能，以便做出正确判定。通常应考虑以下五个因素：

l 计算哈希函数所需时间（简单）。

l 关键字的长度。

l 哈希表大小。

l 关键字分布情况。

l 记录查找频率

2、哈希冲突的解决方法

通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：

开放地址法
再哈希法
链地址法
建立公共溢出区

2.1、开放地址法

其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。

2.2、再哈希法

这种方法是同时构造多个不同的哈希函数：

Hi=RH1（key）  i=1，2，…，k

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

2.3、链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

下面要介绍的HashMap采用的就是这种方法

3.4、建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

参考地址http://blog.sina.com.cn/s/blog_6fd335bb0100v1ks.html

下面开始正式分析Java中的HashMap源码

一、基本参数与构造函数

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {  
  
	private static final long serialVersionUID = 362498820763181265L;  
      
      
    /* ---------------- Fields -------------- */  
  
    //存储节点的table数组，第一次使用的时候初始化，必要时resize，长度总是2的幂 
    transient Node<K,V>[] table;  
  
    //缓存entrySet，用于keySet() and values()  
    transient Set<Map.Entry<K,V>> entrySet;  
  
    //容器中元素的个数  
    transient int size;  
  
    //每次扩容和更改map结构的计数器  
    transient int modCount;  
  
    //阈值，当实际大小超过阈值时，会进行扩容  
    int threshold;  
  
    //装载因子  
    final float loadFactor;      
      
      
  
    //默认的初始容量，必须是2的幂次，出于优化考虑，默认16  
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
  
    //默认的最大容量  
    static final int MAXIMUM_CAPACITY = 1 << 30;  
  
    //默认的装载因子，在无参构造器中默认设为该值  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  
  
    //阈值，当链表中节点数大于该阈值后就会转变成红黑树  
    static final int TREEIFY_THRESHOLD = 8;  
  
    //与上一个阈值相反，当小于这个阈值后转变回链表  
    static final int UNTREEIFY_THRESHOLD = 6;  
  
    // 看源码注释里说是：树的最小的容量，至少是 4 x TREEIFY_THRESHOLD = 32 然后为了避免(resizing 和 treeification thresholds) 设置成64  
    static final int MIN_TREEIFY_CAPACITY = 64;  
  
  
  
    //基本哈希容器节点 实现Map.Entry接口  
    static class Node<K,V> implements Map.Entry<K,V> {  
        final int hash;//不可变的哈希值，由关键字key得来  
        final K key;//不可变的关键字  
        V value;  
        Node<K,V> next;  
  
        Node(int hash, K key, V value, Node<K,V> next) {  
            this.hash = hash;  
            this.key = key;  
            this.value = value;  
            this.next = next;  
        }  
  
        public final K getKey()        { return key; }  
        public final V getValue()      { return value; }  
        public final String toString() { return key + "=" + value; }  
  
        public final int hashCode() {//Node对象的哈希值，关键字key的hashCode()与值value的hashCode()做异或运算    
            return Objects.hashCode(key) ^ Objects.hashCode(value);  
        }  
  
        public final V setValue(V newValue) {  
            V oldValue = value;  
            value = newValue;  
            return oldValue;  
        }  
  
        public final boolean equals(Object o) {//对象相同或同类型且key-value均相同，则返回true    
            if (o == this)  
                return true;  
            if (o instanceof Map.Entry) {  
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;  
                if (Objects.equals(key, e.getKey()) &&  
                    Objects.equals(value, e.getValue()))  
                    return true;  
            }  
            return false;  
        }  
    }  
      
    /* 
     * 构造函数 
     */  
      
    public HashMap(int initialCapacity, float loadFactor) {//给定初始容量和装载因子，构造一个空的HashMap  
        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);  
        this.loadFactor = loadFactor;  
        this.threshold = tableSizeFor(initialCapacity);//根据指定的容量计算容量，因为必须是2的幂次，虽然将该值赋给threshold，但表示的依然是容量，到时候会重新计算阈值  
    }  
  
    public HashMap(int initialCapacity) {//指定初始容量，和默认装载因子0.75构造空HashMap  
        this(initialCapacity, DEFAULT_LOAD_FACTOR);  
    }  
  
    public HashMap() {//无参，使用默认的初始容量16,和装载因子0.75构造空的HashMap  
        this.loadFactor = DEFAULT_LOAD_FACTOR;   
    }  
  
    public HashMap(Map<? extends K, ? extends V> m) {//构造一个和给定Map映射相同的HashMap，默认装载因子，初始空间以足够存放给定Map中的映射为准   
        this.loadFactor = DEFAULT_LOAD_FACTOR;  
        putMapEntries(m, false);  
    }      
}

上面给出了HashMap的定义，和前面的基本参数，内部节点类的定义和4个构造函数。

1、table数组

该数组类似于一个桶，通过对key值hash运算得到index值，就该节点在数组中的下标，所有index值相同的节点形成链表或者红黑树，而table[index]则指向该链表或者红黑树的头节点。最理想的状态就是每个index中只有一个元素，这样查找一个key的时候，通过O(1)时间计算出index，就可以直接找到该key对应的节点。

2、容量、装载因子和阈值

个人人为这三个参数是HashMap中最重要的三个参数。

2.1、容量Capacity

table数组的大小，一定是2的幂。
如果在构造函数中指定了容量，会调用tableSizeFor()方法来计算出保证是2的倍数的容量:

this.threshold = tableSizeFor(initialCapacity);

虽然将该值赋给threshold，但表示的依然是容量，到时候会重新计算阈值。
如果没有指定容量，会使用默认的16，在第一次加入元素的时候会通过resize方法来创建该数组。

初始化之后，每次map中元素超过阈值，容量都会*2，直到达到设定的最大容量。

//返回大于指定容量且是2的幂次的值，比如给定999，返回1024  
static final int tableSizeFor(int cap) {  
    int n = cap - 1;  
    n |= n >>> 1;  
    n |= n >>> 2;  
    n |= n >>> 4;  
    n |= n >>> 8;  
    n |= n >>> 16;  
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;  
}

阿里的Java开发手册中提到，【推荐】集合初始化时，指定集合初始值的大小。

说明： HashMap 使用 HashMap(int initialCapacity) 初始化，

正例：initialCapacity = (需要存储的元素个数 / 负载因子) + 1。注意负载因子（即 loader factor）默认为 0.75，如果暂时无法确定初始值大小，请设置为 16。

反例： HashMap 需要放置 1024 个元素，由于没有设置容量初始大小，随着元素不断增加，容量 7 次被迫扩大， resize 需要重建 hash 表，严重影响性能。

2.2、阈值threshold

一个临界值，当map中的节点个数超过这个临界值的时候，就要调用resize方法来将table数组扩大2倍，同时阈值也会扩大2倍。
默认情况下threshold=DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY，之后在每次容量翻倍的时候，阈值也跟着翻倍。
如果在构造函数中指定了容量，那么会调用tableSizeFor方法来计算然后把计算结构赋值给阈值。最后初始化之后再重新计算阈值。

float ft = (float)newCap * loadFactor;

2.3、装载因子loadFactor

用来计算阈值。举个例子:

如果装载因子是默认的0.75，HashMap(16)的时候，占16个内存空间，实际上只用到了12个，超过12个就扩容。如果负载因子是1的话，HashMap(16)的时候，占16个内存空间，实际上会填满16个以后才会扩容。

3、构造函数

一共有4个构造函数，前面三个都是构造一个空的HashMap,可以指定容量和装载因子，或者直接使用默认值。第四个构造一个和给定Map映射相同的HashMap，默认装载因子，初始空间以足够存放给定Map中的映射为准，调用putMapEntries方法下面再详细分析。

二、关键方法

个人人为HashMap最关键的两个方法就是hash函数的实现和resize方法。每次put元素的时候都要先调用hash函数来去诶的那个元素存储的位置，而resize方法用于新建或扩大table的容量，下面主要分析这两个方法。

1、hash函数的实现和put()方法

put()方法的完整过程为：

如果table数组为空，那么调用resize()方法新建数组
对key的hashCode()做hash，然后再计算index;
如果没碰撞直接放到bucket里；
如果碰撞了，放在以链表的形式存在buckets后；
如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
如果节点已经存在就替换old value(保证key的唯一性)
如果bucket满了(超过load factor*current capacity)，就要resize

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

 /* 
  * 实现Map.put以及相关方法 
  * 向map中加入个节点 
  * 没有分析onlyIfAbsent和evict 
  */       
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {  
    Node<K, V>[] tab;//指向table数组  
    Node<K, V> p;//对应下标中的第一个节点，为null说明没有碰撞，不为null代表链表第一个元素或红黑树根节点  
    int n, i;//n为table数组的长度，2的幂次; i表示对应的下标index  

    if ((tab = table) == null || (n = tab.length) == 0) // 如果table为空即第一次添加元素，则进行初始化  
        n = (tab = resize()).length;  

    /* 
     * 计算下标，根据hash与n计算index 
     * 公式:i = (n - 1) & hash; 
     */  

    // p=table[i]; 对应下标中的第一个节点  

    if ((p = tab[i = (n - 1) & hash]) == null) // p为null说明没有碰撞，  
        tab[i] = newNode(hash, key, value, null);//直接新建一个节点加入就可以了  

    else {// p不为null，说明有碰撞  
        Node<K, V> e;//e，代表map中与给定key值相同的节点  
        K k;//代表e的key  

        // p的关键字与要加入的关键字相同，则p就是要找的e  
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))  
            e = p;  

        // 如果p的类型是红黑树，则向红黑树中查找e  
        else if (p instanceof TreeNode)  
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);  

        // 否则就是链表  
        else {  
            for (int binCount = 0;; ++binCount) {//遍历链表查找e，如果找不到就新建一个  
                if ((e = p.next) == null) {// 如果next为null，说明没有找到  
                    p.next = newNode(hash, key, value, null);// 那么新创建一个节点  
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 加入节点后如果超出树形化阈值  
                        treeifyBin(tab, hash);// 则转换为红黑树  
                    break;  
                }  
                if (e.hash == hash && // 找到关键字相同的节点，退出循环  
                        ((k = e.key) == key || (key != null && key.equals(k))))  
                    break;  

                p = e;  
            }  
        }  
        if (e != null) { //e不为null，说明原来存在对应的key，那么返回原来的值  
            V oldValue = e.value;// 保留原来的值，用于返回  
            if (!onlyIfAbsent || oldValue == null)  
                e.value = value;  
            afterNodeAccess(e);  
            return oldValue;  
        }  
    }  

    //说明新插入了一个节点，返回null  
    ++modCount;  
    if (++size > threshold) // 超过临界值，则resize  
        resize();  
    afterNodeInsertion(evict);  
    return null;  
}

1.1、第一次加入元素

在构造函数中虽然指定了容量，但是并不会初始化table数组，该数组的初始化是在第一次加入元素的时候通过resize()方法完成的:

if ((tab = table) == null || (n = tab.length) == 0) // 如果table为空即第一次添加元素，则进行初始化

n = (tab = resize()).length;

1.2、index的计算

index值决定了加入的元素要放到table数组中的下标.

在调用put(key, value)方法后会首先调用hash(key)计算出key的hash值：

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

先得到key的hashcode即一个int型32为的整数
然后将它的高16位不变，低16位和高16为做异或操作，得到key的hash值。

将hash值传入到putVal()方法中，计算index值：

i = (n - 1) & hash;

其中n为table数组的长度，也就是说它肯定是2的幂次，举个例子，加入n=16，那么n-1=15的二进制表示就是0x0000 1111，可以看出，任何一个2的幂次减1后二进制肯定都是这种形式，它的意义在于，任何一个值和它做&操作，得到的结构肯定都在0~(n-1)之间，也就是说计算出来的下标值肯定数组的合法下标。hash函数的计算过程如下图

2、resize()方法

从上面可以看到，每次加入元素如果table数组为空或者加入之后元素个数超出阈值，都会调用调用resize()方法来进行扩容，它的意义在于使节点均匀分布尽量避免碰撞，这样才能实现较好的查找性能。

先根据容量和阈值确定新的容量和阈值
更新阈值和新容量的table
如果原来的table中元素，那么把原来的元素加入到新的table中

/* 
 * 第一次加入元素或者size超过阈值的时候都会调用该方法初始化或者扩大table的容量 
 */  
final Node<K,V>[] resize() {  
    Node<K,V>[] oldTab = table;  
    int oldCap = (oldTab == null) ? 0 : oldTab.length;  
    int oldThr = threshold;  
    int newCap, newThr = 0;  

    /* 
     * step1: 先根据容量和阈值确定新的容量和阈值 
     */  

    //case1: 如果table已经被初始化，说明不是第一次加入元素  
    if (oldCap > 0) {              
        if (oldCap >= MAXIMUM_CAPACITY) {//如果table的容量已经达到最大值，那么就不再扩容了，碰撞也没办法  
            threshold = Integer.MAX_VALUE;//那么扩大阈值到最大值  
            return oldTab;//原来的table不变  
        }  

        //不然的话table的容量扩大2倍，newCap = oldCap << 1            大部分情况下肯定都是这种情况              
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                 oldCap >= DEFAULT_INITIAL_CAPACITY)  
            newThr = oldThr << 1; //阈值也扩大2倍  
    }          

    //case2: table没有被初始化，但是阈值大于0，说明在构造函数中指定了容量，但是容量存在阈值那个变量上  
    else if (oldThr > 0)  
        newCap = oldThr;//那么将阈值设置为table的容量，下面还会重新计算阈值  

    //case3: table和阈值都没有初始化，说明是无参构造函数  
    else {                 
        newCap = DEFAULT_INITIAL_CAPACITY;//使用默认的初始容量  
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//计算默认的阈值，threshold=load_factor*capacity  
    }  

    //重新计算阈值  
    if (newThr == 0) {  
        float ft = (float)newCap * loadFactor;  
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
                  (int)ft : Integer.MAX_VALUE);  
    }  

    /* 
     * step2: 更新阈值和新容量的table 
     */  
    threshold = newThr;  
    @SuppressWarnings({"rawtypes","unchecked"})  
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
    table = newTab;  


    /* 
     * step3: 如果原来的table中元素，那么把原来的元素加入到新的table中 
     */               
    if (oldTab != null) {  
        for (int j = 0; j < oldCap; ++j) {  
            Node<K,V> e;  //e = oldTab[j]
            if ((e = oldTab[j]) != null) {  
                oldTab[j] = null;  
                if (e.next == null)  //e所在位置没有哈希冲突，只有一个元素，直接计算
                    newTab[e.hash & (newCap - 1)] = e;  
                else if (e instanceof TreeNode)  //e所在位置是一颗红黑树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
                else {// e所在位置是一个链表，则遍历链表
                  	// 根据e.hash & oldCap) == 0，确定放入lo还是hi两个链表
                  	// 其实就是判断e.hash是否大于oldCap
                  	// lo和hi两个链表放分别放在在newTab[j]和newTab[j + oldCap]
                    Node<K,V> loHead = null, loTail = null;  
                    Node<K,V> hiHead = null, hiTail = null;  
                    Node<K,V> next;  
                    do {  
                        next = e.next;  
                        if ((e.hash & oldCap) == 0) {  
                            if (loTail == null)  
                                loHead = e;  
                            else  
                                loTail.next = e;  
                            loTail = e;  
                        }  
                        else {  
                            if (hiTail == null)  
                                hiHead = e;  
                            else  
                                hiTail.next = e;  
                            hiTail = e;  
                        }  
                    } while ((e = next) != null);  
                    if (loTail != null) {  
                        loTail.next = null;  
                        newTab[j] = loHead;  
                    }  
                    if (hiTail != null) {  
                        hiTail.next = null;  
                        newTab[j + oldCap] = hiHead;  
                    }  
                }  
            }  
        }  
    }  
    return newTab;  
}

三、常用方法

上面介绍了两个比较复杂的方法，接下来继续分析Map中比较常见的方法和内部的实现。

1、get()方法和containsKey()方法

这两个方法是最常用的，都是根据给定的key值，一个获取对应的value，一个判断是否存在于Map中，在内部这两个方法都会调用一个finall方法，就是getNode()，也就是查找对应key值的节点。

getNode方法的大致过程：

table里的第一个节点，直接命中；
如果有冲突，则遍历链表或二叉树去查找相同节点
查找节点时先判断hash值是否相等
如果hash值相等，再判断key值是否相等
判断key值相等时，用==或equals或，整个判断条件为：

(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

public V get(Object key) {  
    Node<K,V> e;  
    return (e = getNode(hash(key), key)) == null ? null : e.value;  
}  

public boolean containsKey(Object key) {  
    return getNode(hash(key), key) != null;  
}  

/* 
 * 实现Map.get以及相关方法 
 */  
final Node<K,V> getNode(int hash, Object key) {  
    Node<K,V>[] tab; //指向table数组  
    Node<K,V> first, e; //first为table[index]，即所在数组下标中第一个节点；e用于遍历节点  
    int n; K k;//n为table的长度，k用于指向节点的key  

    if ((tab = table) != null && (n = tab.length) > 0 &&//首先必须保证table数组不为空                 
        (first = tab[(n - 1) & hash]) != null) {//计算下标，保证数组下标中第一个节点不为null不然就肯定找不到直接返回null  

        if (first.hash == hash && // 先检查第一个节点hash值是否相等  
            ((k = first.key) == key || (key != null && key.equals(k))))//再判断key，如果相等直接返回  
            return first;  

        if ((e = first.next) != null) { //第一个不符合，就从下一个开始找  
            if (first instanceof TreeNode)//红黑树 O(logn)  
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);  
            do {//不然就是链表O(n)  
                if (e.hash == hash &&  
                    ((k = e.key) == key || (key != null && key.equals(k))))  
                    return e;  
            } while ((e = e.next) != null);  
        }  
    }  
    return null;  
}

2、putAll()方法

putAll方法用于将一个已有的Map加入现有的Map中，在内部也是调用一个final方法putMapEntries，这个方法也实现了最后一个构造函数。

public void putAll(Map<? extends K, ? extends V> m) {  
    putMapEntries(m, true);  
}  


//用于实现Map.putAll和上面的那个构造函数  
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {  
    int s = m.size();//s代表要加入的元素个数  
    if (s > 0) {  

        if (table == null) { // 如果table为null，说明还没有进行初始化  

            float ft = ((float)s / loadFactor) + 1.0F;//根据s计算容量和阈值  
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?  
                     (int)ft : MAXIMUM_CAPACITY);  
            if (t > threshold)  
                threshold = tableSizeFor(t);  
        }  

        else if (s > threshold)//如果超出阈值，则进行扩容  
            resize();  

        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {//逐个将节点加入  
            K key = e.getKey();  
            V value = e.getValue();  
            putVal(hash(key), key, value, false, evict);  
        }  
    }  
}

可以看出这大致过程就是先根据已有元素进行容量和阈值的计算，类似和初始化过程差不多，然后遍历Map，将其中元素逐个加入，加入的过程就是调用putVal，上面已经分析过。

3、remove()方法

remove方法用于删除给定key值对应的节点并返回，如果不存在就返回null。在内部也是调用一个final方法 removeNode。

 public V remove(Object key) {  
     Node<K,V> e;  
     return (e = removeNode(hash(key), key, null, false, true)) == null ?  
         null : e.value;  
 }  
   
 /* 
  * 实现Map.remove及相关方法 
  */  
final Node<K, V> removeNode(int hash, Object key, Object value,   
        boolean matchValue, boolean movable) {  
    Node<K, V>[] tab;//指向table数组  
    Node<K, V> p;//table[index]，链表第一个元素或红黑树根节点  
    int n, index;//n为table数组的长度。index为hash值对应的下标  

    if ((tab = table) != null && (n = tab.length) > 0 &&   
        (p = tab[index = (n - 1) & hash]) != null) {              
        Node<K, V> node = null, e;  
        K k;  
        V v;  
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))  
            node = p;  

        else if ((e = p.next) != null) {  
            if (p instanceof TreeNode)  
                node = ((TreeNode<K, V>) p).getTreeNode(hash, key);  
            else {  
                do {  
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {  
                        node = e;  
                        break;  
                    }  
                    p = e;  
                } while ((e = e.next) != null);  
            }  
        }  

        //上面的过程和getNode基本一样  
        if (node != null && (!matchValue ||//如果找到了该节点   
            (v = node.value) == value || (value != null && value.equals(v)))) {  

            if (node instanceof TreeNode)//如果是红黑树，在红黑树中删除节点  
                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);  

            else if (node == p)//如果是链表第一个节点  
                tab[index] = node.next;//直接指向next  

            else//  
                p.next = node.next;//  
            ++modCount;  
            --size;//  
            afterNodeRemoval(node);  
            return node;  
        }  
    }  
    //节点不存在，返回null  
    return null;  
}

可以看出，remove过程和get过程有很多相同的操作，都是先找到对应的元素，remove在查找之后会进行删除操作。

4、size()和isEmpty()方法

这两个方法很简单，一个返回元素个数，一个返回是否有元素。

public int size() {  
    return size;  
}  

public boolean isEmpty() {  
    return size == 0;  
}

5、clear()方法

清空整个Map。

public void clear() {  
    Node<K,V>[] tab;  
    modCount++;  
    if ((tab = table) != null && size > 0) {  
        size = 0;  
        for (int i = 0; i < tab.length; ++i)  
            tab[i] = null;  
    }  
}

size置0，直接遍历table数组，全部置为null，节点不用管，交给垃圾回收。

可以看出，clear方法后，Map的容量和阈值都是不变的，只是其中的元素被清空了。

6、containsValue()方法

这个方法虽然看上去和containsKey差不多，而且作用也确实都是判断Map中是否含有某key或某value，但是内部的实现却是完全不一样的，containsKey会调用getNode方法进行查找，而containsKey是直接遍历所有元素逐个对比的。二者查找方式与性能都有着很大的差别。

public boolean containsValue(Object value) {  
    Node<K,V>[] tab; V v;  
    if ((tab = table) != null && size > 0) {  
        for (int i = 0; i < tab.length; ++i) {  
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {  
                if ((v = e.value) == value ||  
                    (value != null && value.equals(v)))  
                    return true;  
            }  
        }  
    }  
    return false;  
}

可以看出，有两层循环，是挨个查找的，所以效率并不高。

7、JDK1,8扩展方法

四、返回Set的相关方法

HashMap类实现了Map接口，在Map中，定义了三个views相关的方法(源码注释里就是这么写的)。

// Views  
Set<K> keySet();  
Collection<V> values();  
Set<Map.Entry<K, V>> entrySet();

顾名思义，这三个方法分别返回Map中的关键字集合，值集合和节点集合。在HashMap中实现了这三个方法。

1、keySet()方法

返回包含Map中所有key值的Set，定义了一个继承自AbstractSet的内部类，它只会被new一次，因为在new之后会有一个全局变量keySet指向它，keySet变量是父类AbstractMap中定义的。

public Set<K> keySet() {  
    Set<K> ks;//ks=keySet  

    return (ks = keySet) == null ? (keySet = new KeySet()) : ks;  
}  

final class KeySet extends AbstractSet<K> {  
    public final int size()                 { return size; }  
    public final void clear()               { HashMap.this.clear(); }  
    public final Iterator<K> iterator()     { return new KeyIterator(); }  
    public final boolean contains(Object o) { return containsKey(o); }  
    public final boolean remove(Object key) {  
        return removeNode(hash(key), key, null, false, true) != null;  
    }  
    public final Spliterator<K> spliterator() {  
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);  
    }  
    public final void forEach(Consumer<? super K> action) {  
        Node<K,V>[] tab;  
        if (action == null)  
            throw new NullPointerException();  
        if (size > 0 && (tab = table) != null) {  
            int mc = modCount;  
            for (int i = 0; i < tab.length; ++i) {  
                for (Node<K,V> e = tab[i]; e != null; e = e.next)  
                    action.accept(e.key);  
            }  
            if (modCount != mc)  
                throw new ConcurrentModificationException();  
        }  
    }  
}

可以看出，返回的keySet对象和Map是向关联的，而不是一个复制，对返回Set的操作也会对应到相应的Map节点中。下面是我测试的一个小例子。

public static void main(String[] args) {  
    Map<Integer, String> map=new HashMap<Integer, String>();  
    map.put(1, "1");  
    map.put(2, "2");  
    Set<Integer> keySet=map.keySet();  
    System.out.println(keySet.contains(1));//true  
    map.remove(1);  
    System.out.println(keySet.contains(1));//false  
    keySet.remove(2);  
    System.out.println(map.size());//0  
}

2、values()方法

values方法与keySet基本类似，返回Map中包含的所有的value集合。很多操作的原理和上面都基本一样。

public Collection<V> values() {  
    Collection<V> vs;  
    return (vs = values) == null ? (values = new Values()) : vs;  
}  

final class Values extends AbstractCollection<V> {  
    public final int size()                 { return size; }  
    public final void clear()               { HashMap.this.clear(); }  
    public final Iterator<V> iterator()     { return new ValueIterator(); }  
    public final boolean contains(Object o) { return containsValue(o); }  
    public final Spliterator<V> spliterator() {  
        return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);  
    }  
    public final void forEach(Consumer<? super V> action) {  
        Node<K,V>[] tab;  
        if (action == null)  
            throw new NullPointerException();  
        if (size > 0 && (tab = table) != null) {  
            int mc = modCount;  
            for (int i = 0; i < tab.length; ++i) {  
                for (Node<K,V> e = tab[i]; e != null; e = e.next)  
                    action.accept(e.value);  
            }  
            if (modCount != mc)  
                throw new ConcurrentModificationException();  
        }  
    }  
}

有几点不同之处：

keySet返回的是Set，而values返回的是Collections，我觉得是因为Map中key是唯一的，Set也是不包含重复元素的。
返回的values中没有remove操作，因为Map可以对指定的key删除，却不可以对指定的value删除。

3、entrySet()方法

该方法返回的也是set，不过它返回的直接是键值对，其他的和上面两个也差不多。

public Set<Map.Entry<K,V>> entrySet() {  
    Set<Map.Entry<K,V>> es;  
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;  
}  

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {  
    public final int size()                 { return size; }  
    public final void clear()               { HashMap.this.clear(); }  
    public final Iterator<Map.Entry<K,V>> iterator() {  
        return new EntryIterator();  
    }  
    public final boolean contains(Object o) {  
        if (!(o instanceof Map.Entry))  
            return false;  
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;  
        Object key = e.getKey();  
        Node<K,V> candidate = getNode(hash(key), key);  
        return candidate != null && candidate.equals(e);  
    }  
    public final boolean remove(Object o) {  
        if (o instanceof Map.Entry) {  
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;  
            Object key = e.getKey();  
            Object value = e.getValue();  
            return removeNode(hash(key), key, value, true, true) != null;  
        }  
        return false;  
    }  
    public final Spliterator<Map.Entry<K,V>> spliterator() {  
        return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);  
    }  
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {  
        Node<K,V>[] tab;  
        if (action == null)  
            throw new NullPointerException();  
        if (size > 0 && (tab = table) != null) {  
            int mc = modCount;  
            for (int i = 0; i < tab.length; ++i) {  
                for (Node<K,V> e = tab[i]; e != null; e = e.next)  
                    action.accept(e);  
            }  
            if (modCount != mc)  
                throw new ConcurrentModificationException();  
        }  
    }  
}

有个区别就是entrySet是在HashMap中定义的，而不是继承自父类。在最上面第一部分代码中就列出了。

4、Map的遍历

关于Map的遍历，阿里的Java开发手册中同样提到【推荐】使用 entrySet 遍历 Map 类集合 KV，而不是 keySet 方式进行遍历。

说明： keySet 其实是遍历了 2 次，一次是转为 Iterator 对象，另一次是从 hashMap 中取出key 所对应的 value。而 entrySet 只是遍历了一次就把 key 和 value 都放到了 entry 中，效率更高。如果是 JDK8，使用 Map.foreach 方法。

正例： values()返回的是 V 值集合，是一个 list 集合对象； keySet()返回的是 K 值集合，是一个 Set 集合对象； entrySet()返回的是 K-V 值组合集合。