标签： Java编程思想
HashMap在Map家族中的地位相当于ArrayList在List家族中的地位，是当之无愧的老大哥
public class HashMap
顾名思义，HashMap是一个基于哈希表实现Map接口的集合。我们已经知道，hash的优势就是在查找时速度很快，因此：
HashMap 其特殊存储结构使得在获取指定元素前需要经过哈希运算，得到目标元素在哈希表中的位置，然后再进行少量比较即可得到元素，这使得 HashMap 的查找效率贼高。
虽然HashMap具有很快的访问速度，但遍历顺序却是不确定的。
HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
总结HashMap具有一下特点：
首先简单讲解下HashMap的原理：
HashMap基于Hash算法，我们通过put(key,value)来存储键值对，通过get(key)来获取。当传入key时，HashMap会根据key.hashCode()计算出hash值，根据hash值将value保存在“桶”里。当计算出的hash值相同时怎么办呢，我们称之为Hash冲突，HashMap的做法是用链表和红黑树存储相同hash值的value。当Hash冲突的个数比较少时，使用链表，否则使用红黑树。
从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下如所示。
搞清楚HashMap，首先需要知道HashMap的内部存储结构；其次弄明白它能干什么，即它的功能实现方法。下面我们针对这两个方面详细展开讲解。
下面给出一些比较重要的成员变量：
static final int DEFAULT_INITIAL_CAPACITY = 1 <<4; static final float DEFAULT_LOAD_FACTOR = 0.75f;int threshold;transient int modCount;transient Set<Map.Entry<K,V>> entrySet;transient Node[] table; transient int size;final float loadFactor;我们可以在HashMap的源码中找到这样一句：
transient Node[] table; 很明显，HashMap还是凭借数组实现的，辅以链表和红黑树。我们知道数组的特点：寻址容易，插入和删除困难，而链表的特点是：寻址困难，插入和删除容易，红黑树则对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。HashpMap将这三者结合在一起。
由于 HashMap 扩容开销很大（需要创建新数组、重新哈希、分配等等），因此与扩容相关的两个因素：容量、加载因子成为了 HashMap 最重要的部分之一，它们决定了 HashMap 什么时候扩容：
HashMap 的默认加载因子为 0.75，这是在时间、空间两方面均衡考虑下的结果：
因此在设置初始容量时，需要提前考虑Map中可能有多少对键值对，设计合理的加载因子，尽可能避免进行扩容。
如果存储的键值对很多，干脆设置个大点的容量，这样可以少扩容几次。
HashMap提供了三个构造函数：
HashMap()： 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。HashMap(int initialCapacity)： 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。HashMap(int initialCapacity, float loadFactor)： 构造一个带指定初始容量和加载因子的空 HashMap。HashMap(Map m)： 创建一个内容指定Map的一个HashMap。Node前面提到，HashMap 的底层数据结构之一就是链表数组：transient Node，即哈希桶数组（桶这个概念，应该是指同一数组元素所对应的链表装载一个桶里）
明显它是一个Node的数组。我们来看Node[JDK1.8]是何物:
//Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)
static class Node implements Map.Entry {
final int hash; //哈希值，用来定位数组索引位置
final K key;
V value;
Node next; //链表，Node类型的下一个node
//构造方法，需要传进hash值，键，值，链表的下一个node
Node(int hash, K key, V value, Node 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; }
//重写hashCode()方法
//对于Node节点的hashCode()，是key的hashCode 对 value的hashCode次方
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//重写equals()方法，以key和value的值相等作为判断依据
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
////Map.Entry 相等的条件：键相等、值相等、个数相等、顺序相等
Map.Entry e = (Map.Entry)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
} 分析：
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。
HashMap就是使用哈希表来存储的。Java中HashMap采用了链地址法来解决冲突，简单来说，就是在每个数组元素上都有一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。
例如程序执行下面代码：
map.put("实验室","Japson");系统将调用”实验室”这个key的hashCode()方法得到其hashCode值（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算，下文有介绍）来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。
这里面涉及两个概念：哈希桶和哈希桶数组：
如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。
HashMap的内部功能实现很多，本文主要从根据key获取哈希桶数组索引位置、添加方法的详细执行、扩容过程、获取等几个具有代表性的点深入展开讲解。
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):
方法一：
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 将 hashCode 进行无符号右移 16 位，然后进行按位异或
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1); //第三步 取模运算
}这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
对于任意给定的对象，只要它的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的计算中，同时不会有太大的开销。
public V put(K key,V value)
添加指定的键值对到Map中，如果已经存在，就替换。
HashMap的put方法执行过程可以通过下图来理解：
步骤详解：
判断键值对数组table[i]是否为空或为null，若为空或null，则执行resize()进行扩容；
根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3；
判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；
判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；
遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
HashMap的put方法源码如下:
public V put(K key, V value) {
// 对key的hashCode()做hash，计算key的位置
return putVal(hash(key), key, value, false, true);
}/**
* @param onlyIfAbsent 若是true，不更改现有值；若为false，则更改现有值。
* @param evict 若是true，则该表不是创建模式；若是false，则该表处于创建模式。
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
//步骤1：当前哈希表tab为空则创建，n指向最后一个桶的位置
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//步骤2：计算哈希桶数组索引位置p：
//如果p位置为null，新建个节点并放进去
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果p位置已经有元素，则替换，过程如下：
else {
Node e; // e 指向被替换的元素
K k;
// 步骤3：节点key存在（p的hash值和key都和要添加的一样）直接覆盖，令 e 指向 p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤4：如果判断该链为红黑树，调用 putTreeVal 插入
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
//步骤5：若该链为链表，从链表数组查找、替换
else {
//遍历链表
for (int binCount = 0; ; ++binCount) {
//若是链表中最后一个节点，则将新Node节点插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果添加之后链表长度大于8，则转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//如果链表中有此节点，则覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//存在要替换的节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //这是一个空的方法
return oldValue;
}
}
// 步骤6：超过最大容量 就扩容
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict); //这是一个空的方法
return null;
} 插入过程中涉及到几个其他关键的方法 ：
hash():计算对应的位置 resize():扩容 putTreeVal():树形节点的插入 treeifyBin():树形化容器
我们在putVal方法中看到，不少地方都调用了afterNodeAccess(e)和afterNodeInsertion(evict)方法，但是我们点进去之后发现，是一个空的方法。
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node p) { } 这个三个方法都是为了继承HashMap的LinkedHashMap类服务的,将会在LinkedHashMap中被使用。
在理解了put之后，get就很简单了。大致思路如下：
具体代码的实现如下：
public V get(Object key) {
Node e;
//返回key所对应的值
return (e = getNode(hash(key), key)) == null ? null : e.value;
} getNode(int hash, Object key)需要传入key的hash值和key。
final Node getNode(int hash, Object key) {
Node[] tab;
Node first, e;
int n;
K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中，即表头的hash值和key都与参数给出的相同，返回表头
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 否则
if ((e = first.next) != null) {
// 若是在红黑树中，则调用 getTreeNode(hash, key)方法
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
// 若是在链表中，通过对链表do-while循环对比来get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
} 当put时，如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例，也就是当前的size >= threshold，那么就会发生resize。在resize的过程，简单的说就是把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中。resize的注释是这样描述的：
nitializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
大致意思就是说，当超过限制的时候会resize，然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：
因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：
这个设计非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
下面是代码的具体实现：
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; //旧表的长度
int oldThr = threshold; //旧表的阈值
int newCap, newThr = 0;
if (oldCap > 0) { //当旧表的长度 > 0
// 若超过最大值就不再扩充了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap <<1) oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr <<1; // 二倍的阈值
}
//如果旧表长度为0，且旧阈值>0，说明之前创建了哈希表但没有添加元素，新的表长为原来的阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//旧表长度、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值为 容量*加载因子
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 在处理完newCap和newThr后，计算新的resize上限：
//如果新的阈值为 0 ，就得用 新容量*加载因子 重计算一次
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新阈值
threshold = newThr;
//创建新链表数组，容量是原来的两倍
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
//若旧表不空，则遍历旧表，复制到新表
if (oldTab != null) {
for (int j = 0; j Node e;
if ((e = oldTab[j]) != null) {
//将旧的桶赋给新的 e ，旧的桶置为空（方便回收）
oldTab[j] = null;
//当前的桶只有一个元素（即只有链表的头结点），直接赋值给对应位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果旧哈希表中这个位置的桶是红黑树，则调用split方法将新表的当前桶也变为红黑树
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
//如果旧哈希表中这个位置的桶是链表，则保留旧哈希表桶中链表的顺序
else {
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
//do-while 循环赋值给新哈希表
do {
next = e.next;
// 如果hash值新增的bit是0，则是原索引不变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 如果hash值新增的bit是1，则新索引为原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
}
while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} 总结扩容的思路：
我们通过一些问题，加深对HashMap的理解：
答： 是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。
答： 通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
答： 通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
答： 在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。
答： 如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。
答： capacity 为2的整数次幂的话，计算桶的位置 h&(length-1) 就相当于对 length 取模，提升了计算效率；并且 capacity 为2的整数次幂的话，为偶数，这样 capacity-1 为奇数，奇数的最后一位是 1，这样便保证了 h&(capacity-1) 的最后一位可能为 0，也可能为（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性；
答： HashMap是非同步的，多线程操作会有问题，并可以接受为null的ke和value，而Hashtable是同步的，且不接受null。另一个区别是HashMap的迭代器是fail-fast迭代器，而Hashtable的迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构，将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。
答： HashMap可以通过下面的语句进行同步：
Map m = Collections.synchronizeMap(hashMap);
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有