HashMap

目录

• 1.简介
• 2.新数据的存储过程
• 3.集合类的成员变量
• • 3.1 继承关系
  • 3.2 成员变量
  • 3.3 构造方法
• 4.成员方法
• • 4.1 put()
  • 4.2 将链表转换为红黑树
  • 4.3 扩容机制
  • 4.4 remove()
  • 4.5 get()
• 5.遍历
• 6.HashMap 的初始化容量建议

1.简介

• 存储形式：key-value（key唯一，value可重复，两者都可为null，但key至多有一个null）

• 无序存储

• HashMap 的实现不是同步，非线程安全类

• jdk1.8 之前 HashMap 由 数组 + 链表组成
  数组——主体
  链表——解决多个对象调用的地址冲突（拉链法）
  

• jdk1.8 之前 HashMap 由 数组（主体） + 链表/红黑树组成
  红黑树——链表长度大于阈值（或者红黑树的边界值，默认为 8 ）&&当前数组的长度大于 64 ，使用红黑树储存
  数组扩容——考虑到效率，当上述条件非全部满足时，使用数组扩容
  

2.新数据的存储过程

hash表底层采用的计算hash表的算法： key的hashcode方法的值结合数组长度进行无符号右移（>>>）、按位异或（^）、按位与（^）计算出索引
不考虑效率，还可采用的方法： 平方取中法、取余数、伪随机数法

        HashMap map1 = new HashMap<>();

        map1.put(1,"张三");
        map1.put(2,"李四");
        map1.put(2,"王五");//会覆盖掉之前的张三
        
        System.out.println(map1);

1. HashMap 的构造方法是在第一次调用 put 方法时创建数组（长度16） Node[] table来存储键值对数据。

2. 在像hash表中存储数据时，若计算出的索引的索引空间没有数据，就将数据存到数组中
   

3. 索引空间有数据，就在此空间上划出一个节点来存储键值对数据
   

4. key重复时（hash碰撞），可知计算出的存储位置不变，会覆盖之前的value
   

小结

1. 当两个对象对象的 hashcode相等（hash碰撞） 时（调用equals()比较key）
   
   key相同： 覆盖之前的value
   key不同： 接到链表之后，链表>阈值8且数组长度>64，采用红黑树存储（O(logn)），链表(O(n))
   
   
2. 当不断添加数据，超出临界值时，采用扩容，默认为原来容量的两倍
   
   创建一个新的数组，创建一个新的数组，长度是原来的 2倍
   遍历旧表的元素，重新计算hashcode并插入到新表
3. put的全过程
   
   size： HashMap 中键值对的实时数量
   threshold（临界值）： 当前已占用数组长度的最大值， threshold（临界值）= capacity（容量）* loadFactor（负载因子）

3.集合类的成员变量 3.1 继承关系

• Cloneable 空接口，表示可以克隆。创建并返回 HashMap 对象的一个副本。
• Serializable 序列化接口。属于标记性接口。HashMap 对象可以被序列化和反序列化。
• AbstractMap 父类提供了 Map 实现接口。以最大限度地减少实现此接口所需的工作。

3.2 成员变量

serialVersionUID——序列化版本号

private static final long serialVersionUID = 362498820763181265L;

DEFAULT_INITIAL_CAPACITY——集合的初始化容量（必须为2^n）

// 默认的初始容量是16	1 << 4 相当于 1*2的4次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

HashMap 为了存取高效，减少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现的关键就在把数据存到哪个链表中的算法。

算法： hash % length，hash值，数组长度
因为取余效率不如位运算，计算机对齐进行了优化
优化后的算法： hash & ( length - 1)
优化算法的前提： length = 2^n

    
    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;
    }

在实例化 HashMap 实例时，如果给定了 initialCapacity，由于 HashMap 的 capacity 必须都是 2 的幂，因此这个方法用于找到>= initialCapacity 的最小的 2 的幂
最终得到的这个 capacity 被赋值给了 threshold

this.threshold = tableSizeFor(initialCapacity);

指定集合的初始容量

// 构造一个带指定初始容量和默认负载因子（0.75)的空 HashMap。
HashMap(int initialCapacity)

DEFAULT_LOAD_FACTOR——默认加载因子（0.75）

static final float DEFAULT_LOAD_FACTOR = 0.75f;

MAXIMUM_CAPACITY——集合最大容量

static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次幂

TREEIFY_THRESHOLD——当链表的值超过8则会转为红黑树（jdk1.8新增）

// 当桶（bucket）上的结点数大于这个值时会转为红黑树
static final int TREEIFY_THRESHOLD = 8;

Map桶中节点超过8转为红黑树：
TreeNodes 占用空间是普通 Nodes 的两倍
泊松分布
链表长度达到 8 就转成红黑树，当长度降到 6 就转成普通 bin（bin就是 bucket 桶）→权衡空间和时间

     * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

UNTREEIFY_THRESHOLD——树转表的节点个数阈值

// 当桶（bucket）上的结点数小于这个值，树转为链表 
static final int UNTREEIFY_THRESHOLD = 6;

MIN_TREEIFY_CAPACITY——表转树的数组长度阈值

// 桶中结构转化为红黑树对应的数组长度最小的值 
static final int MIN_TREEIFY_CAPACITY = 64;

table——初始化hash表（2^n）

// 存储元素的数组 
transient Node[] table;

table 就是 HashMap 中的数组，jdk8 之前数组类型是 Entry 类型。从 jdk1.8 之后是 Node 类型。都实现了Map.Entry接口，仅名字不同。

entrySet——存放缓存

// 存放具体元素的集合
transient Set> entrySet;

size——表中元素个数

// 存放元素的个数，注意这个不等于数组的长度
 transient int size;

size代表 键值对数量，不是数组的长度

modCount——表的修改次数

// 每次扩容和更改 map 结构的计数器
 transient int modCount;  

threshold——扩展临界值

// 临界值 当实际大小（容量*负载因子）超过临界值时，会进行扩容
int threshold;

threshold（临界值）= capacity（容量）* loadFactor（负载因子）

loadFactor——表的负载因子

// 负载因子
final float loadFactor;

加载因子：
取值0~1之间，用来衡量 HashMap 满的程度（表示HashMap的疏密程度），越靠近1越满（密），影响hash 操作到同一个数组位置的概率

计算 HashMap 的实时负载因子：
size/capacity,capacity——数组的长度

影响：
太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散，0.75f 是官方给出的一个比较好的临界值

扩容：
表中元素达到 HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容，而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。开发中，为减少扩容，通常在创建hashmap对象时指定初始容量

定制：
HashMap 的构造器中可以定制 loadFactor

HashMap构造器

// 构造方法，构造一个带指定初始容量和负载因子的空HashMap
HashMap(int initialCapacity, float loadFactor);

3.3 构造方法

HashMap()——默认初始容量（16）默认负载因子（0.75）

public HashMap() {
   this.loadFactor = DEFAULT_LOAD_FACTOR; // 将默认的负载因子0.75赋值给loadFactor，并没有创建数组
}

HashMap(int initialCapacity)——指定初始容量（>=指定容量的最小的2^n），默认负载因子（0.75）

 // 指定“容量大小”的构造函数
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

HashMap(int initialCapacity, float loadFactor)——指定初始容量与负载因子

public HashMap(int initialCapacity, float loadFactor) {
    	// 判断初始化容量initialCapacity是否小于0
        if (initialCapacity < 0)
            // 如果小于0，则抛出非法的参数异常IllegalArgumentException
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    	// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY)
            // 如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
            initialCapacity = MAXIMUM_CAPACITY;
    	// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            // 如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
     	// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactor
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
// 最后调用了tableSizeFor，来看一下方法实现：
     
    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;
    }

HashMap(Map m)——包含另一个 “Map” 的构造函数

// 构造一个映射关系与指定 Map 相同的新 HashMap。
public HashMap(Map m) {
    	// 负载因子loadFactor变为默认的负载因子0.75
         this.loadFactor = DEFAULT_LOAD_FACTOR;
         putMapEntries(m, false);
 }

putMapEntries()的源码

final void putMapEntries(Map m, boolean evict) {
    //获取参数集合的长度
    int s = m.size();
    if (s > 0) {
        //判断参数集合的长度是否大于0，说明大于0
        if (table == null) { // 判断table是否已经初始化
                // 未初始化，s为m的实际元素个数
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
                // 计算得到的t大于阈值，则初始化阈值
                if (t > threshold)
                    threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

float ft = ((float)s / loadFactor) + 1.0F;这一行代码中为什么要加 1.0F ？
扩大容量，尽量减少扩容（resize）次数

4.成员方法 4.1 put()

实现步骤：

1. 由 hash 值计算出 key 映射到哪个桶；
2. 桶上没有hash碰撞，则直接插入；
3. 有hash碰撞：
   3.1 如果该桶使用红黑树处理冲突，则调用红黑树的方法插入数据；
   3.2 否则采用传统的链式方法插入。如果链的长度达到临界值，则把链转变为红黑树；
4. 桶中存在重复的键，则为该键替换新值 value；
5. size 大于阈值 threshold，则进行扩容

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

putVa()l负责—put的元素插入，调用了一个方法hash()

可见：key可以为空，返回为0，key不为空，就计算hashCode并赋值给h，再将h无符号右移16位和hashCode进行按位异或得到最终的hash值

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

接下来，根据上述代码计算出的hashCode计算索引

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
	...
	if ((p = tab[i = (n - 1) & hash]) == null) // 这里的n表示数组长度16
	...
}

小结——计算hash值

1. key.hashCode()计算hashCode
2. key.hashCode()^(key.hashCode()>>>16)计算出hash值
   即：高16位保持不变，低16位与高16位异或

目的： 将高位地位都利用起来，解决hash碰撞


当数组长度很小时，与hashCode直接进行按位与操作，表的利用率极低。当hash值高位变化很大，低变化很小，这样就容易导致hash碰撞。

putVal

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node[] tab; Node p; int n, i;
    
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
     
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 创建一个新的结点存入到桶中
        tab[i] = newNode(hash, key, value, null);
    else {
         // 执行else说明tab[i]不等于null，表示这个位置已经有值了
        Node e; K k;
        
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                 
                e = p;
        // hash值不相等或者key不相等；判断p是否为红黑树结点
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
        // 说明是链表结点
        else {
            
            for (int binCount = 0; ; ++binCount) {
                
                if ((e = p.next) == null) {
                    
                    p.next = newNode(hash, key, value, null);
                    
                    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) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                // 用新值替换旧值
                // e.value 表示旧值  value表示新值 
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 修改记录次数
    ++modCount;
    // 判断实际大小是否大于threshold阈值，如果超过则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

主要参数：
hash：key 的 hash 值
key：原始 key
value：要存放的值
onlyIfAbsent：如果 true 代表不更改现有的值
evict：如果为false表示 table 为创建状态

4.2 将链表转换为红黑树

treeifyBin()

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
   //转换为红黑树 tab表示数组名  hash表示哈希值
   treeifyBin(tab, hash);

final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //扩容方法
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        
        // hd：红黑树的头结点   tl：红黑树的尾结点
        TreeNode hd = null, tl = null;
        do {
            // 新创建一个树的结点，内容和当前链表结点e一致
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p; // 将新创键的p结点赋值给红黑树的头结点
            else {
                p.prev = tl; // 将上一个结点p赋值给现在的p的前一个结点
                tl.next = p; // 将现在结点p作为树的尾结点的下一个结点
            }
            tl = p;
            
        } while ((e = e.next) != null);
        
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

小结——链表转树

1. 根据键值对个数判断是进行树化还是扩容
2. 树化：
   遍历桶中的元素，创建相同个数的树形结点，复制内容，建立起联系
   让桶中的第一个元素指向新创建的树根结点，替换桶的链表内容为树形化内容

4.3 扩容机制

• 扩容前提：
  数组元素个数超过临界值，threshold（临界值）= capacity（容量）* loadFactor（负载因子）
  
  链表节点>8，数组长度<64

• 扩容说明：
  扩容（resize）：重新进行hash分配，并且遍历hash表中所有元素，比较耗时
  
  HashMap扩容（rehash）：因为每次扩容都是翻倍，与原来计算的 (n - 1) & hash 的结果相比，只是多了一个 bit 位，所以结点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置。
  从 16 扩展为 32 :
  
  因此元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的标记范围在高位多 1bit（要么为1要么为0）
  

说明：

1. 5 是假设计算出来的原来的索引，用来验证：扩容之后所以结点要么就在原位置，要么就被分配到 “原位置 + 旧容量” 这个位置。
2. 在扩充 HashMap 的时候，不需要重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就可以了，是 0 的话索引没变，是 1 的话索引变成 “原位置 + 旧容量” 。

采用这种refresh方式的优势：

1. 省去了重新计算hash的时间
2. 由于高位可1可0，完全随机，在扩容的过程中保证了 rehash 之后每个桶上的结点数一定小于等于原来桶上的结点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的结点分散到新的桶中了

resize()——扩容

final Node[] resize() {
    // 得到当前数组
    Node[] oldTab = table;
    // 如果当前数组等于null长度返回0，否则返回当前数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //当前阀值点 默认是12(16*0.75)
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果老的数组长度大于0
    // 开始计算扩容后的大小
    if (oldCap > 0) {
        // 超过最大值就不再扩充了，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 修改阈值为int的最大值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 阈值扩大一倍
            newThr = oldThr << 1; // double threshold
    }
    // 老阈值点大于0 直接赋值
    else if (oldThr > 0) // 老阈值赋值给新的数组长度
        newCap = oldThr;
    else { // 直接使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;//16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize最大上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 新的阀值 默认原来是12 乘以2之后变为24
    threshold = newThr;
    // 创建新的哈希表
    @SuppressWarnings({"rawtypes","unchecked"})
    //newCap是新的数组长度--》32
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    // 判断旧数组是否等于空
    if (oldTab != null) {
        // 把每个bucket都移动到新的buckets中
        // 遍历旧的哈希表的每个桶，重新计算桶里元素的新位置
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                // 原来的数据赋值为null 便于GC回收
                oldTab[j] = null;
                // 判断数组是否有下一个引用
                if (e.next == null)
                    // 没有下一个引用，说明不是链表，当前桶上只有一个键值对，直接插入
                    newTab[e.hash & (newCap - 1)] = e;
                //判断是否是红黑树
                else if (e instanceof TreeNode)
                    // 说明是红黑树来处理冲突的，则调用相关方法把树分开
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // 采用链表处理冲突
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    // 通过上述讲解的原理来计算结点的新位置
                    do {
                        // 原索引
                        next = e.next;
                     	// 这里来判断如果等于true e这个结点在resize之后不需要移动位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

4.4 remove()

根据key值，遍历数组找到元素（若在链表/树中，继续遍历链表/树），再删除

remove()

    public V remove(Object key) {
        Node e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

removeNode()

final Node removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node[] tab; Node p; int n, index;
	// 根据hash找到位置 
	// 如果当前key映射到的桶不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node node = null, e; K k; V v;
        // 如果桶上的结点就是要找的key，则将node指向该结点
        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)p).getTreeNode(hash, key);
            else {
                // 判断是否以链表方式处理hash冲突，是的话则通过遍历链表来寻找要删除的结点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 比较找到的key的value和要删除的是否匹配
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 通过调用红黑树的方法来删除结点
            if (node instanceof TreeNode)
                ((TreeNode)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 链表删除
                tab[index] = node.next;
            else
                p.next = node.next;
            // 记录修改次数
            ++modCount;
            // 变动的数量
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

4.5 get()

根据key找到value

get

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

getNode

final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    // 如果哈希表不为空并且key对应的桶上不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果不是第一个元素，判断是否有后续结点
        if ((e = first.next) != null) {
            // 判断是否是红黑树，是的话调用红黑树中的getTreeNode方法获取结点
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            do {
                // 不是红黑树的话，那就是链表结构了，通过循环的方法判断链表中是否存在该key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

5.遍历

分别遍历key和value

//Object可以替换为key和value的封装类型

for (Object key : map.keySet()) {
	System.out.println(key);
}

for (Object vlaue : map.values() {
	System.out.println(value);
}

使用 Iterator 迭代器

Iterator> iterator = map.entrySet().iterator();

while (iterator.hasNext()) {
    Map.Entry mapEntry = iterator.next();
    System.out.println(mapEntry.getKey() + "---" + mapEntry.getValue());
}

通过 get 方式（不建议使用）
阿里开发手册，不建议使用这种方式，因为迭代两次。（keySet 获取 Iterator一次，还有通过 get 又迭代一次，降低性能。）

Set keySet = map.keySet();

for (String str : keySet) {
	System.out.println(str + "---" + map.get(str));
}

jdk8 以后使用 Map 接口中的默认方法

map.forEach((key, value) -> {
    System.out.println(key + "---" + value);
});

forEach

    @Override
    public void forEach(BiConsumer action) {
        Node[] 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 e = tab[i]; e != null; e = e.next)
                    action.accept(e.key, e.value);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

6.HashMap 的初始化容量建议

使用HashMap(int initialCapacity)初始化hash表容量时， Jdk 并不会直接拿用户传进来的数字当做默认容量，而是会进行一番运算，最终得到>=自定义初始值的最小的2^n

---

《阿里巴巴Java开发手册》原文：

即 initialCapacity/ 0.75F + 1.0F，牺牲一定内存来换取性能。