HashMap源码阅读

发表于 更新于 分类于
花了两天时间，对HashMap 1.8的一千多行的源码认真的研究了一下，不禁感叹源码的严谨性，在我平常看来有很多判断都是没有必要的，但是仔细想想为什么这样写，其实严谨的不无道理。 因为源码一共有两千多行，但是真正关键的部分大概是1400行之前，所以就详细的对这些部分做一个解释。

HashMap的数据结构

先介绍一点基础结构

HashMap的基础结构是由数组（Node<K,V>[] table）+ 链表 + 红黑树组成的，因为我对红黑树不太了解，所以就没有看后面红黑树部分的东西（1400行之后的代码基本全是在说红黑树部分的），下面就没有讲述红黑树部分的内容。
数组的每个下标位置储存的是Node结点， 在Javadoc中把存放数据的table数组的每个下表称作bin（桶），数组每个下标的一开始存放的是链表，当链表长度大于等于（>=）8的时候，会将链表转换为红黑树。

顶部注释：

HashMap是Map接口基于哈希表的实现。这种实现提供了所有可选的Map操作，并允许key和value为null（除了HashMap是unsynchronized的和允许使用null外，HashMap和HashTable大致相同。）。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

此实现假设哈希函数在桶内适当地分布元素，为基本实现(get 和 put)提供了稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。如果遍历操作很重要，就不要把初始化容量initial capacity设置得太高（或将加载因子load factor设置得太低），否则会严重降低遍历的效率。

HashMap有两个影响性能的重要参数：初始化容量initial capacity、加载因子load factor。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。initial capacityload factor就是当前允许的最大元素数目，超过initial capacityload factor之后，HashMap就会进行rehashed操作来进行扩容，扩容后的的容量为之前的两倍。

通常，默认加载因子 (0.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生rehash 操作。

如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：
Map m = Collections.synchronizedMap(new HashMap(…));

由所有此类的“collection 视图方法”所返回的迭代器都是fail-fast 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的remove方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测bug。

此类是 Java Collections Framework 的成员。

从上面的内容可以总结出以下几点：

  • 底层： HashMap是Map接口基于哈希表实现的。
  • 是否允许null： HashMap允许key和value为null。
  • 是否有序：HashMap不保证映射到顺序，特别是它不保证顺序恒久不变。
  • 两个影响HashMap性能的参数： 初始化容量initial capacity、加载因子load factor。
  • 每次扩容大小：扩容后的的容量为之前的两倍。
  • 初始化容量对性能的影响： 不应设置的太小，容量小虽然可以节省空间，但是可能会导致频繁的扩容，扩容操作非常消耗时间；也不应该设置的太大，容量大会导致严重降低遍历的效率以及内存空间的浪费。总结来说就是：小了会增大时间开销（频繁的扩容）；大了会增大空间开销和时间开销（降低遍历效率）。
  • 加载因子对性能的影响： 0.75是一个折中的值，加载因子过高虽然减少了空间开销，但是也增加了查询到成本；而加载因子过低会导致频繁的扩容。
  • 是否同步： HashMap不是同步的。
  • 迭代器： 迭代器是fast-fail，但是迭代器的快速失败行为不能得到保证。

HashMap的定义

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
  • HashMap<K,V>：HashMap是以key-value形式存储数据。
  • extends AbstractMap<K,V>： 继承于AbstractMap，大大减少了实现Map接口时需要的工作。
  • implements Map<K,V： 实现了Map接口，提供所有可选的Map操作。
  • implements Cloneable：实现了Cloneable接口，内部可以调用clone()方法来返回实例的浅拷贝(shallow copy)。
  • implements Serializable：实现了Serializable接口，表明该类时可以序列化的。

静态全局变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 默认初始容量—必须是2的幂。
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;	// 也就是 16

/**
 * 如果具有参数的任一构造函数隐式指定更高的值，则使用最大容量。
 * 必须是2的幂 <= 1 << 30。
 */
static final int MAXIMUM_CAPACITY = 1 << 30;	// 也就是 2的30次方

/**
 * 构造函数中没有指定时使用的加载因子，即默认的加载因子。
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 将链表转化成红黑树的临界值。
 * 当链表长度(包括下标处开始的那个结点)大于等于8时，桶中的链表被转化成红黑树。
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 将红黑树恢复成链表时的临界值。
 * 当红黑树的长度小于等于6时，桶中的红黑树被转化成链表。
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 桶被转化成红黑树的最小容量。
 * 当链表长度大于等于8，且HashMap的总体大小大于等于64时，才会将桶中的链表被转化成红黑树。
 * 否则只会采取扩容的方式来减少冲突。
 * 该值不能小于 4 * TREEIFY_THRESHOLD
 */
static final int MIN_TREEIFY_CAPACITY = 64;

静态内部类 Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/**
 * HashMap的基本节点类型，即是HashMap底层的组成元素，也是每个桶（bin）中的链表的组成元素。
 */
   static class Node<K,V> implements Map.Entry<K,V> {
	/**
 	* key的hash值
 	*/
       final int hash;
       final K key;
       V value;
	/**
 	* 指向下一个Node节点的引用
 	*/
       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() {
           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) {
           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;
       }
   }

静态工具

hash方法详解

1
2
3
4
5
6
7
8
9
/** 
 * 计算key.hashCode（）并将更高位的散列扩展（XOR）降低。
 */
   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

i = (table.length - 1) & hash;	//这一步是在后面添加元素putVal()方法中进行位置的确定

主要分为三步：

  1. 取hashCode的值： key.hashCode()。调用Object. hashCode() 方法，该方法根据一定规则将与对象相关的信息，例如对象的存储地址，对象的字段等，映射成与一个32位 int 类型的值，这个数值称作为hash值。
  2. 让高位参与运算： h>>>16 。将得到的hash值无符号右移十六位，空出来的高位补零。
  3. 取模运算： (n-1) & hash 。 为了让数组元素分布均匀，把hash值对数组长度-1取余，也就是hash%n，得到在数组中保存的位置下标。

为什么要这样做的理由：

整个过程如上图所示，将原本的32位的hash值右移16位，然后与原值进行异或运算，是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。

看到这里有个疑问，为什么要做异或运算？
设想一下，如果n很小，假设为16的话，那么n-1即为15（0000 0000 0000 0000 0000 0000 0000 1111），这样的值如果跟hashCode()直接做与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样很容易造成碰撞，所以把高低位都参与到计算中，从而解决了这个问题，而且也不会有太大的开销。
然后将得到的最终的hash值对数组长度-1取余，就可以得到在数组中保存的位置下标。这也是为什么要保证数组的长度总是2的n次方的理由。当数组长度length总是2的n次方时，(n - 1) & hash == hash % n，但是位运算的速度更快，因此保证效率更高。

comparableClassFor方法解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
    * 当对象x的类型为X，并且X实现了Comparable接口（比较的参数本身必须为X类本身）时
    * 返回x的运行时类型，否则返回null。
    * 
    */
   static Class<?> comparableClassFor(Object x) {
       if (x instanceof Comparable) {
           Class<?> c; Type[] ts, as; ParameterizedType p;
           if ((c = x.getClass()) == String.class) // bypass checks
               return c;
           if ((ts = c.getGenericInterfaces()) != null) {
               for (Type t : ts) {
                   if ((t instanceof ParameterizedType) &&
                       ((p = (ParameterizedType) t).getRawType() ==
                        Comparable.class) &&
                       (as = p.getActualTypeArguments()) != null &&
                       as.length == 1 && as[0] == c) // type arg is c
                       return c;
               }
           }
       }
       return null;
   }

如注释所示，传参传入一个对象，当对象x的类型为X，并且X实现了Comparable接口（比较的参数本身必须为X类本身）时，返回x的运行时类型，否则返回null。
接下来分析这个方法的每行代码。

  • instanceof
    1
    x instanceof Comparable

instanceof可以理解为是某种类型的实例。不论是运行时类型，或者是他的父类、它实现的接口、他的父类实现的接口、甚至是他父类的父类的父类实现的接口的父类的父类，总之，只要在继承链上有这个类型就可以了。

  • getClass()
    1
    c = x.getClass()

与instanceof相应对的是getClass()方法，无论该对象如何转型，该方法返回的只会是它的运行时类型，可以简单的理解为它的实际类型，也就是new它的时候的类型。
有一种例外情况：匿名对象。当匿名对象调用该方法时，返回的是依赖它的对象的运行时类型，并且以1，2，3…的索引区分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Demo {
   public static void main(String[] args) {
       D d = new D();
       System.out.println(new A(){}.getClass());   // class Demo$1
       System.out.println(new B(){}.getClass());   // class Demo$2
       System.out.println(new Comparable<Object>(){    // class Demo$3
           @Override
           public int compareTo(Object o) {
               return 0;
           }}.getClass());
       	System.out.println(d.c.getClass()); // class D$1
   	}
}

abstract class A{}
abstract class B{}
abstract class C{}
class D{
   	C c;
   	D(){
       	c= new C(){};
   	}
}
  • getGenericInterfaces()
    1
    ts = c.getGenericInterfaces()

getGenericInterfaces()方法返回的是该对象的运行时类型”直接实现”的接口，这意味着:

  • 返回的一定是接口
  • 必然是该类型自己直接实现的接口，继承过来的不算

  • getGenericSuperclass()和getSuperclass()
    这两个方法虽然没有出现在上述代码中，但是也顺便说一下：

    • getGenericSuperclass()返回的是父类的直接类型，不包括泛型参数。
    • getSuperclass()返回的是包括泛型参数的父类类型，但是注意，如果子类在继承父类时，没有实现（声明）父类的泛型，那么这时候子类是没有泛型参数的。

  • ParameterizedType

    1
    t instanceof ParameterizedType

ParameterizedType是Type接口的子接口，表示实现了泛型参数的类型。需要注意：

  • 如果直接用Bean对象 instanceof ParameterizedType，结果都是false。
  • Class对象不能 instanceof ParameterizedType，编译会报错。
  • 只有用Type对象 instanceof ParameterizedType ，才能得到想要的比较结果。可以理解为：一个Bean类不会是ParameterizedType，只有代表这个Bean类的类型（Type）才有可能是ParameterizedType。
  • 实现泛型参数，必须给泛型传入参数，例如：class Child2<A,B> extends Super<A,B>{} ;只声明泛型而不实现,例如：class Child3<A,B> extends Super{} , 对比结果为false。
  • getRawType()
    1
    ((p = (ParameterizedType) t).getRawType()

该方法返回实现了这个类型的类或者接口，即去掉了泛型参数部分的类型对象。

  • getActualTypeArguments()
    1
    as = p.getActualTypeArguments()

该方法与getRawType()相对应，以数组形式返回泛型的参数列表。

  • 当参数是真实类型时，打印的是全类名
  • 当参数是另一个新声明的泛型参数时，打印的是代表该泛型类型的符号。

所以总结comparableClassFor(Object x)方法的实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static Class<?> comparableClassFor(Object x) {
       if (x instanceof Comparable) {  // 判断是否实现了Comparable接口
           Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
           if ((c = x.getClass()) == String.class) 
               return c;   // 如果是String类型，直接返回String.class
           if ((ts = c.getGenericInterfaces()) != null) {  // 判断是否有直接实现的接口
               for (int i = 0; i < ts.length; ++i) {   // 遍历直接实现的接口
                   if (((t = ts[i]) instanceof ParameterizedType) &&   // 该接口实现了泛型
                       ((p = (ParameterizedType)t).getRawType() == // 获取接口不带参数部分的类型对象
                        Comparable.class) &&   //  该类型是Comparable
                       (as = p.getActualTypeArguments()) != null &&    // 获取泛型参数数组
                       as.length == 1 && as[0] == c)   // 只有一个泛型参数，且该实现类型是该类型本身
                       return c;   // 返回该类型
               }
           }
       }
       return null;
   }

compareComparables 方法

1
2
3
4
5
6
7
8
9
10
11
/**
 * Returns k.compareTo(x) if x matches kc (k's screened comparable
 * class), else 0.
 * 如果x的类型是kc，返回 k.compareTo(x) 的比较结果
 * 如果x为空，或者类型不是kc，返回0
 */
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

tableSizeFor 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Returns a power of two size for the given target capacity.
 * 返回给定数值的比第一个比它大的2的幂次方的数
 */
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;
}

该方法是为了在构造函数中，把传入的指定容量转化为2的幂次方的整数，保证HashMap的容量为2的幂次方。

字段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * table数组，存放HashMap的所有元素的容器
 * 在第一次使用的时候初始化，并且可以根据需要调整大小
 * 当分配时，长度总是为2的幂次方
 * 在某些操作中容忍长度为零，以允许当前不需要的引导机制
 */
transient Node<K,V>[] table;

/**
 * 保存缓存的 entrySet 
 * AbstractMap字段用于keySet（）和values（）
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * HashMap中的包含的键值对数量
 */
transient int size;

/**
 * 该HashMap经过结构修改的次数
 * 结构修改指的是更改HashMap中的键值对数量或者以其他方式修改其内部结构（例如：rehash）
 * 该字段用于在迭代器中的快速失败（fail-fast），抛出 ConcurrentModificationException 的异常
 * 因为HashMap时线程不安全的容器，所以当A线程遍历时HashMap时，还没有遍历到的部分，被线程B修改，如删除
 * 那么当线程A遍历到被删除的地方时就会抛出该异常
 */
transient int modCount;

/**
 * 下一个要调整HashMap大小的值，容量乘加载因子(capacity * load factor).
 * 因为当大小超过这个值时，哈希碰撞的概率会大大增加，所以达到该值时，对HashMap扩容
 * @serial
 */
int threshold;

/**
 * 哈希表的加载因子
 * 默认为 0.75f
 * @serial
 */
final float loadFactor;

核心方法

构造方法

指定初始化容量和加载因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  /**
   * 构造具有指定初始容量和加载因子的空HashMap。
   *
   * @param  initialCapacity 初始容量
   * @param  loadFactor      加载因子
   * @throws IllegalArgumentException 如果初始容量为负或负载因子为非正时，抛出该异常
   *         
   */
  public HashMap(int initialCapacity, float loadFactor) {
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal initial capacity: " +
                                             initialCapacity);
//当指定初始容量超过最大容量（2的30次方）时，把其值设置为最大容量
      if (initialCapacity > MAXIMUM_CAPACITY)
          initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new IllegalArgumentException("Illegal load factor: " +
                                             loadFactor);
      this.loadFactor = loadFactor;
//将传入指定容量转换为最近的2的整数次方
      this.threshold = tableSizeFor(initialCapacity);
  }

指定初始化容量

1
2
3
4
5
6
7
8
9
10
11
  /**
   * 构造一个具有指定初始容量和默认加载因子(0.75)的空HashMap。
   * 
   *
   * @param  initialCapacity 初始容量
   * @throws IllegalArgumentException 如果初始容量为负时，抛出该异常
   */
  public HashMap(int initialCapacity) {
//调用指定初始化容量和加载因子的构造方法，加载因子为默认（0.75）
      this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

默认的初始化容量和加载因子

1
2
3
4
5
6
/**
 * 构造一个具有默认初始容量(16)和默认负载因子(0.75)的空HashMap。
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他字段都默认
}

使用与指定映射相同的映射

1
2
3
4
5
6
7
8
9
10
11
12
  /**
   * 使用与指定映射相同的映射构造新的HashMap。
   * HashMap是使用默认负载因子(0.75)创建的，初始容量足以容纳指定映射中的映射。
   *
   * @param   m 要在此map中放置其键值对（映射）的map
   * @throws  NullPointerException 如果指定的映射为空抛出该异常
   */
  public HashMap(Map<? extends K, ? extends V> m) {
      this.loadFactor = DEFAULT_LOAD_FACTOR;
//putMapEntries方法见核心方法putMapEntries()章节
      putMapEntries(m, false);
  }

putMapEntries方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
  /**
   * 实现了Map接口的 Map.putAll and Map 构造方法
   * 其中的加载因子等参数、是默认的
   *
   * @param m 指定map
   * @param 在最初构造此映射时为false，否则为true
   *        (传递到下面的afterNodeInsertion方法，该方法请详见允许LinkedHashMap后操作的回调节)。
   */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
       int s = m.size();
       if (s > 0) {
		//如果table未初始化，对其进行初始化
           if (table == null) { // pre-size
			//使用默认的加载因子（0.75）和传入的map的大小计算出阈值（扩容的临界值）
               float ft = ((float)s / loadFactor) + 1.0F;
               //用上一步计算出的阈值与最大容量对比，如果超过最大容量，就把它赋为最大容量
               int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
               //如果当前默认的阈值小于t，就把当前的阈值扩容为大于t的最小的2的整数次方的整数
               if (t > threshold)
                   threshold = tableSizeFor(t);
           }//如果table已经初始化，且传入的map的大小超过阈值，就对table扩容（resize()方法请在核心方法章节查看）
           else if (s > threshold)
               resize();
           //做完初始化、扩容等准备工作，现在table已经可以放下传入的map的元素了，迭代map，挨个放入table中
           for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
               K key = e.getKey();
               V value = e.getValue();
			//putVal()方法见下面
               putVal(hash(key), key, value, false, evict);
           }
       }
}

size方法

1
2
3
4
5
6
7
8
/**
 * 返回此映射中键值对的数目。
 *
 * @return 此映射中键值映对的数目。
 */
public int size() {
    return size;
}

isEmpty方法

1
2
3
4
5
6
7
8
9
  /**
   * 如果此映射不包含键值映射，则返回{@code true}。
   *
   * @return 如果此映射不包含键值映射，则返回{@code true}。
   */
  public boolean isEmpty() {
//键值对数目为零则为空
      return size == 0;
  }

get方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *返回指定键映射到的值，如果该映射不包含键的映射，则返回null。
 *
 * 更正式地说，如果这个映射包含从键k到值v的映射(key==null ?k==null:key.equals(k))，
 * 则该方法返回v;否则返回null。(最多可以有一个这样的映射。)
 *
 * 
 * 返回值为null并不一定表示映射不包含键的映射;也有可能映射显式地将键映射为null。
 * containsKey操作可用于区分这两种情况。
 * @see #put(Object, Object)
 */
public V get(Object key) {
    Node<K,V> e;
    //getNode方法见下面
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
    * 实现 Map接口的get方法 和其他相关方法
    *
    * @param hash key的hash值
    * @param key 键（key）
    * @return 返回节点，如果不存在的话返回null
    */
   final Node<K,V> getNode(int hash, Object key) {
       Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
       /**
        * 1.如果table为空，那么代表HashMap没有进行初始化
        * 2.如果table长度小于等于0，那么就代表HashMap中没有数据
        * 3.如果根据key的hash值计算出的下标处，没有结点，那么不存在以该key为键得映射
        * 满足以上三种情况得任意一种，直接返回null；只有三种情况全部满足的情况下，才进入链表/红黑树查找
        */
       if ((tab = table) != null && (n = tab.length) > 0 &&
           (first = tab[(n - 1) & hash]) != null) {
       	//检查该下标处得第一个结点，如果符合即返回
           if (first.hash == hash && // 总是检查第一个结点
               ((k = first.key) == key || (key != null && key.equals(k))))
               return first;
           //头节点不合符，那么检查头结点后面的结点
           if ((e = first.next) != null) {
           	//如果桶中的数据结构是红黑树，则用红黑树的方法查找
               if (first instanceof TreeNode)
                   return ((TreeNode<K,V>)first).getTreeNode(hash, key);
               do {
               	/**
               	 * 如果同桶中的数据结构是链表，从链表的第二个节点开始，遍历链表的每一个结点查找
               	 * e.hash == hash 比较hash值是否相等
               	 * key.equals(k) 和 (k = e.key) == key其实是一样的
               	 * Object的equals方法内部调用的就是 == 来验证是否相等
               	 * 此处体现出了严谨性
               	 */
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k))))
                       return e;
               } while ((e = e.next) != null);
           }
       }
       return null;
   }

get和getNode方法总结

从上面的源码中可以看出，get方法可以分为三个步骤：

  1. 通过hash方法得到key的hash值（hash方法在上面有详细的解释）
  2. 将上一步得到的key的hash值和key传入getNode方法，得到该key对应的Node
  3. 如果该key对应的Node为空，则返回null，否则返回Node中的value，如果Node中的value为空，那么也返回null

getNode方法步骤如下：

  1. 判断HashMap中存放数据的table的是否初始化，是否有数据（长度是否为0），根据key的hash值计算得到的该key在table中对应得下标处是否有结点；只有三种情况全部满足的情况下，才进入下标处得链表/红黑树查找，否则直接返回null
  2. 检查下标处的头节点是否匹配，匹配则返回该节点，否则检查头结点后面的结点
  3. 判断桶中存放数据的的数据结构是红黑树还是链表，如果桶中的数据结构是红黑树，则用红黑树的方法查找。
  4. 如果是链表则从链表的第二个节点开始，遍历链表的每一个结点查找，找到就返回对应的节点。
  5. 如果红黑树或链表的遍历中都没有找到，那么就返回null，代表不存在该节点。

containsKey方法

1
2
3
4
5
6
7
8
9
10
/**
 * 如果此映射包含特定键的映射，则返回true。
 * 否则返回false。
 *
 * @param   key   要测试在此映射中存在的key
 * @return {@code true} 如果此映射包含指定的key
 */
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

该方法其实本质调用了getNode的方法，判断是否存在以key的键的结点，如过Node存在则返回true，否则返回false。

put方法

1
2
3
4
5
6
7
8
9
10
11
/**
 * 将指定参数key和指定参数value插入map中，如果key已经存在，那就替换key对应的value
 *
 * @param key 指定key
 * @param value 指定value
 * @return 如果value被替换，则返回旧的value，否则返回null。当然，可能key对应的value就是null。
 */
public V put(K key, V value) {
    //putVal方法的实现就在下面
    return putVal(hash(key), key, value, false, true);
}

put方法可以分为三个步骤：

  1. 通过hash方法获取到传入的key的hash值（hash方法在上面有详细的解释）
  2. 通过putVal方法放入map中
  3. 返回putVal方法的结果

putVal方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * 实现了 Map接口的 put和 相关方法。
 *
 * @param hash key的hash值
 * @param key  键
 * @param value 要放入的值
 * @param onlyIfAbsent 如果为true，即使指定参数key在map中已经存在，也不会替换value
 * @param evict 如果为false，则该表处于创建模式。
 * @return 如果value被替换，则返回旧的value，否则返回null。当然，可能key对应的value就是null。
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /**
     * 如果table为null，则代表table没有初始化；或者table数组的长度为0，
     * 这两种情况下，调用resize方法对table进行初始化，
     * resize方法不仅可以对table扩容，还可以对table初始化
     * n用来记录table的长度
     */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /**
     * 如果通过key的hash值计算得到的下标处没有结点，那么新建一个链表结点放入
     * newNode方法调用了Node的构造方法，生成了一个新的结点。
     */
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//下面就是产生了碰撞的情况
        Node<K,V> e; K k;
        //如果第一个结点的key就与传入的key相等，那么就把这个结点记录下来，在后面覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果第一个key没有碰撞，而且桶中的结构是树，那么就调用相应的树的方法放置键值对
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        	//如果第一个key没有碰撞，而且桶中的结构是链表，那么就遍历链表
            for (int binCount = 0; ; ++binCount) {	//binCount记录了链表长度
            	//当遍历到链表尾部，新建节点然后插入链表尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    /**
                     * 如果插入后的链表长度大于等于8，那就把链表转化为树
                     * 这里减一是为了加上头结点，因为链表是从第二个结点开始遍历的
                     */
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;
                }
                //如果在链表中某个结点的key就与传入的key相等，那么就把这个结点记录下来，在后面覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果发生了结点相等的情况，那么之前就记录了下来，所以e不为null，在这里进行覆盖
        if (e != null) { 
        	//把结点的原值记录下来，用来返回
            V oldValue = e.value;
            //如果存在则覆盖或者旧节点的值为空，那么覆盖
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //回调方法，文章最后会说
            afterNodeAccess(e);
            //把旧值返回
            return oldValue;
        }
    }
    //因为上面是覆盖，所以未发生结构性改变，但是如果是插入，那么久发生了结构改变，所以modCount加一
    ++modCount;
    //如果table大小超过了阈值，那就进行扩容，扩容后面会详细讲解
    if (++size > threshold)
        resize();
    ////回调方法，文章最后会说
    afterNodeInsertion(evict);
    return null;
}

总结putVal方法，共有如下几个步骤：

  1. 判断table数组是否初始化，如果没有就进行初始化
  2. 根据key的hash值计算得到的下标处，如果该下标处没有节点，那么就新建一个结点放入桶中
  3. 如果该下标处已经存在节点，那么就代表发生了碰撞，开始对链表/红黑树进行遍历
  4. 如果第一个结点的key就与传入的key相等，那么就把这个结点记录下来，在后面覆盖；
  5. 如果第一个key没有碰撞，而且桶中的结构是树，那么就调用相应的树的方法放置键值对， 如果第一个key没有碰撞，而且桶中的结构是链表，那么就遍历链表
  6. 当遍历到链表尾部，新建节点然后插入链表尾部，然后判断链表长度，是否需要转化为红黑树，如果在遍历链表中发生了key相等，那么就把这个结点记录下来，在后面覆盖；
  7. 如果发生了key相等的情况，就对结点旧值覆盖，然后把旧值返回
  8. 如果没有发生key相等的情况，而是插入了新的结点，那么modCount和size都加一，判断size是否超过阈值，超过就扩容
  9. 返回null

resize方法

当像HashMap中不断地添加元素的时候，元素的数量就会增加，数量增大就不避免的增大了碰撞的概率。所以当元素的数量达到一个阈值的时候，就对HashMap进行扩容。当然数组是无法自动扩容的，扩容方法使用一个新的数组代替已有的容量小的数组。
resize方法非常巧妙，因为每次扩容都是翻倍，保证了数组大小为2得整数次方，同时与原来计算（n-1）&hash的结果相比，节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/**
    *  对table进行初始化或者大小翻倍的扩容。  
    * 如果为空，则按照字段阈值中包含的初始容量目标分配。
    * 否则，因为我们使用的是2的幂展开，所以每个bin中的元素必须保持相同的索引，或者在新表中以2的幂偏移量移动。
    *
    * @return 新的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;
     //如果旧的容量 > 0
       if (oldCap > 0) {
       	//如果旧的容量 > 最大容量，那么就把阈值变为最大值
           if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
               return oldTab;
           }	//如果旧容量的二倍小于规定的最大容量，并且旧的容量大于默认容量
           else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
           	//则对数组的容量和阈值进行翻倍扩容，新的容量和阈值是旧值的二倍
               newThr = oldThr << 1; // double threshold
       }//如果旧容量 = 0，而且旧临界值 > 0，那么就把容量设置为旧的阈值
       else if (oldThr > 0) // 初始容量设置为阈值
           newCap = oldThr;
       else { // 如果旧容量 = 0，且旧阈值 = 0，表示使用默认值，容量为16，阈值为容量*加载因子
           newCap = DEFAULT_INITIAL_CAPACITY;
           newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
       }
       //在当上面的条件判断中，只有oldThr > 0成立时，newThr == 0
       if (newThr == 0) {
       	 //ft为临时阈值，使用上面得到的新的容量和默认的加载因子计算得到
           float ft = (float)newCap * loadFactor;
           //这个阈值是否合法，如果合法，那就是真正的临界值，如果超出了最大容量，那么就是最大容量
           newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                     (int)ft : Integer.MAX_VALUE);
       }
       //把阈值变为新阈值
       threshold = newThr;
       @SuppressWarnings({"rawtypes","unchecked"})
       //创建一个新的数组，大小为新的容量，并且后面把旧的table中的数据全部转移到新的table中
       Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
       //把系统的table变为新的table
       table = newTab;
       //如果旧table不为空，将旧table中的元素复制到新的table中
       if (oldTab != null) {
       	//遍历旧的table的每个桶
           for (int j = 0; j < oldCap; ++j) {
               Node<K,V> e;
               //如果该桶中含有元素，那么久开始复制，先使用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<K,V>)e).split(this, newTab, j, oldCap);
                   else { // 使用两个头尾对象保持顺序，是由于链表中的元素的下标在扩容后,要么是原下标+oldCap,要么不变,下面会证实
                       Node<K,V> loHead = null, loTail = null;
                       Node<K,V> hiHead = null, hiTail = null;
                       Node<K,V> next;
                       do {//遍历链表，分别把要存放新坐标的结点和要存放旧坐标的结点放到两根链表中
                           next = e.next;
                           //如果计算得到0，那么下标没有改变，使用旧的头尾对象保存
                           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) {
                       	// 尾部节点next设置为null，代码严谨
                           loTail.next = null;
                           //下标没有改变
                           newTab[j] = loHead;
                       }
                       // 新下标对应的链表
                       if (hiTail != null) {
                           hiTail.next = null;
                         //新下标为就 旧的下标+新的容量
                           newTab[j + oldCap] = hiHead;
                       }
                   }
               }
           }
       }
       return newTab;
   }

resize方法总结：
总体可以两大部分：

  1. 首先是计算新桶数组的容量 newCap 和新阈值 newThr
  2. 将原集合的元素重新映射到新集合中
    细节的过程如下：

remove方法

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
    * 如果存在，则从此映射中删除指定键的映射，并且返回与该键相关联的值。
    *
    * @param  key 要从映射中删除其映射的键
    * @return 与key关联的值，如果没有key的映射，则为null。
    * (null返回值还可以代表将null与key关联的映射。)
    */
   public V remove(Object key) {
       Node<K,V> e;
	//removeNode方法就在下面
       return (e = removeNode(hash(key), key, null, false, true)) == null ?
           null : e.value;
   }

removeNode方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
    * 实现了 Map接口的remove方法 和其他相关方法
    *
    * @param hash key（键）的hash值
    * @param key 键
    * @param value 如果matchValue为true，则value也作为确定被删除的node的条件之一，否则忽略
    * @param matchValue 如果为true，则仅在键值都相等时删除
    * @param movable 如果为false，删除时不会移动其他节点
    * @return Node节点，如果没有，则为空
    */
   final Node<K,V> removeNode(int hash, Object key, Object value,
                              boolean matchValue, boolean movable) {
       Node<K,V>[] tab; Node<K,V> p; int n, index;
       //如果table数组不为空，且数组内有元素，且根据hash值计算得到的下标处的桶里有元素，才寻找，否则直接返回null
       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;
         //如果桶上第一个node的就是要删除的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<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);
               }
           }
           //如果得到的node不为null且(matchValue为false||node.value和参数value匹配)
           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;
               else//如果要删除的目标结点在链表中，则使用下一个结点代替该结点
                   p.next = node.next;
               //结构修改记录加一，元素个数减一
               ++modCount;
               --size;
               //回调函数，最后会讲
               afterNodeRemoval(node);
               //把删除的结点返回
               return node;
           }
       }
       //如果数组table为空或key映射到的桶为空，返回null。
       return null;
   }

总结removeNode方法为：

  1. 如果数组table为空或key映射到的桶为空，直接返回null。
  2. 如果key映射到的桶上第一个Node的就是要删除的Node，记录下来。
  3. 如果桶内不止一个Node，且桶内的结构为红黑树，记录key映射到的Node。
  4. 桶内的结构不为红黑树，那么桶内的结构就肯定为链表，遍历链表，找到key映射到的Node，记录下来。
  5. 如果被记录下来的Node不为null，则使用数据结构相对应的删除方法删除Node，++modCount;–size;
  6. 返回被删除的node。

clear方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 删除HashMap中的所有映射。
 * 这个调用返回后HashMap将为空。
 */
public void clear() {
    Node<K,V>[] tab;
    //结构修改次数+1
    modCount++;
    //如果table不为空且其中有元素，就进行清空
    if ((tab = table) != null && size > 0) {
    	//元素数量设置为零
        size = 0;
        //遍历table数组每一个桶，将桶置为null，剩下的交给让GC自动回收
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

containsValue方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 如果此HashMap中将一个或多个键映射到指定的值，则返回true。
 * 
 *
 * @param value 值，其在此映射中的存在性将被测试
 * @return 如果此映射将一个或多个键映射到指定值，则返回true，否则返回false。
 *         
 */
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    //如果table不为空且其中有元素，就进行寻找，否则直接返回false
    if ((tab = table) != null && size > 0) {
    	//遍历table数组中每个小标出处的桶寻找
        for (Node<K,V> e : tab) {
        	//遍历桶中的Node结点链
            for (; e != null; e = e.next) {
            	//如果有值匹配，就返回true
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

一些其他方法

keySet方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 返回此映射中所包含的键的 Set 视图。
 * 该 set 受映射的支持，所以对映射的更改将反映在该 set 中，反之亦然。
 * 如果在对 set 进行迭代的同时修改了映射（通过迭代器自己的 remove 操作除外），则迭代结果是不确定的。
 * 该 set 支持元素的移除，通过 Iterator.remove、 Set.remove、 removeAll、 retainAll 和 clear 操作可从该映射中移除相应的映射关系。
 * 它不支持 add 或 addAll 操作。
    *
    * @return 此映射中包含的键的 set 视图
    */
   public Set<K> keySet() {
       Set<K> ks = keySet;
       if (ks == null) {
           ks = new KeySet();
           keySet = ks;
       }
       return ks;
   }

values方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 返回此映射所包含的值的 Collection 视图。
 * 该 collection 受映射的支持，所以对映射的更改将反映在该 collection 中，反之亦然。
 * 如果在对 collection 进行迭代的同时修改了映射（通过迭代器自己的 remove 操作除外），则迭代结果是不确定的。
 * 该 collection 支持元素的移除，
 * 通过 Iterator.remove、 Collection.remove、 removeAll、 retainAll 和 clear 操作可从该映射中移除相应的映射关系。
 * 它不支持 add 或 addAll 操作。
 *
 * @return a view of the values contained in this map
 */
public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}

entrySet方法

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 返回此映射所包含的映射关系的 Set 视图。 
 * 该 set 受映射支持，所以对映射的更改将反映在此 set 中，反之亦然。
 * 如果在对 set 进行迭代的同时修改了映射（通过迭代器自己的 remove 操作，或者通过在该迭代器返回的映射项上执行 setValue 操作除外），则迭代结果是不确定的。
 * 该 set 支持元素的移除，通过 Iterator.remove、 Set.remove、 removeAll、 retainAll 和 clear 操作可从该映射中移除相应的映射关系。
 * 它不支持 add 或 addAll 操作。
 *
 * @return a set view of the mappings contained in this map
 */
public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

clone方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 返回此HashMap实例的浅拷贝:键和值本身没有克隆。
 * 浅拷贝与深拷贝的区别：
 * 简单的来说就是，在有指针的情况下，浅拷贝只是增加了一个指针指向已经存在的内存
 * 而深拷贝就是增加一个指针并且申请一个新的内存，使这个增加的指针指向这个新的内存
 * 采用深拷贝的情况下，释放内存的时候就不会出现在浅拷贝时重复释放同一内存的错误！
 *
 * @return a shallow copy of this map
 */
@SuppressWarnings("unchecked")
@Override
public Object clone() {
    HashMap<K,V> result;
    try {
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
    result.reinitialize();
    result.putMapEntries(this, false);
    return result;
}

回调方法

1
2
3
4
// 允许LinkedHashMap后操作的回调
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

这三个回调方法在之前方法中出现过，它们的作用就是在给LinkedHashMap时继承使用，在HashMap中没有实质的作用，所以方法体为空。LinkedHashMap 是 HashMap 的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。

个人总结

  1. 可以看出HashMap在扩容时的操作是很花费时间的，所以尽量在创建HashMap的时候就把容量指定，避免扩容操作，增大运行时间。
  2. 不知道有没有人想过，为什么在很多方法中，都是新建局部变量，然后把相应的数据赋给局部变量，而不是直接使用全局变量呢？例如下面这样：
    1
    2
    3
    4
    5
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    tab = table;
    n = tab.length;
    first = tab[(n - 1) & hash];
    k = first.key;

个人猜测这样做的原因是：
新定义的变量在栈顶，出栈快，局部变量，用完就销毁，提高速度，也不额外占用内存。
当然还有一种可能是因为HashMap不是线程安全的，所以可能因为使用全局变量的话会导致数据差异的原因，所以在每个方法里面，把这个方法开始的时候的数据保存下来，只对当前保存下来的数据进行运算，不影响其他线程和方法对数据的使用，同时也体现了高明的严谨性。

当然这只是个人猜测的结果，具体的原因也没有查到，所以这里就算是一个遗留的小问题吧。