本文基于JDK 7，内容涉及HashMap常用API，put()过程，get()过程，自动扩容等
HashMap用法
常用API
V get(Object key); // 获得指定键的值
V put(K key, V value); // 添加键值对
void putAll(Map<? extends K, ? extends V> m); // 将指定Map中的键值对 复制到 此Map中
V remove(Object key); // 删除该键值对
boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true
boolean containsValue(Object value); // 判断是否存在该值的键值对；是 则返回true
Set<K> keySet(); // 单独抽取key序列，将所有key生成一个Set
Collection<V> values(); // 单独value序列，将所有value生成一个Collection
void clear(); // 清除哈希表中的所有键值对
int size(); // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为 空 取值
public class HashMapTest1 {
static Map<String,Integer> map = new HashMap<>();
public static void main(String[] args) {
map.put("柚子", 3);
System.out.println("key = 柚子的值为：" + map.get("柚子") + "\n");
// 输出：key = 柚子的值为：3
}
}遍历
方式一：获得key-value的Set集合再遍历
Map<String,Integer> map = new HashMap<>(); Set<Map.Entry<String, Integer>> entrySet = map.entrySet(); // 遍历Set集合，从而获取key-value for (Map.Entry<String, Integer> entry : entrySet) { System.out.print(entry.getKey()); System.out.println(entry.getValue()); } // 或者 Iterator iter1 = entrySet.iterator(); while (iter1.hasNext()) { // 遍历时，需先获取entry，再分别获取key、value Map.Entry entry = (Map.Entry) iter1.next(); System.out.print((String) entry.getKey()); System.out.println((Integer) entry.getValue()); }方式二：获得key的Set集合再遍历
Map<String,Integer> map = new HashMap<>(); // 1. 获得key的Set集合 Set<String> keySet = map.keySet(); // 2. 遍历Set集合，从而获取key，再获取value // 2.1 通过foreach循环 for (String key : keySet) { System.out.print(key); System.out.println(map.get(key)); } // 2.2 通过迭代器 Iterator iter2 = keySet.iterator(); String key = null; while (iter2.hasNext()) { key = (String) iter2.next(); System.out.print(key); System.out.println(map.get(key)); }方式三：获得value的Set集合再遍历
// 1. 获得value的Set集合 Collection valueSet = map.values(); // 2. 遍历Set集合，从而获取value // 2.1 获得values 的Iterator Iterator iter3 = valueSet.iterator(); // 2.2 通过遍历，直接获取value while (iter3.hasNext()) System.out.println(iter3.next());三种遍历方式优先选择第一种，其效率最高，因为：
- 对于遍历keySet 、valueSet，实质上是遍历了2次
- 第一次转为iterator迭代器遍历
- 第二次从HashMap中取出key和value
- 对于遍历entrySet，实质只遍历了1次，也就是获取存储实体Entry（存储了key 和 value ）
- 对于遍历keySet 、valueSet，实质上是遍历了2次
数据结构
简介
HashMap是散列表的一种，HashMap本身采用数组来进行储存。同时HashMap采用拉链法来解决hash冲突，拉链法就是通过链表来解决hash冲突。所以说整体上来看，HashMap采用的数据结构 = 数组（主） + 单链表（副）
由此可见：
- 一个长方形格子代表一个entry对象，同时也代表一个键值对；
- 即 HashMap的本质 = 1个存储Entry类对象的数组 + 多个单链表
- Entry对象本质 = 1个映射（键 - 值对），属性包括：键（key）、值（value）、下个节点( next) = 单链表的指针 = 也是一个Entry对象，用于解决hash冲突
重要参数介绍
构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) // MAXIMUM_CAPACITY == 1 << 30
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
// 设置扩容阈值 = 初始容量
// 注意：此处不是真正的阈值，仅是为了接收参数初始容量大小（capacity）、加载因子(Load factor)，
// 并没有真正初始化哈希表，即初始化存储数组table
// 真正初始化哈希表（初始化存储数组table）是在第1次添加键值对时，即第1次调用put()时
threshold = initialCapacity; // 16
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
/*
名词介绍：
1、容量（capacity）：HashMap中数组【强调一下是数组，不是元素个数】的长度
2、容量范围：必须是2的幂并且小于最大容量（2的30次方）
3、初始容量 = 哈希表创建时的容量
*/
//默认初始容量 = 哈希表创建时的容量。默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 十进制的2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
// 最大容量 = 2的30次方（若传入的容量过大，将被最大值替换）
static final int MAXIMUM_CAPACITY = 1 << 30;
/*
1、加载因子(Load factor)：HashMap在其容量自动增加前的一种尺度。
2、加载因子越大、填满的元素越多 = 空间利用率高、但hash冲突的机会加大、查找效率变低（因为链表变长了）
3、加载因子越小、填满的元素越少 = 空间利用率小、hash冲突的机会减小、查找效率高（链表不长）
*/
// 实际加载因子
final float loadFactor;
// 默认加载因子 = 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 就是上面说的数组，hashmap用Entry数组储存k-v键值对
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
static final Entry<?,?>[] EMPTY_TABLE = {};
// HashMap的大小，即HashMap中存储的键值对的数量。注意：和容量区分开，容量是数组Entry的长度
transient int size;
/*
1、扩容阈值（threshold）：当哈希表的大小【就是上面的size】 ≥ 扩容阈值时，就会扩容哈希表
（即扩充HashMap的容量）
2、扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
3、扩容阈值 = 容量 x 加载因子 (16 x 0.75)
*/
int threshold;数组Entry
/**
* Entry类实现了Map.Entry接口
* 即重写了getKey()、getValue()、equals(Object o)和hashCode()等方法
**/
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 键
V value; // 值
Entry<K,V> next; // 指向下一个节点 ，也是一个Entry对象，从而形成解决hash冲突的单链表
int hash; // hash值
/**
* 构造方法，创建一个Entry
* 参数：哈希值h，键值k，值v、下一个节点n
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
// 返回与此项 对应的键
public final K getKey() {
return key;
}
// 返回 与 此项 对应的值
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
/**
* equals（）
* 作用：判断2个Entry是否相等，必须key和value都相等，才返回true
*/
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
/**
* hashCode（）
*/
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* 当向HashMap中添加元素时，即调用put(k,v)时，
* 对已经在HashMap中k位置进行v的覆盖时，会调用此方法
* 此处没做任何处理
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* 当从HashMap中删除了一个Entry时，会调用该函数
* 此处没做任何处理
*/
void recordRemoval(HashMap<K,V> m) {
}
}HashMap put的过程
public V put(K key, V value) {
/**
* 一、若哈希表未初始化（即table为空)，则调用inflateTable()方法，使用构造函数时设置的阈值
* (即初始容量)初始化数组table
*/
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
/** 二、
* 1 判断key是否为空值null
* 2 若key == null，则调用putForNullKey()方法，putForNullKey()方法最终将该键-值存放到数组
* table中的第1个位置，即table[0]。本质：key = Null时，hash值 = 0，故存放到table[0]中）
* 该位置永远只有1个value，新传进来的value会覆盖旧的value
* 3 k != null往下走
*/
if (key == null)
return putForNullKey(value);
// 下面就是k != null的情况
// 计算key的hash值
int hash = hash(key);
// 根据hash值最终获得key对应存放的数组Table中位置(也就是数组下标)
int i = indexFor(hash, table.length);
/**
* 三、通过遍历以该数组元素为头结点的链表，逐个判断是否发生hash冲突，同时判断该key对应的值是
* 否已存在
*/
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
/**
* 四、如果发生了hash冲突，且key也相等。则用新value替换旧value(此时说明发生了更新的情况)，
* 注意这里强调的是发生了hash冲突并且key也相等。
*/
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 修改次数+1
modCount++;
/**
* 五、
* 1 走到这一步有两种情况
* 1-1 没有发生hash冲突
* 1-2 发生了hash冲突，但是没有在链表中找到key一样的键
* 2 接着准备采用头插法，插入链表的头部(也就是数组里面)
*/
addEntry(hash, key, value, i);
return null;
}下图的描述就是put过程的各个阶段
inflateTable()方法
private void inflateTable(int toSize) {
/*
* 将传入的容量大小转化为：>传入容量大小的最小的2的次幂，即如果传入的是容量大小是18，那么转化后，
* 初始化容量大小为32（即2的5次幂）
*/
int capacity = roundUpToPowerOf2(toSize);
// 重新计算阈值 threshold = 容量 * 加载因子
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
/*
* 使用计算后的初始容量（已经是2的次幂）初始化数组table（作为数组长度）即 哈希表的容量大小 =
* 数组大小（长度）
*/
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}roundUpToPowerOf2()方法
private static int roundUpToPowerOf2(int number) {
// 若容量超过了最大值，初始化容量设置为最大值；否则，设置为>传入容量大小的最小的2的次幂
return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}putForNullKey()
当 key == null时，将该 key-value 的存储位置规定为数组table 中的第1个位置，即table [0]
private V putForNullKey(V value) {
/*
* 1 遍历以table[0]为首的链表，寻找是否存在key==null对应的键值对
* 1-1 若有：则用新value替换旧value；同时返回旧的value值。
*/
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
/*
* 1 若无key==null的键，那么调用addEntry()，将空键和对应的值封装到Entry中，并放到table[0]中
* 2 能走到这里的情况就是table[0]位置之前没有元素，这一次是第一次添加key为null的元素
* 3 k == null已经是固定放在了table[0]的位置，不会有链表存在，只会有一个元素。
*/
addEntry(0, null, value, 0);
return null;
}从此处可以看出：
- HashMap的键key可以为null（区别于：HashTable的key不可为null）
- HashMap的键key可为null且只能为1个，但值value可为null且为多个
hash()
这个方法比较重要，1.7和1.8改动的比较大
/**
* 1 该函数在JDK7和8中的实现不同，但原理一样 = 扰动函数 = 使得根据key生成的
* 哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）
* 2 JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
* 3 JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算
* 4 hash()方法被final修饰，表示该方法不可以被重写
*/
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 4次位运算 + 5次异或运算
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}indexFor()
// 这里h & (length-1)的意思就是hash值与数组长度取模。只是因为数组长度是特殊的2的幂，
// 所以这个等价关系刚好成立
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}addEntry()
// 作用：添加键值对（Entry）到HashMap中。参数4:插入数组table的索引位置，也就是数组下标
// 注意：JDK7是先扩容再插入
void addEntry(int hash, K key, V value, int bucketIndex) {
/*
* 1 插入前，先判断容量是否足够
* 1.1 若不足够，则进行扩容（2倍）、重新计算Hash值、重新计算存储数组下标
*/
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // 这里是扩容，在下面具体讲解
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 1.2 若容量足够，则创建1个新的数组元素（Entry）并放入到数组中
createEntry(hash, key, value, bucketIndex);
}HashMap的自动扩容机制
下面的也是JDK7扩容的步骤，接着上面的addEntry()
resize()
/**
* 作用：当大小不足时（size > 阈值，注意是size，不是容量），则扩容（扩到2倍）
*/
void resize(int newCapacity) {
// 1 保存旧数组（old table）
Entry[] oldTable = table;
// 2 保存旧容量（old capacity），即数组长度
int oldCapacity = oldTable.length;
// 3 若旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值，返回
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 4 根据新容量（2倍容量）新建1个数组，即newTable
Entry[] newTable = new Entry[newCapacity];
//5 将旧数组上的数据（键值对）转移到新table中，从而完成扩容
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 6 新数组table引用到HashMap的table属性上
table = newTable;
// 7 重新设置阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
} transfer()
/**
* 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
* 过程：按旧链表的正序遍历链表、在新链表的头部依次插入。但是这样会导致扩容完成后的链表逆序
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 通过遍历旧数组，将旧数组上的数据（键值对）转移到新数组中
for (Entry<K,V> e : table) {
while(null != e) {
/*
* 1 遍历以该数组元素为首的链表
* 2 转移链表时，因是单链表，故要保存下1个结点，否则转移后链表会断开
*/
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 重新计算每个元素的存储位置
int i = indexFor(e.hash, newCapacity);
// 这个地方暂时先放着，后面讲死循环链表的时候会讲到
e.next = newTable[i];
// 将当前元素赋给新数组的对应下标位置。
newTable[i] = e;
// 访问下一个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
e = next;
}
}
}
1、在扩容resize()过程中，在将旧数组上的数据转移到新数组上时，转移操作就是按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况。
2、设重新计算存储位置后不变，即扩容前 1->2->3，扩容后 = 3->2->1
3、此时若（多线程）并发执行 put()操作，一旦出现扩容情况，则容易出现环形链表，从而在获取数据、遍历链表时形成死循环（Infinite Loop），即线程不安全。
createEntry()
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++; // 这里才进行size++
}举个例子说明流程：
1、假设hashmap中容量为16，加载因为为0.75 = 12。
2、此时hashmap中有11个元素，也就是size == 11，在你添加第12个元素时。看代码，此时size还是11，所以并不会扩容。只有在你调用完createEntry(),size++执行完毕后，size变成12。
3、在添加第13个元素时，才会进入if逻辑里进行先扩容。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}扩容出现的死循环链表
/**
* 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
* 过程：按旧链表的正序遍历链表、在新链表的头部依次插入。但是这样会导致扩容完成后，链表逆序
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 通过遍历旧数组，将旧数组上的数据（键值对）转移到新数组中
for (Entry<K,V> e : table) {
while(null != e) {
/*
* 1 遍历以该数组元素为首的链表
* 2 转移链表时，因是单链表，故要保存下1个结点，否则转移后链表会断开
*/
Entry<K,V> next = e.next; // pos_1
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 重新计算每个元素的存储位置
int i = indexFor(e.hash, newCapacity);
// 这个地方暂时先放着，后面讲死循环链表的时候会讲到
e.next = newTable[i];
// 讲当前元素，赋给新数组的对应下标位置。
newTable[i] = e;
// 访问下1个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
e = next;
}
}
}为了演示方便，设初始状态时，hashmap容量为2，加载因子为默认的0.75，扩容阈值为2 * 0.75 = 1.5。
第一步：
此时假设有两个线程，线程a和线程b同时put，并且都没有进入到addEntry()方法里的if逻辑【因为此时size都没有++，size == 1，1 < 1.5 所以if判断不成立。】。两个线程都准备同时调用createEntry()方法。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}线程a put的是 e3 = <k3,v3>。线程b put的是e2 = <k2,v2>。两个都调用了createEntry()方法。
第二步：
此时size==3。下次再进行put的时候，addEntry()方法里的if判断就会成立。
第三步：
接着，又来了两个线程，线程1和线程2。【假设线程1put的是e1，线程2put的是e0。其实也不用管它们两put的是谁】
两个线程都同时调用resize()方法，新数组已经扩容完毕，准备转移旧数组上的数据到新数组里。也就是准备调用resize()里的下面这个方法。
// 将旧数组上的数据（键值对）转移到新table中，从而完成扩容 transfer(newTable, initHashSeedAsNeeded(newCapacity));来看此时内存里的状态
第四步：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
// pos_1
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// pos_2
e.next = newTable[i];
// pos_3
newTable[i] = e;
// pos_4
e = next;
}
}
}假设线程1执行完代码pos_1位置后，暂时挂起。此时e == e2；e.next == e3
线程2直接扩容完毕，那么完成后的状态是这样【假设e2和e3还是hash到同一个位置】
线程1还是原来的状态
第五步：
目前两个线程里的新数组是这样的
为了方便后面观看，我画成这样。
第六步：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
// pos_1
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// pos_2
e.next = newTable[i];
// pos_3
newTable[i] = e;
// pos_4
e = next;
}
}
}之前说过：假设线程1执行完代码pos_1位置后，暂时挂起。此时e == e2 e.next == e3【也就是next == e3】
线程1唤醒后，继续执行pos_2，pos_3，pos_4
执行pos_2：意思是e2的next指针指向了线程1的新hash表【也就是newTable1】，因为newTable1是新的所以为null，所以e2.next = null
执行pos_3：newTable1[3] = e2
执行pos_4： e = e3
也就变成了下面这个样子。
第七步：
线程1继续执行循环
注意之前强调过线程2已经扩容完毕，那么table就已经被指向了newTable2，也就是说第二次循环时，线程1所循环的table变量就是newTable2
执行pos_1：此时e == e3，那么next就是 e3.next，此时next == e2；
执行pos_2：经过第一轮循环，newTable1[3] == e2。那么执行完这行代码后，e3.next还是等于e2【相当于没执行】
执行pos_3：newTable1[3] == e3。
执行pos_4：e = e2
执行完，变成这样。
第八步：
线程1执行第三次循环
执行pos_1：next = e2.next得到 next == null。
执行pos_2：
e.next = newTable[i]e2.next == newTable1[3]。也就是相当于 e2.next == e3执行pos_3： newTable[i] = e得到 newTable1[3] == e2
这样就形成了循环链表，再get()数据就会陷入死循环。
HashMap get()的过程
public V get(Object key) {
// 当key==null时，则到table[0]为头结点的链表去寻找对应 key == null的键
if (key == null)
return getForNullKey();
// 当key ≠ null时，去获得对应值
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0)
return null;
// 遍历以table[0]为头结点的链表，寻找 key==null 对应的值
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 从table[0]中取key==null的value值
if (e.key == null)
return e.value;
}
return null;
}
final Entry<K,V> getEntry(Object key) {
if (size == 0)
return null;
// 根据key值，通过hash()计算出对应的hash值
int hash = (key == null) ? 0 : hash(key);
// 根据hash值计算出对应的数组下标，遍历以该数组下标的数组元素为头结点的链表所有节点，
// 寻找该key对应的值
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
// 若hash值和key相等，则证明该Entry = 我们要的键值对
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
} 
