1. HashMap的数据结构
数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。
数组
数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；
链表
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。
哈希表
那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。
哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 拉链法，我们可以理解为“链表的数组” ，如图：
从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12, 28%16=12, 108%16=12, 140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。 那一个线性数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。
HashMap存储的是key-value形式的键值对，这个键值对在实现中使用一个静态内部类Entry来表示，它存储了key、value、hash值、以及在hash冲突时链表中下一个元素的引用。这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。
HashMap源码中有一个Entry类型的table数组:
/** * The table, resized as necessary. Length MUST Always be a power of two. * 这个table数组成员变量是HashMap扩容所必须的,其长度必须是2的次幂 */ transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
附录HashMap$Entry的源码如下:(它存储了key、value、hash值、以及在hash冲突时链表中下一个元素的引用)
1 static class Entry<K,V> implements Map.Entry<K,V> { 2 final K key; 3 V value; 4 Entry<K,V> next; 5 int hash; 6 7 /** 8 * Creates new entry. 9 */ 10 Entry(int h, K k, V v, Entry<K,V> n) { 11 value = v; 12 next = n; 13 key = k; 14 hash = h; 15 } 16 17 public final boolean equals(Object o) { 18 if (!(o instanceof Map.Entry)) 19 return false; 20 Map.Entry e = (Map.Entry)o; 21 Object k1 = getKey(); 22 Object k2 = e.getKey(); 23 if (k1 == k2 || (k1 != null && k1.equals(k2))) { 24 Object v1 = getValue(); 25 Object v2 = e.getValue(); 26 if (v1 == v2 || (v1 != null && v1.equals(v2))) 27 return true; 28 } 29 return false; 30 } 31 32 public final int hashCode() { 33 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); 34 } 35 36 public final String toString() { 37 return getKey() + "=" + getValue(); 38 } 39 ********** 40 }
2. HashMap的存取实现
(1) put方法的实现:
1 public V put(K key, V value) { 2 // 创建时未分配空间，所以检查如果还是空表的话，就分配内存空间 3 if (table == EMPTY_TABLE) { 4 inflateTable(threshold); 5 } 6 // 对null的key进行的特殊处理 7 if (key == null) 8 return putForNullKey(value); 9 // 计算key的hashCode 10 int hash = hash(key); 11 // 根据hashCode和当前容量来确定元素在hash表中的位置，即hash桶的位置 12 int i = indexFor(hash, table.length); 13 // 检查key是否已经存在，如果已经存在，则替换旧值为新值，并返回旧值 14 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 15 Object k; 16 // 这里可以看到是根据hashCode和equals方法来判断一个key是否已经存在 17 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 18 V oldValue = e.value; 19 e.value = value; 20 e.recordAccess(this); 21 return oldValue; 22 } 23 } 24 // 增加map的修改次数，这用于实现fail-fast机制 25 modCount++; 26 // 真正把元素添加到hash表中指定的索引位置处理（也叫hash桶） 27 addEntry(hash, key, value, i); 28 // 返回null表示key之前不存在 29 return null; 30 }
上面put()源码中有关于Map初始化的方法inflateTable(),源码如下: (如何初始化并分配内存)
1 /** 2 * Inflates the table. 3 */ 4 private void inflateTable(int toSize) { 5 // Find a power of 2 >= toSize 6 //保证容量是2的整数次幂 7 int capacity = roundUpToPowerOf2(toSize); 8 // 在初始化的时候就把扩容的阙值计算好并保存，避免每次都重新计算 9 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 10 // 这里才会真正的分配内存 11 table = new Entry[capacity]; 12 // 初始化hash种子 13 initHashSeedAsNeeded(capacity); 14 } 15 /** 16 * 保证容量是2的整数次幂，并且不超过最大容量。 17 * 比如：传入的是15，值变成16，传入的是17，则会变成32， 18 * 即大于当前值且与最接近2的整数次幂的数 19 */ 20 private static int roundUpToPowerOf2(int number) { 21 // assert number >= 0 : "number must be non-negative"; 22 //保证容量是2的整数次幂，并且不超过最大容量 23 return number >= MAXIMUM_CAPACITY 24 ? MAXIMUM_CAPACITY 25 : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; 26 }
上面put()源码中对空值null的处理方法putForNullKey
1 /** 2 * Offloaded version of put for null keys 3 */ 4 private V putForNullKey(V value) { 5 // 如果已经存在，则替换旧值 6 for (Entry<K,V> e = table[0]; e != null; e = e.next) { 7 if (e.key == null) { 8 V oldValue = e.value; 9 e.value = value; 10 e.recordAccess(this); 11 return oldValue; 12 } 13 } 14 // 增加map的修改次数，这用于实现fail-fast机制 15 modCount++; 16 // null key的hashCode固定为0，并且桶的位置也固定为0 17 addEntry(0, null, value, 0); 18 return null; 19 }
上面put()源码中如何确定非null的key的位置,对应indexFor()方法.
/* put()源码中写法如下: 根据hashCode和当前容量来确定元素在hash表中的位置，即hash桶的位置 int i = indexFor(hash, table.length); */ static int indexFor(int h, int length) { return h & (length-1); }
h是key的hashCode，length是当前hash表的最大长度，h & (length-1)与h % length等价，只是前者使用位运算，而位运算比取模运算速度更快。这里为什么可以用&运算代替取模运算呢？
因为length是2的整数次幂，而它减1，低位正好全是1，与另一个数进行&运算，结果肯定不会超过length，与%运算的效果一样。如果length不是2的整数次幂，那么是不能这样做的，所以这里运用的非常巧妙。
举例:length=8; 8的2进制是1000,7的2进制是111 任何一个数和7相与& 取值范围都是0~7 任何一个数和8取余范围也都是0~7
上面put()源码中最核心的生成hashCode的hash方法:
final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } // 调用key的hashCode()方法得到hashCode h ^= k.hashCode(); // 对hashCode进行一系列的位移与异或运算并把结果作为hashCode返回 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
这里为什么要进行这一系列的位移与异或运算呢？主要是经过它这里的运算之后，能够使这个hashCode中的bit 0和1均匀分布，从而减少hash冲突，从而提高整个HashMap的效率。
上面put()源码中向Table数组中添加元素对应的addEntry()和createEntry()方法:
1 void addEntry(int hash, K key, V value, int bucketIndex) { 2 // 判断是否需要扩容，当前容量达到阙值，并且产生了hash冲突（指定hash桶已经有元素存在） 3 if ((size >= threshold) && (null != table[bucketIndex])) { 4 // 容量扩展为之前的2倍 5 resize(2 * table.length); 6 hash = (null != key) ? hash(key) : 0; 7 // 重新计算存储的hash桶位置 8 bucketIndex = indexFor(hash, table.length); 9 } 10 // 创建Entry并存储到hash表中 11 createEntry(hash, key, value, bucketIndex); 12 } 13 14 void createEntry(int hash, K key, V value, int bucketIndex) { 15 // 取出之前已经存在的元素 16 Entry<K,V> e = table[bucketIndex]; 17 // 把新元素放到链表的开头，即让新元素的next引用指向之前已经存在的元素 18 table[bucketIndex] = new Entry<>(hash, key, value, e); 19 // 修改元素计数 20 size++; 21 }
这个里面还有resize()方法,即HashMap的扩容方法,下面会单独提到.
以上put的过程大致可以总结为以下4步:
1.对key做null检查。如果key是null，会被存储到table[0]，因为null的hash值总是0。
2.key的hashcode()方法会被调用，然后计算hash值。
3.indexFor(hash,table.length)用来计算在table数组中存储Entry对象的精确的索引。
4.如果两个key有相同的hash值(也叫冲突)，它们会以迭代链表的形式来存储。
如果在刚才计算出来的索引位置没有元素，直接把Entry对象放在那个索引上。
如果索引上有元素，然后会进行迭代，一直到Entry->next是null。当前的Entry对象变成链表的下一个节点。
如果我们再次放入同样的key会怎样呢？会调用equals()方法来检查key的相等性(key.equals(k))，如果这个方法返回true，它就会用当前Entry的value来替换之前的value。
(2)HashMap的扩容resize();
从put的源代码中可以看到，扩容需要满足以下两个条件：
- 达到加载因子指定的阙值
- put当前值时发生hash冲突（即当前桶的位置已经存在有元素了）
只是当前容器中key value数量超过阙值是不会进行扩容的。就是说，比如初始容量为16，当达到阙值以前发生大量的hash冲突，而后添加的元素又很少发生hash冲突，那么有可能key value的数量超过16*0.75=12甚至超过16都不进行扩容，所以hash算法必须保证分布均匀，尽量减少hash冲突。
扩容时候的rehash:
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 重新创建底层数组 Entry[] newTable = new Entry[newCapacity]; // 对已经存在的元素进行重新hash放到新的hash桶中 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; // 更新扩容阙值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { 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; e = next; } } }
由于hash表长度变化了，所以对于已经存在的元素，需要重新计算hashCode并放到新的hash桶中。这是一个比较耗时的操作，所以在创建HashMap时，如果对数据量有个预期值，那么，应该设置更合适的初始容量，以避免添加数据的过程中不断的扩容造成的性能损失。
(3)get()方法实现
1 public V get(Object key) { 2 // null key进行特殊操作 3 if (key == null) 4 return getForNullKey(); 5 // 获取key对应的Entry 6 Entry<K,V> entry = getEntry(key); 7 // 如果存在则返回key对应的值，不存在则返回null 8 return null == entry ? null : entry.getValue(); 9 } 10 11 final Entry<K,V> getEntry(Object key) { 12 // size为0表示没有元素，所以直接返回null 13 if (size == 0) { 14 return null; 15 } 16 // 获取key的hashCode 17 int hash = (key == null) ? 0 : hash(key); 18 // 获取key对应的hash桶中的元素，并对链表进行迭代返回相应的value 19 for (Entry<K,V> e = table[indexFor(hash, table.length)]; 20 e != null; 21 e = e.next) { 22 Object k; 23 // 根据hashCode和equalse（）方法来确定key 24 if (e.hash == hash && 25 ((k = e.key) == key || (key != null && key.equals(k)))) 26 return e; 27 } 28 // 如果不存在，返回null 29 return null; 30 }
对于加载因子，默认为0.75，这是一个折衷的值， 我们可以通过构造方法来改变这个值，但是需要注意，加载因子越大，查询数据的开销可能越大。因为加载因子越大，意味着map中存放的元素越多，所以hash冲突的可能性越大，根据hashCode计算出的hash桶的位置相同，则保存为链表，而链表的查询操作会遍历整个链表，所以查询效率不高。而在get和put时都要查询元素，所以提高查询效率就提高了hashmap的效率。这是一种用空间换取时间的策略。
为什么HashMap很高效呢？HashMap通过以下几点保证了它的效率：
- 高效的hash算法，使其不易产生hash冲突
- 基于数组存储，实现了元素和链表的优点可以快速存取
- 可通过加载因子，使用空间换取时间
本文转自SummerChill博客园博客，原文链接：http://www.cnblogs.com/DreamDrive/p/7505448.html，如需转载请自行联系原作者
