HashMap的实现原理深入剖析

1.HashMap概述：

      HashMap是基于哈希表的Map接口的非同步实现。其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

      HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrentHashMap。

      HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。

      HashMap存数据的过程是：
      HashMap内部维护了一个存储数据的Entry数组，HashMap采用链表解决冲突，每一个Entry本质上是一个单向链表。当准备添加一个key-value对时，首先通过hash(key)方法计算hash值，然后通过indexFor(hash,length)求该key-value对的存储位置，计算方法是先用hash&0x7FFFFFFF后，再对length取模，这就保证每一个key-value对都能存入HashMap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入链表头。

      HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。


2.HashMap的数据结构：

   在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。




      HashMap内存储数据的Entry数组默认是16，如果没有对Entry扩容机制的话，当存储的数据一多，Entry内部的链表会很长，这就失去了HashMap的存储意义了。所以HasnMap内部有自己的扩容机制。HashMap内部有：

      变量size，它记录HashMap的底层数组中已用槽的数量；

      变量threshold，它是HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）   

      变量DEFAULT_LOAD_FACTOR = 0.75f，默认加载因子为0.75

      HashMap扩容的条件是：当size大于threshold时，对HashMap进行扩容 

      扩容是是新建了一个HashMap的底层数组，而后调用transfer方法，将就HashMap的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。 很明显，扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用HashMap的时，最好能提前预估下HashMap中元素的个数，这样有助于提高HashMap的性能。

      HashMap共有四个构造方法。构造方法中提到了两个很重要的参数：初始容量和加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中槽的数量（即哈希数组的长度），初始容量是创建哈希表时的容量（从构造函数中可以看出，如果不指明，则默认为16），加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 resize 操作（即扩容）。

      如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。

       另外，无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方


   从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。


源码如下：
Java代码
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/ 
transient Entry[] table; 
 
static class Entry<K,V> implements Map.Entry<K,V> { 
    final K key; 
    V value; 
    Entry<K,V> next; 
    final int hash; 
    …… 
} 

   可以看出，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。

3.HashMap的存取实现：
   1) 存储：

Java代码
public V put(K key, V value) { 
    // HashMap允许存放null键和null值。 
    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。 
    if (key == null) 
        return putForNullKey(value); 
    // 根据key的keyCode重新计算hash值。 
    int hash = hash(key.hashCode()); 
    // 搜索指定hash值在对应table中的索引。 
    int i = indexFor(hash, table.length); 
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。 
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
        Object k; 
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
            V oldValue = e.value; 
            e.value = value; 
            e.recordAccess(this); 
            return oldValue; 
        } 
    } 
    // 如果i索引处的Entry为null，表明此处还没有Entry。 
    modCount++; 
    // 将key、value添加到i索引处。 
    addEntry(hash, key, value, i); 
    return null; 
} 

   从上面的源代码中可以看出：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

put 方法过程：
1.程序首先计算该key的hashCode()值
2.然后对该哈希码值进行再哈希
3.然后把哈希值和(数组长度-1)进行按位与操作，得到存储的数组下标
4.如果该位置处设有链表节点，那么就直接把包含<key,value>的节点放入该位置。如果该位置有结点，就对链表进行遍历，看是否有hash,key和要放入的节点相同的节点，如果有的话，就替换该节点的value值，如果没有相同的话，就创建节点放入值，并把该节点插入到链表表头(头插法)。


   addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的i索引处。addEntry 是 HashMap 提供的一个包访问权限的方法，代码如下：

Java代码
void addEntry(int hash, K key, V value, int bucketIndex) { 
    // 获取指定 bucketIndex 索引处的 Entry  
    Entry<K,V> e = table[bucketIndex]; 
    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry 
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
    // 如果 Map 中的 key-value 对的数量超过了极限 
    if (size++ >= threshold) 
    // 把 table 对象的长度扩充到原来的2倍。 
        resize(2 * table.length); 
} 

   当系统决定存储HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。
   hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。

Java代码
static int hash(int h) { 
    h ^= (h >>> 20) ^ (h >>> 12); 
    return h ^ (h >>> 7) ^ (h >>> 4); 
} 

   我们可以看到在HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。
   对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，在HashMap中是这样做的：调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：

Java代码
static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

   这个方法非常巧妙，它通过 h & (table.length -1) 来得到该对象的保存位，而HashMap底层数组的长度总是 2 的 n 次方，这是HashMap在速度上的优化。在 HashMap 构造器中有如下代码：

Java代码
int capacity = 1; 
    while (capacity < initialCapacity) 
        capacity <<= 1; 
   这段代码保证初始化时HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方。
当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
   这看上去很简单，其实比较有玄机的，我们举个例子来说明：
   假设数组长度分别为15和16，优化后的hash码分别为8和9，那么&运算后的结果如下：
      




   从上面的例子中可以看出：当它们和15-1（1110）“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链 表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hash值会与15-1（1110）进行“与”，那么 最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！而当数组长度为16时，即为2的n次方时，2n-1得到的二进制数的每个位上的值都为1，这使得在低位上&时，得到的和原hash的低位相同，加之hash(int h)方法对key的hashCode的进一步优化，加入了高位计算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。
  
   所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

为何数组的长度是2的n次方呢?

1.这个方法非常巧妙，它通过h & (table.length-1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，2^n -1得到的二进制数的每个位上的值都为1,那么与全部为1的一一个数进行与操作，速度会大大提升。

2.当length总是2的n次方时，h& (length-1)运 算等价王对length取模，也就是h%length,但是&比%县有更高的效率。

3.当数组长度为2的n次幂的时候，不同的key算得的index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰擁的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。


   根据上面 put 方法的源代码可以看出，当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

   2) 读取：

Java代码
public V get(Object key) { 
    if (key == null) 
        return getForNullKey(); 
    int hash = hash(key.hashCode()); 
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
        e != null; 
        e = e.next) { 
        Object k; 
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
            return e.value; 
    } 
    return null; 
} 

   有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

get方法过程：
1.首先通过key的两次hash后的值与数组的长度-1进行与操作，定位到数组的某个位置，
2.然后对该列的链表进行遍历，一般情况下，hashMap的这种查找速度是非常快的，hash 值相同的元( O就会造成链表中数据很多，而链表中的数据查找是通过应历所有链表中的元素进行的，这可能会影响到查找速度，找到即返回。特别注意:当返回为null时，你不能判断是没有找到指定元素，还是在hashmap中存着一一个value为null的元素，因为hashmap允许value为null.

 
   3) 归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

4.HashMap的resize（rehash）：

   当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
   那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

5.HashMap的性能参数：

   HashMap 包含如下几个构造器：
   HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
   HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
   HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。
   HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。
   initialCapacity：HashMap的最大容量，即为底层数组的长度。
   loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。
   负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。
   HashMap的实现中，通过threshold字段来判断HashMap的最大容量：

Java代码

threshold = (int)(capacity * loadFactor); 

   结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：

Java代码
if (size++ >= threshold)    
    resize(2 * table.length);   

6.Fail-Fast机制：

   我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。
   这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

Java代码
HashIterator() { 
    expectedModCount = modCount; 
    if (size > 0) { // advance to first entry 
    Entry[] t = table; 
    while (index < t.length && (next = t[index++]) == null) 
        ; 
    } 
} 

   在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：
   注意到modCount声明为volatile，保证线程之间修改的可见性。

Java代码
final Entry<K,V> nextEntry() {    
    if (modCount != expectedModCount)    
        throw new ConcurrentModificationException(); 

   在HashMap的API中指出：

   由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。
   注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。



Hashtable和HashMap的相同点：

HashMap和Hashtable都是存储“键值对(key-value)”的散列表，而且都是采用拉链法实现的。

存储的思想都是：通过table数组存储，数组的每一个元素都是一个Entry；而一个Entry就是一个单向链表，Entry链表中的每一个节点就保存了key-value键值对数据。

添加key-value键值对：首先，根据key值计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据数组索引找到Entry(即，单向链表)，再遍历单向链表，将key和链表中的每一个节点的key进行对比。若key已经存在Entry链表中，则用该value值取代旧的value值；若key不存在Entry链表中，则新建一个key-value节点，并将该节点插入Entry链表的表头位置。

删除key-value键值对：删除键值对，相比于“添加键值对”来说，简单很多。首先，还是根据key计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据索引找出Entry(即，单向链表)。若节点key-value存在与链表Entry中，则删除链表中的节点即可。


 
Hashtable与HashMap的区别：

1、继承的父类不同：

Hashtable继承的是Dictionary类，HashMap继承的是AbstractMap，但两者都实现了Map接口。

HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。

HashMap的定义:

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable { ... }

Hashtable的定义:

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable { ... }

(1) HashMap和Hashtable都实现了Map、Cloneable、java.io.Serializable接口。
      实现了Map接口，意味着它们都支持key-value键值对操作。支持“添加key-value键值对”、“获取key”、“获取value”、“获取map大小”、“清空map”等基本的key-value键值对操作。
      实现了Cloneable接口，意味着它能被克隆。
      实现了java.io.Serializable接口，意味着它们支持序列化，能通过序列化去传输。

(2). HashMap继承于AbstractMap，而Hashtable继承于Dictionary
      Dictionary是一个抽象类，它直接继承于Object类，没有实现任何接口。虽然Dictionary也支持“添加key-value键值对”、“获取value”、“获取大小”等基本操作，但它的API函数比Map少；而且Dictionary一般是通过Enumeration(枚举类)去遍历，Map则是通过Iterator(迭代器)去遍历。 然而‘由于Hashtable也实现了Map接口，所以，它即支持Enumeration遍历，也支持Iterator遍历。
      AbstractMap是一个抽象类，它实现了Map接口的绝大部分API函数；为Map的具体实现类提供了极大的便利。


2、是否允许null：

HashMap可以允许存在一个 null 的 key 和任意个 null 的 value，不过建议尽量避免这样使用null作为 key，HashMap以null作为key时，总是存储在table数组的第一个节点table[0]为头结点的链表中；Hashtable中的 key 和 value 都不允许为 null 。

在HashMap中，当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。

（1）当HashMap遇到为null的key时，它会调用putForNullKey方法来进行处理。对于value没有进行任何处理，只要是对象都可以。

if (key == null)
            return putForNullKey(value);

（2）如果在Hashtable中有类似put(null,null)的操作，编译时可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常。

if (value == null) {
            throw new NullPointerException();
        }

3、Hashtable的方法是线程安全的，底层的每个方法都使用synchronized的，而HashMap的方法多线程不安全。

虽然HashMap不是线程安全的，但是它的效率会比Hashtable要好很多。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。

4、遍历不同：HashMap仅支持Iterator的遍历方式，Hashtable支持Iterator和Enumeration两种遍历方式。

（1）HashMap 的Iterator 使用的是fail-fast 迭代器，当有其他线程改变了 HashMap 的结构（增加、删除、修改元素），将会抛出ConcurrentModificationException。

（2）JDK8之前的版本中，Hashtable是没有fast-fail机制的。在JDK8及以后的版本中 ，HashTable也是使用fast-fail的， 源码如下： 

if (expectedModCount != modCount) {
     throw new ConcurrentModificationException();
  }

modCount 的使用类似于并发编程中的 CAS( Compare and Swap) 技术，每次在发生增删改操作的时候，都会出现modCount++的动作，而modcount可以理解为是当前hashtable的状态。每发生一次操作，状态+1。设置这个状态，主要是用于hashtable 等容器类在迭代时，判断数据是否过时时使用的。尽管hashtable采用了原生的同步锁来保护数据安全。但是在出现迭代数据的时候，则无法保证边迭代，边正确操作。于是使用这个值来标记状态。一旦在迭代的过程中状态发生了改变，则会快速抛出一个异常，终止迭代行为。

5、是否提供contains方法：

（1）HashMap把Hashtable的contains()方法去掉了，改成containsValue 和 containsKey ，因为contains() 方法容易让人引起误解；

（2）Hashtable则保留了contains，containsValue 和 containsKey 三个方法 ，其中 contains 和 containsValue 功能相同。

6、内部实现使用的数值初始化 和 扩容方式不同：

HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。
Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”。

HashMap默认的“加载因子”是0.75, 默认的容量大小是16。

当HashMap的 “实际容量” >= “阈值”时，(阈值 = 总的容量 * 加载因子)，就将HashMap的容量翻倍。

Hashtable默认的“加载因子”是0.75, 默认的容量大小是11。

当Hashtable的 “实际容量” >= “阈值”时，(阈值 = 总的容量 x 加载因子)，就将变为“原始容量x2 + 1”。

（1）两者的默认负载因子都是0.75，但Hashtable扩容时，容量变为原来的2倍+1，HashMap扩容时，将容量变成原来的2倍；Hashtable在不制定容量的情况下默认容量是11，也就是说Hashtable会尽量使用素数、奇数，而HashMap 的默认容量 为16，Hashtable不要求底层数组的容量为2的整数次幂，而 HashMap 要求一定为2的整数次幂。

（2）之所以会有这样的不同，是因为Hashtable和HashMap设计时的侧重点不同。Hashtable的侧重点是哈希的结果更加均匀，使得哈希冲突减少。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。而HashMap则更加关注hash的计算效率问题。在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。HashMap为了加快hash的速度，将哈希表的大小固定为了2的幂。当然这引入了哈希分布不均匀的问题，所以HashMap为解决这问题，又对hash算法做了一些改动。这从而导致了Hashtable和HashMap的计算hash值的方法不同。

7、hash 值不同：

（1）Hashtable直接使用Object的hashCode()，hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值，然后再使用去取模运算来获得最终的位置。 这里一般先用 hash & 0x7FFFFFFF 后，再对length取模，&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而 hash & 0x7FFFFFFF 后，只有符号外改变，而后面的位都不变。Hashtable在计算元素的位置时需要进行一次除法运算，而除法运算是比较耗时的。 

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

（2）为了提高计算效率，HashMap 将哈希表的大小固定为了2的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。HashMap的效率虽然提高了，但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高，HashMap的效率虽然提高了，但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高。而计算位运算为了解决这个问题，HashMap重新根据hashcode计算hash值后，又对hash值做了一些运算来打散数据。使得取得的位置更加分散，从而减少了hash冲突。当然了，为了高效，HashMap只做了一些简单的位处理。从而不至于把使用2 的幂次方带来的效率提升给抵消掉。

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

 

HashMap源码剖析

package java.util; 
import java.io.*; 

public class HashMap<K,V> 
    extends AbstractMap<K,V> 
    implements Map<K,V>, Cloneable, Serializable 
{ 

    // 默认的初始容量（容量为HashMap中槽的数目）是16，且实际容量必须是2的整数次幂。 
    static final int DEFAULT_INITIAL_CAPACITY = 16; 

    // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换） 
    static final int MAXIMUM_CAPACITY = 1 << 30; 

    // 默认加载因子为0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f; 

    // 存储数据的Entry数组，长度是2的幂。 
    // HashMap采用链表法解决冲突，每一个Entry本质上是一个单向链表 
    transient Entry[] table; 

    // HashMap的底层数组中已用槽的数量 
    transient int size; 

    // HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子） 
    int threshold; 

    // 加载因子实际大小 
    final float loadFactor; 

    // HashMap被改变的次数 
    transient volatile int modCount; 

    // 指定“容量大小”和“加载因子”的构造函数 
    public HashMap(int initialCapacity, float loadFactor) { 
        if (initialCapacity < 0) 
            throw new IllegalArgumentException("Illegal initial capacity: " + 
                                               initialCapacity); 
        // HashMap的最大容量只能是MAXIMUM_CAPACITY 
        if (initialCapacity > MAXIMUM_CAPACITY) 
            initialCapacity = MAXIMUM_CAPACITY; 
//加载因此不能小于0
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
            throw new IllegalArgumentException("Illegal load factor: " + 
                                               loadFactor); 

        // 找出“大于initialCapacity”的最小的2的幂 
        int capacity = 1; 
        while (capacity < initialCapacity) 
            capacity <<= 1; 

        // 设置“加载因子” 
        this.loadFactor = loadFactor; 
        // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。 
        threshold = (int)(capacity * loadFactor); 
        // 创建Entry数组，用来保存数据 
        table = new Entry[capacity]; 
        init(); 
    } 


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

    // 默认构造函数。 
    public HashMap() { 
        // 设置“加载因子”为默认加载因子0.75 
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
        // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。 
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 
        // 创建Entry数组，用来保存数据 
        table = new Entry[DEFAULT_INITIAL_CAPACITY]; 
        init(); 
    } 

    // 包含“子Map”的构造函数 
    public HashMap(Map<? extends K, ? extends V> m) { 
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); 
        // 将m中的全部元素逐个添加到HashMap中 
        putAllForCreate(m); 
    } 

    //求hash值的方法，重新计算hash值
    static int hash(int h) { 
        h ^= (h >>> 20) ^ (h >>> 12); 
        return h ^ (h >>> 7) ^ (h >>> 4); 
    } 

    // 返回h在数组中的索引值，这里用&代替取模，旨在提升效率
    // h & (length-1)保证返回值的小于length 
    static int indexFor(int h, int length) { 
        return h & (length-1); 
    } 

    public int size() { 
        return size; 
    } 

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

    // 获取key对应的value 
    public V get(Object key) { 
        if (key == null) 
            return getForNullKey(); 
        // 获取key的hash值 
        int hash = hash(key.hashCode()); 
        // 在“该hash值对应的链表”上查找“键值等于key”的元素 
        for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
             e != null; 
             e = e.next) { 
            Object k; 
//判断key是否相同
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
                return e.value; 
        }
//没找到则返回null
        return null; 
    } 

    // 获取“key为null”的元素的值 
    // HashMap将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！ 
    private V getForNullKey() { 
        for (Entry<K,V> e = table[0]; e != null; e = e.next) { 
            if (e.key == null) 
                return e.value; 
        } 
        return null; 
    } 

    // HashMap是否包含key 
    public boolean containsKey(Object key) { 
        return getEntry(key) != null; 
    } 

    // 返回“键为key”的键值对 
    final Entry<K,V> getEntry(Object key) { 
        // 获取哈希值 
        // HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值 
        int hash = (key == null) ? 0 : hash(key.hashCode()); 
        // 在“该hash值对应的链表”上查找“键值等于key”的元素 
        for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
             e != null; 
             e = e.next) { 
            Object k; 
            if (e.hash == hash && 
                ((k = e.key) == key || (key != null && key.equals(k)))) 
                return e; 
        } 
        return null; 
    } 

    // 将“key-value”添加到HashMap中 
    public V put(K key, V value) { 
        // 若“key为null”，则将该键值对添加到table[0]中。 
        if (key == null) 
            return putForNullKey(value); 
        // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。 
        int hash = hash(key.hashCode()); 
        int i = indexFor(hash, table.length); 
        for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
            Object k; 
            // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！ 
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
                V oldValue = e.value; 
                e.value = value; 
                e.recordAccess(this); 
                return oldValue; 
            } 
        } 

        // 若“该key”对应的键值对不存在，则将“key-value”添加到table中 
        modCount++;
//将key-value添加到table[i]处
        addEntry(hash, key, value, i); 
        return null; 
    } 

    // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置 
    private V putForNullKey(V 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; 
            } 
        } 
        // 如果没有存在key为null的键值对，则直接题阿见到table[0]处! 
        modCount++; 
        addEntry(0, null, value, 0); 
        return null; 
    } 

    // 创建HashMap对应的“添加方法”， 
    // 它和put()不同。putForCreate()是内部方法，它被构造函数等调用，用来创建HashMap 
    // 而put()是对外提供的往HashMap中添加元素的方法。 
    private void putForCreate(K key, V value) { 
        int hash = (key == null) ? 0 : hash(key.hashCode()); 
        int i = indexFor(hash, table.length); 

        // 若该HashMap表中存在“键值等于key”的元素，则替换该元素的value值 
        for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
            Object k; 
            if (e.hash == hash && 
                ((k = e.key) == key || (key != null && key.equals(k)))) { 
                e.value = value; 
                return; 
            } 
        } 

        // 若该HashMap表中不存在“键值等于key”的元素，则将该key-value添加到HashMap中 
        createEntry(hash, key, value, i); 
    } 

    // 将“m”中的全部元素都添加到HashMap中。 
    // 该方法被内部的构造HashMap的方法所调用。 
    private void putAllForCreate(Map<? extends K, ? extends V> m) { 
        // 利用迭代器将元素逐个添加到HashMap中 
        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { 
            Map.Entry<? extends K, ? extends V> e = i.next(); 
            putForCreate(e.getKey(), e.getValue()); 
        } 
    } 

    // 重新调整HashMap的大小，newCapacity是调整后的容量 
    void resize(int newCapacity) { 
        Entry[] oldTable = table; 
        int oldCapacity = oldTable.length;
//如果就容量已经达到了最大值，则不能再扩容，直接返回
        if (oldCapacity == MAXIMUM_CAPACITY) { 
            threshold = Integer.MAX_VALUE; 
            return; 
        } 

        // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中， 
        // 然后，将“新HashMap”赋值给“旧HashMap”。 
        Entry[] newTable = new Entry[newCapacity]; 
        transfer(newTable); 
        table = newTable; 
        threshold = (int)(newCapacity * loadFactor); 
    } 

    // 将HashMap中的全部元素都添加到newTable中 
    void transfer(Entry[] newTable) { 
        Entry[] src = table; 
        int newCapacity = newTable.length; 
        for (int j = 0; j < src.length; j++) { 
            Entry<K,V> e = src[j]; 
            if (e != null) { 
                src[j] = null; 
                do { 
                    Entry<K,V> next = e.next; 
                    int i = indexFor(e.hash, newCapacity); 
                    e.next = newTable[i]; 
                    newTable[i] = e; 
                    e = next; 
                } while (e != null); 
            } 
        } 
    } 

    // 将"m"的全部元素都添加到HashMap中 
    public void putAll(Map<? extends K, ? extends V> m) { 
        // 有效性判断 
        int numKeysToBeAdded = m.size(); 
        if (numKeysToBeAdded == 0) 
            return; 

        // 计算容量是否足够， 
        // 若“当前阀值容量 < 需要的容量”，则将容量x2。 
        if (numKeysToBeAdded > threshold) { 
            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); 
            if (targetCapacity > MAXIMUM_CAPACITY) 
                targetCapacity = MAXIMUM_CAPACITY; 
            int newCapacity = table.length; 
            while (newCapacity < targetCapacity) 
                newCapacity <<= 1; 
            if (newCapacity > table.length) 
                resize(newCapacity); 
        } 

        // 通过迭代器，将“m”中的元素逐个添加到HashMap中。 
        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { 
            Map.Entry<? extends K, ? extends V> e = i.next(); 
            put(e.getKey(), e.getValue()); 
        } 
    } 

    // 删除“键为key”元素 
    public V remove(Object key) { 
        Entry<K,V> e = removeEntryForKey(key); 
        return (e == null ? null : e.value); 
    } 

    // 删除“键为key”的元素 
    final Entry<K,V> removeEntryForKey(Object key) { 
        // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算 
        int hash = (key == null) ? 0 : hash(key.hashCode()); 
        int i = indexFor(hash, table.length); 
        Entry<K,V> prev = table[i]; 
        Entry<K,V> e = prev; 

        // 删除链表中“键为key”的元素 
        // 本质是“删除单向链表中的节点” 
        while (e != null) { 
            Entry<K,V> next = e.next; 
            Object k; 
            if (e.hash == hash && 
                ((k = e.key) == key || (key != null && key.equals(k)))) { 
                modCount++; 
                size--; 
                if (prev == e) 
                    table[i] = next; 
                else
                    prev.next = next; 
                e.recordRemoval(this); 
                return e; 
            } 
            prev = e; 
            e = next; 
        } 

        return e; 
    } 

    // 删除“键值对” 
    final Entry<K,V> removeMapping(Object o) { 
        if (!(o instanceof Map.Entry)) 
            return null; 

        Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 
        Object key = entry.getKey(); 
        int hash = (key == null) ? 0 : hash(key.hashCode()); 
        int i = indexFor(hash, table.length); 
        Entry<K,V> prev = table[i]; 
        Entry<K,V> e = prev; 

        // 删除链表中的“键值对e” 
        // 本质是“删除单向链表中的节点” 
        while (e != null) { 
            Entry<K,V> next = e.next; 
            if (e.hash == hash && e.equals(entry)) { 
                modCount++; 
                size--; 
                if (prev == e) 
                    table[i] = next; 
                else
                    prev.next = next; 
                e.recordRemoval(this); 
                return e; 
            } 
            prev = e; 
            e = next; 
        } 

        return e; 
    } 

    // 清空HashMap，将所有的元素设为null 
    public void clear() { 
        modCount++; 
        Entry[] tab = table; 
        for (int i = 0; i < tab.length; i++) 
            tab[i] = null; 
        size = 0; 
    } 

    // 是否包含“值为value”的元素 
    public boolean containsValue(Object value) { 
    // 若“value为null”，则调用containsNullValue()查找 
    if (value == null) 
            return containsNullValue(); 

    // 若“value不为null”，则查找HashMap中是否有值为value的节点。 
    Entry[] tab = table; 
        for (int i = 0; i < tab.length ; i++) 
            for (Entry e = tab[i] ; e != null ; e = e.next) 
                if (value.equals(e.value)) 
                    return true; 
    return false; 
    } 

    // 是否包含null值 
    private boolean containsNullValue() { 
    Entry[] tab = table; 
        for (int i = 0; i < tab.length ; i++) 
            for (Entry e = tab[i] ; e != null ; e = e.next) 
                if (e.value == null) 
                    return true; 
    return false; 
    } 

    // 克隆一个HashMap，并返回Object对象 
    public Object clone() { 
        HashMap<K,V> result = null; 
        try { 
            result = (HashMap<K,V>)super.clone(); 
        } catch (CloneNotSupportedException e) { 
            // assert false; 
        } 
        result.table = new Entry[table.length]; 
        result.entrySet = null; 
        result.modCount = 0; 
        result.size = 0; 
        result.init(); 
        // 调用putAllForCreate()将全部元素添加到HashMap中 
        result.putAllForCreate(this); 

        return result; 
    } 

    // Entry是单向链表。 
    // 它是 “HashMap链式存储法”对应的链表。 
    // 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数 
    static class Entry<K,V> implements Map.Entry<K,V> { 
        final K key; 
        V value; 
        // 指向下一个节点 
        Entry<K,V> next; 
        final int hash; 

        // 构造函数。 
        // 输入参数包括"哈希值(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; 
        } 

        // 判断两个Entry是否相等 
        // 若两个Entry的“key”和“value”都相等，则返回true。 
        // 否则，返回false 
        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 (key==null   ? 0 : key.hashCode()) ^ 
                   (value==null ? 0 : value.hashCode()); 
        } 

        public final String toString() { 
            return getKey() + "=" + getValue(); 
        } 

        // 当向HashMap中添加元素时，绘调用recordAccess()。 
        // 这里不做任何处理 
        void recordAccess(HashMap<K,V> m) { 
        } 

        // 当从HashMap中删除元素时，绘调用recordRemoval()。 
        // 这里不做任何处理 
        void recordRemoval(HashMap<K,V> m) { 
        } 
    } 

    // 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。 
    void addEntry(int hash, K key, V value, int bucketIndex) { 
        // 保存“bucketIndex”位置的值到“e”中 
        Entry<K,V> e = table[bucketIndex]; 
        // 设置“bucketIndex”位置的元素为“新Entry”， 
        // 设置“e”为“新Entry的下一个节点” 
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
        // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小 
        if (size++ >= threshold) 
            resize(2 * table.length); 
    } 

    // 创建Entry。将“key-value”插入指定位置。 
    void createEntry(int hash, K key, V value, int bucketIndex) { 
        // 保存“bucketIndex”位置的值到“e”中 
        Entry<K,V> e = table[bucketIndex]; 
        // 设置“bucketIndex”位置的元素为“新Entry”， 
        // 设置“e”为“新Entry的下一个节点” 
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
        size++; 
    } 

    // HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。 
    // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。 
    private abstract class HashIterator<E> implements Iterator<E> { 
        // 下一个元素 
        Entry<K,V> next; 
        // expectedModCount用于实现fast-fail机制。 
        int expectedModCount; 
        // 当前索引 
        int index; 
        // 当前元素 
        Entry<K,V> current; 

        HashIterator() { 
            expectedModCount = modCount; 
            if (size > 0) { // advance to first entry 
                Entry[] t = table; 
                // 将next指向table中第一个不为null的元素。 
                // 这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。 
                while (index < t.length && (next = t[index++]) == null) 
                    ; 
            } 
        } 

        public final boolean hasNext() { 
            return next != null; 
        } 

        // 获取下一个元素 
        final Entry<K,V> nextEntry() { 
            if (modCount != expectedModCount) 
                throw new ConcurrentModificationException(); 
            Entry<K,V> e = next; 
            if (e == null) 
                throw new NoSuchElementException(); 

            // 注意！！！ 
            // 一个Entry就是一个单向链表 
            // 若该Entry的下一个节点不为空，就将next指向下一个节点; 
            // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。 
            if ((next = e.next) == null) { 
                Entry[] t = table; 
                while (index < t.length && (next = t[index++]) == null) 
                    ; 
            } 
            current = e; 
            return e; 
        } 

        // 删除当前元素 
        public void remove() { 
            if (current == null) 
                throw new IllegalStateException(); 
            if (modCount != expectedModCount) 
                throw new ConcurrentModificationException(); 
            Object k = current.key; 
            current = null; 
            HashMap.this.removeEntryForKey(k); 
            expectedModCount = modCount; 
        } 

    } 

    // value的迭代器 
    private final class ValueIterator extends HashIterator<V> { 
        public V next() { 
            return nextEntry().value; 
        } 
    } 

    // key的迭代器 
    private final class KeyIterator extends HashIterator<K> { 
        public K next() { 
            return nextEntry().getKey(); 
        } 
    } 

    // Entry的迭代器 
    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { 
        public Map.Entry<K,V> next() { 
            return nextEntry(); 
        } 
    } 

    // 返回一个“key迭代器” 
    Iterator<K> newKeyIterator()   { 
        return new KeyIterator(); 
    } 
    // 返回一个“value迭代器” 
    Iterator<V> newValueIterator()   { 
        return new ValueIterator(); 
    } 
    // 返回一个“entry迭代器” 
    Iterator<Map.Entry<K,V>> newEntryIterator()   { 
        return new EntryIterator(); 
    } 

    // HashMap的Entry对应的集合 
    private transient Set<Map.Entry<K,V>> entrySet = null; 

    // 返回“key的集合”，实际上返回一个“KeySet对象” 
    public Set<K> keySet() { 
        Set<K> ks = keySet; 
        return (ks != null ? ks : (keySet = new KeySet())); 
    } 

    // Key对应的集合 
    // KeySet继承于AbstractSet，说明该集合中没有重复的Key。 
    private final class KeySet extends AbstractSet<K> { 
        public Iterator<K> iterator() { 
            return newKeyIterator(); 
        } 
        public int size() { 
            return size; 
        } 
        public boolean contains(Object o) { 
            return containsKey(o); 
        } 
        public boolean remove(Object o) { 
            return HashMap.this.removeEntryForKey(o) != null; 
        } 
        public void clear() { 
            HashMap.this.clear(); 
        } 
    } 

    // 返回“value集合”，实际上返回的是一个Values对象 
    public Collection<V> values() { 
        Collection<V> vs = values; 
        return (vs != null ? vs : (values = new Values())); 
    } 

    // “value集合” 
    // Values继承于AbstractCollection，不同于“KeySet继承于AbstractSet”， 
    // Values中的元素能够重复。因为不同的key可以指向相同的value。 
    private final class Values extends AbstractCollection<V> { 
        public Iterator<V> iterator() { 
            return newValueIterator(); 
        } 
        public int size() { 
            return size; 
        } 
        public boolean contains(Object o) { 
            return containsValue(o); 
        } 
        public void clear() { 
            HashMap.this.clear(); 
        } 
    } 

    // 返回“HashMap的Entry集合” 
    public Set<Map.Entry<K,V>> entrySet() { 
        return entrySet0(); 
    } 

    // 返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象 
    private Set<Map.Entry<K,V>> entrySet0() { 
        Set<Map.Entry<K,V>> es = entrySet; 
        return es != null ? es : (entrySet = new EntrySet()); 
    } 

    // EntrySet对应的集合 
    // EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。 
    private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { 
        public Iterator<Map.Entry<K,V>> iterator() { 
            return newEntryIterator(); 
        } 
        public boolean contains(Object o) { 
            if (!(o instanceof Map.Entry)) 
                return false; 
            Map.Entry<K,V> e = (Map.Entry<K,V>) o; 
            Entry<K,V> candidate = getEntry(e.getKey()); 
            return candidate != null && candidate.equals(e); 
        } 
        public boolean remove(Object o) { 
            return removeMapping(o) != null; 
        } 
        public int size() { 
            return size; 
        } 
        public void clear() { 
            HashMap.this.clear(); 
        } 
    } 

    // java.io.Serializable的写入函数 
    // 将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中 
    private void writeObject(java.io.ObjectOutputStream s) 
        throws IOException 
    { 
        Iterator<Map.Entry<K,V>> i = 
            (size > 0) ? entrySet0().iterator() : null; 

        // Write out the threshold, loadfactor, and any hidden stuff 
        s.defaultWriteObject(); 

        // Write out number of buckets 
        s.writeInt(table.length); 

        // Write out size (number of Mappings) 
        s.writeInt(size); 

        // Write out keys and values (alternating) 
        if (i != null) { 
            while (i.hasNext()) { 
            Map.Entry<K,V> e = i.next(); 
            s.writeObject(e.getKey()); 
            s.writeObject(e.getValue()); 
            } 
        } 
    } 


    private static final long serialVersionUID = 362498820763181265L; 

    // java.io.Serializable的读取函数：根据写入方式读出 
    // 将HashMap的“总的容量，实际容量，所有的Entry”依次读出 
    private void readObject(java.io.ObjectInputStream s) 
         throws IOException, ClassNotFoundException 
    { 
        // Read in the threshold, loadfactor, and any hidden stuff 
        s.defaultReadObject(); 

        // Read in number of buckets and allocate the bucket array; 
        int numBuckets = s.readInt(); 
        table = new Entry[numBuckets]; 

        init();  // Give subclass a chance to do its thing. 

        // Read in size (number of Mappings) 
        int size = s.readInt(); 

        // Read the keys and values, and put the mappings in the HashMap 
        for (int i=0; i<size; i++) { 
            K key = (K) s.readObject(); 
            V value = (V) s.readObject(); 
            putForCreate(key, value); 
        } 
    } 

    // 返回“HashMap总的容量” 
    int   capacity()     { return table.length; } 
    // 返回“HashMap的加载因子” 
    float loadFactor()   { return loadFactor;   } 
}