原文：Java 8系列之重新认识HashMap，有删改。
JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别，深入探讨HashMap的结构实现和功能原理，文章末尾附有HashMap的put方法和resize方法的源码解析。
简介
Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示： 
下面针对各个实现类的特点做一些说明：
(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，键值都不可为null，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
简单来说，Hashtable通过给方法加synchronized实现线程安全。而ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素， 每个Segment守护一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。
分段锁可理解为，把整个Map分成了N个Segment，put和get的时候，根据key.hashCode()找到该使用哪个Segment，这个Segment做到了类似于Hashtable的线程安全，分段锁就是说用到哪部分就锁哪部分。ConcurrentHashMap键值不能为null。
(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。
通过上面的比较，我们知道了HashMap是Java的Map家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。下文我们主要结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。
存储结构
从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下图所示：
这里需要讲明白两个问题：数据底层具体存储的是什么（上图的黑点）？这样的存储方式有什么优点呢？
(1) 从源码可知，HashMap类中有一个非常重要的字段，就是Node[] table，即哈希桶数组，明显它是一个Node的数组，我们来看Node[JDK1.8]是何物：
1 static class Node<K,V> implements Map.Entry<K,V> { 2 final int hash; //用来定位数组索引位置 3 final K key; 4 V value; 5 Node<K,V> next; //链表的下一个node 6 7 Node(int hash, K key, V value, Node<K,V> next) { ... } 8 public final K getKey(){ ... } 9 public final V getValue() { ... } 10 public final String toString() { ... } 11 public final int hashCode() { ... } 12 public final V setValue(V newValue) { ... } 13 public final boolean equals(Object o) { ... } 14 }
Node是HashMap的一个内部类，实现了Map.Entry接口，本质就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。
(2) HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都是一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。例如程序执行下面代码：
map.put("美团","小美");
系统将调用”美团”这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算，下文有介绍）来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。
如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组（Node[] table）的大小，并在此基础上设计好的hash算法减少Hash碰撞。所以好的Hash算法和扩容机制至关重要。
在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知，构造函数就是对下面几个字段进行初始化：
int threshold; // 扩容阈值 final float loadFactor; // 负载因子 transient int modCount; // 出现线程问题时，负责及时抛异常 transient int size; // HashMap中实际存在的Node数量
HashMap中重要字段解析
| 参数 | 含义 |
| static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; | Node[] table 数组的默认初始化长度为16 |
| static final int MAXIMUM_CAPACITY = 1 << 30; | 数组允许的最大长度 |
| static final float DEFAULT_LOAD_FACTOR = 0.75f； | 默认的负载因子 |
| int threshold | 数组允许最大的元素数目，触发扩容的阈值（超过就需要扩容），其值为capacity * load factor |
| transient int modCount | 记录hashMap结构修改的次数，这个字段用于集合迭代时进行fail-fast策略 |
| transient int size | HashMap中存储键值对的个数 |
| final float loadFactor | 装载因子，默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，比如内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。 |
我们知道java.util.HashMap不是线程安全的，因此在使用迭代器Iterator的过程中，如果有其他线程修改了map，将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现就是通过modCount，它记录修改次数，在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map。所以遍历那些非线程安全的数据结构时，尽量使用迭代器Iterator。
在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考ttp://blog.csdn.net/liuqiyao_01/article/details/14475159，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。
这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能。想了解更多红黑树数据结构的工作原理可以参考：红黑树算法原理（从二叉搜索树讲起）。
功能实现
HashMap的内部功能实现很多，本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入讲解。
1. 确定哈希桶数组索引位置
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):
这里的Hash算法本质上就是三步：
(1) 取key的hashCode值，h = key.hashCode()；
(2) 高位参与运算，h ^ (h >>> 16)；
(3) 取模运算，h & (length-1)。
对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。
这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
下面举例说明下，n为table的长度：
2. 分析HashMap的put方法
HashMap的put方法执行过程可以通过下图来理解，自己有兴趣可以去对比源码更清楚地研究学习，源码在本文最后可以找到。
1 /** 2 * Implements Map.put and related methods 3 * 4 * @param hash hash for key 5 * @param key the key 6 * @param value the value to put 7 * @param onlyIfAbsent if true, don't change existing value 8 * @param evict if false, the table is in creation mode. 9 * @return previous value, or null if none 10 */ 11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 12 boolean evict) { 13 Node<K,V>[] tab; Node<K,V> p; int n, i; 14 // 默认容量初始化 15 if ((tab = table) == null || (n = tab.length) == 0) 16 n = (tab = resize()).length; 17 // 如果table[i]为空，那么p就是该位置的第一个节点 18 // 新建这个节点，放到table[i]的位置中 19 if ((p = tab[i = (n - 1) & hash]) == null) 20 tab[i] = newNode(hash, key, value, null); 21 // 如果已经存在了该位置已经有了头节点 22 else { 23 Node<K,V> e; K k; 24 // 如果tab[i]的key和输入的key相同，直接把该节点赋给e 25 if (p.hash == hash && 26 ((k = p.key) == key || (key != null && key.equals(k)))) 27 e = p; 28 // 判断tab[i]是否为红黑树节点 29 else if (p instanceof TreeNode) 30 // 如果key已存在，则返回旧节点，否则返回null 31 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 32 else { // 到这一步，tab[i]就是链表 33 // 遍历整个链表 34 for (int binCount = 0; ; ++binCount) { 35 if ((e = p.next) == null) { 36 // 如果p.next为空就插入新节点 37 p.next = newNode(hash, key, value, null); 38 // 如果链表节点数目大于阈值(默认8)，那么就转换为红黑树 39 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 40 treeifyBin(tab, hash); 41 break; 42 } 43 // 如果e=p.next与输入的key相同，就break 44 if (e.hash == hash && 45 ((k = e.key) == key || (key != null && key.equals(k)))) 46 break; 47 // 交换变量值，进入下一次遍历 48 p = e; 49 } 50 } 51 // 到这里为止，如果e不为空,证明e所对应的key已经存在 52 // 则覆盖旧值 53 if (e != null) { // existing mapping for key 54 V oldValue = e.value; 55 if (!onlyIfAbsent || oldValue == null) 56 e.value = value; 57 afterNodeAccess(e); 58 return oldValue; 59 } 60 } 61 // 记录内部结构修改的次数 62 ++modCount; 63 // 如果当前数组的大小超过了阈值，则需要扩容 64 if (++size > threshold) 65 resize(); 66 afterNodeInsertion(evict); 67 return null; 68 }
3. 扩容机制
HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。
首先举个例子直观感受下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组resize成4，然后所有的Node重新rehash的过程。
简单说就是换一个更大的数组重新映射。下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码，写的很赞，在本文最后可以找到。
1 /** 2 * 扩容方法 3 */ 4 final Node<K,V>[] resize() { 5 // 获取当前的数组 6 Node<K,V>[] oldTab = table; 7 // 获取旧的capacity 8 int oldCap = (oldTab == null) ? 0 : oldTab.length; 9 // threshold = loadFactor * capacity 10 int oldThr = threshold; 11 int newCap, newThr = 0; 12 if (oldCap > 0) { 13 // 超过最大值就不扩充了 14 if (oldCap >= MAXIMUM_CAPACITY) { 15 threshold = Integer.MAX_VALUE; 16 return oldTab; 17 } 18 // newThr和newThr都扩容2倍 19 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 20 oldCap >= DEFAULT_INITIAL_CAPACITY) 21 newThr = oldThr << 1; // double threshold 22 } 23 // 下面用于首次初始化table 24 // 带参初始化会进入这里,主要是为了重新算threshold 25 else if (oldThr > 0) 26 newCap = oldThr; 27 // 不带参初始化会进入这里 28 else { 29 newCap = DEFAULT_INITIAL_CAPACITY; 30 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 31 } 32 if (newThr == 0) { 33 float ft = (float)newCap * loadFactor; 34 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 35 (int)ft : Integer.MAX_VALUE); 36 } 37 // 赋予新的阈值 38 threshold = newThr; 39 @SuppressWarnings({"rawtypes","unchecked"}) 40 // 创建一个新的Node数组 41 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 42 table = newTab; 43 44 // 到此为止,如果是第一次扩容（初始化,下面的代码是不会运行的 45 if (oldTab != null) { 46 // 遍历旧的数组(buckets) 47 for (int j = 0; j < oldCap; ++j) { 48 Node<K,V> e; 49 if ((e = oldTab[j]) != null) { 50 oldTab[j] = null; 51 // 如果该桶只有一个节点，计算新的buckets的索引并放入 52 if (e.next == null) 53 newTab[e.hash & (newCap - 1)] = e; 54 // 如果是一个树节点,进行红黑树复制 55 else if (e instanceof TreeNode) 56 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 57 else { 58 // 保证顺序 59 // 链表中的元素的下标在扩容后,要么是原下标+oldCap,要么不变 60 // 所以定义两个头两个尾 61 Node<K,V> loHead = null, loTail = null; 62 Node<K,V> hiHead = null, hiTail = null; 63 Node<K,V> next; 64 65 // 遍历桶中的链表 66 do { 67 68 // 获取当前节点的下一个节点 69 next = e.next; 70 // e.hash & oldCap == 0,说明即使扩充了新链之后， 71 // 还是在原来的索引上 72 if ((e.hash & oldCap) == 0) { 73 74 // 如果loTail == null 说明是第一个元素，把这个元素赋给loHead 75 if (loTail == null) 76 loHead = e; 77 else 78 // 如果不是第一个元素,则加入到尾部 79 loTail.next = e; 80 loTail = e; 81 } 82 // 如果走下面的代码,则说明,新的元素的key值的hash已经超过了oldCap, 83 // 所有要加入到新扩充的链表中 84 else { 85 if (hiTail == null) 86 hiHead = e; 87 else 88 hiTail.next = e; 89 hiTail = e; 90 } 91 } while ((e = next) != null); 92 // 这里为止，产生了两条新的链表 93 // 一条是原来位置上的，一条在j+oldCap的索引上 94 if (loTail != null) { 95 loTail.next = null; 96 // 下标指向新链表的第一个元素 97 newTab[j] = loHead; 98 } 99 // 这一条链是超出了oldCap的索引的那些元素 100 if (hiTail != null) { 101 hiTail.next = null; 102 // 下标j + oldCap指向第二个链表的头,原因是e.hash & oldCap ==0 说明, 103 // 之前的容量还没有填满,直到 !=0 的时候,才表示之前的元素已经填满, 104 // 所以下标, 就变成了j+oldCap 105 newTab[j + oldCap] = hiHead; 106 } 107 } 108 } 109 } 110 } 111 return newTab; 112 }
线程安全性
在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。主要是多线程同时put时，如果同时触发了rehash操作，会导致HashMap中的链表中出现循环节点，进而使得后面get的时候，会死循环。具体原因可以看原文或者这篇文章：
http://blog.csdn.net/xuefeng0707/article/details/40797085
遍历Map对象
既然java中的所有map都实现了Map接口，以下方法适用于任何map实现（HashMap, TreeMap, LinkedHashMap, Hashtable, 等等）：
方法一： 在for-each循环中使用entries来遍历
这是最常见的并且在大多数情况下也是最可取的遍历方式。在键值都需要时使用。但是如果你遍历的是一个空的map对象，for-each循环将抛出NullPointerException，因此在遍历前你总是应该检查空引用。
Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (Map.Entry<Integer, Integer> entry : map.entrySet()) { System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue()); }
方法二：在for-each循环中遍历keys或values
如果只需要map中的键或者值，你可以通过性能稍好的keySet()或values()来实现遍历，而不是用entrySet()。
Map<Integer, Integer> map = new HashMap<Integer, Integer>(); //遍历map中的键 for (Integer key : map.keySet()) { System.out.println("Key = " + key); } //遍历map中的值 for (Integer value : map.values()) { System.out.println("Value = " + value); }
方法三：使用Iterator遍历
Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // 使用泛型 Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator(); while (entries.hasNext()) { Map.Entry<Integer, Integer> entry = entries.next(); System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue()); }
你也可以在keySet和values上应用同样的方法。
该种方式看起来冗余却有其优点所在。首先，在老版本java中这是惟一遍历map的方式。另一个好处是，你可以在遍历时调用iterator.remove()来删除 entries，另两个方法则不能。
小结
(1) 扩容是一个特别耗性能的操作，所以使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
(2) HashMap是线程不安全的，在并发的环境中建议使用ConcurrentHashMap。
(3) JDK1.8引入红黑树大程度优化了HashMap的性能，这主要体现在hash算法不均匀时，即产生的链表非常长，这时把链表转为红黑树可以将复杂度从O(n)降到O(logn)。
(4）HashMap是如何工作的？面试时可以这么回答：
HashMap在Map.Entry静态内部类实现中存储key-value对。HashMap使用哈希算法，在put和get方法中，它使用hashCode()和equals()方法。当我们通过传递key-value对调用put方法的时候，HashMap使用Key hashCode()和哈希算法来找出存储key-value对的索引。Entry存储在LinkedList中，所以如果存在entry，它使用equals()方法来检查传递的key是否已经存在，如果存在，它会覆盖value，如果不存在，它会创建一个新的entry然后保存。当我们通过传递key调用get方法时，它再次使用hashCode()来找到数组中的索引，然后使用equals()方法找出正确的Entry，然后返回它的值。
问题思考
1.HashMap的table为什么是transient的？
transient Node<K,V>[] table;
看到table用了transient修饰，也就是说table里面的内容全都不会被序列化。因为HashMap是基于HashCode的，HashCode作为Object的方法，是native的：
public native int hashCode();
这意味着的是：HashCode和底层实现相关，不同的虚拟机可能有不同的HashCode算法。再进一步说得明白些就是，可能同一个Key在虚拟机A上的HashCode=1，在虚拟机B上的HashCode=2，在虚拟机C上的HashCode=3。
这就有问题了，Java自诞生以来，就以跨平台性作为最大卖点，好了，如果table不被transient修饰，在虚拟机A上可以用的程序到虚拟机B上可以用的程序就不能用了，失去了跨平台性，因为：
1、Key在虚拟机A上的HashCode=100，连在table[4]上
2、Key在虚拟机B上的HashCode=101，这样，就去table[5]上找Key，明显找不到
整个代码就出问题了。因此，为了避免这一点，Java采取了重写自己序列化table的方法，在writeObject选择将key和value追加到序列化的文件最后面：
private void writeObject(java.io.ObjectOutputStream s) throws IOException { int buckets = capacity(); // Write out the threshold, loadfactor, and any hidden stuff s.defaultWriteObject(); s.writeInt(buckets); s.writeInt(size); internalWriteEntries(s); } // Called only from writeObject, to ensure compatible ordering. void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException { Node<K,V>[] tab; // 对每个key和value进行序列化 if (size > 0 && (tab = table) != null) { for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) { s.writeObject(e.key); s.writeObject(e.value); } } } }
而在readObject的时候重构HashMap数据结构：
private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold (ignored), loadfactor, and any hidden stuff s.defaultReadObject(); reinitialize(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new InvalidObjectException("Illegal load factor: " + loadFactor); s.readInt(); // 忽略掉buckets（其实跟size相等） int mappings = s.readInt(); // 读取size if (mappings < 0) throw new InvalidObjectException("Illegal mappings count: " + mappings); else if (mappings > 0) { // (if zero, use defaults) // Size the table using given load factor only if within // range of 0.25...4.0 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f); float fc = (float)mappings / lf + 1.0f; int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ? DEFAULT_INITIAL_CAPACITY : (fc >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)fc)); float ft = (float)cap * lf; threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ? (int)ft : Integer.MAX_VALUE); // Check Map.Entry[].class since it's the nearest public type to // what we're actually creating. SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, cap); @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] tab = (Node<K,V>[])new Node[cap]; table = tab; // 读取key和value，并且重新计算hash值，然后放入hashMap // Read the keys and values, and put the mappings in the HashMap for (int i = 0; i < mappings; i++) { @SuppressWarnings("unchecked") K key = (K) s.readObject(); @SuppressWarnings("unchecked") V value = (V) s.readObject(); putVal(hash(key), key, value, false, false); } } }
一种麻烦的方式，但却保证了跨平台性。
这个例子也告诉了我们：尽管使用的虚拟机大多数情况下都是HotSpot，但是也不能对其它虚拟机不管不顾，有跨平台的思想是一件好事
2.HashMap和Hashtable的区别
HashMap和Hashtable是一组相似的键值对集合，它们的区别也是面试常被问的问题之一，我这里简单总结一下HashMap和Hashtable的区别：
1、Hashtable是线程安全的，Hashtable所有对外提供的方法都使用了synchronized，也就是同步，而HashMap则是线程非安全的
2、Hashtable不允许空的value，空的value将导致空指针异常，而HashMap则无所谓，没有这方面的限制
3、上面两个缺点是最主要的区别，另外一个区别无关紧要，我只是提一下，就是两个的rehash算法不同.