数组虽然可以随机访问，但插入和删除效率较低，链表虽然插入和删除效率较高，查找却只能通过遍历，而HashMap则基于数组加链表,完美结合了二者的优点，查找，更新，插入，删除几乎都可以达到O(1)时间复杂度。
但要注意的是，HashMap并没有任何同步策略，因此HashMap并不是一个线程安全的容器。如果在多线程环境下，请用Collections.synchronizedMap方法包装或直接用ConcurrentHashMap代替。
本文中HashMap源码基于JDK1.8。
类继承关系
HashMap.png
相比LinkedList,ArrayList的继承体系，HashMap的继承体系更为简单清晰，HashMap继承AbstractMap同时实现了Map这一顶级接口。
源码学习
1.HashMap比较重要的参数
默认初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默认加载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
链表转为红黑树的节点数量阀值
static final int TREEIFY_THRESHOLD = 8;
存放元素的数组元素
transient Node<K,V>[] table;
HashMap扩容的阀值
int threshold;
2.HashMap如何put一个元素
HashMap在JDK1.8中引入了红黑树，当数组节点上挂载的链表节点数量大于8的时候，链表会转为红黑树，引入红黑树的是为了链表太长时，挂载节点和查询时间复杂度可以从O(n)优化到为O(logn)。红黑树的细节不做研究。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算索引，如果该位置为空，则直接在该位置插入元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 该位置已有节点，判断Key是否重复
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 遍历过程中，发现Key已经存在，则退出遍历，进行value覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果key存在 则直接覆盖value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
代码乍一看逻辑比较复杂，借用他人博客中的一张图片，可以很好的说明这段代码的执行逻辑。
putVal.png
HashMap中重要的概念，方法都在这张图中了。HashMap的底层结构是数组加链表,因此要往HashMap中put元素,首先要确定这个元素放在数组的哪个位置，因此必须将key对象映射成一个整数索引。HashMap中是通过计算Key的hash值并对数组长度进行求模运算来完成对象到整数数组索引的映射的。
// n 为数组的长度
tab[i = (n - 1) & hash]
当n为2的n次幂时，hash % n等价于(n-1) & hash,证明在这里。而之所以不直接用hash%n是因为位运算的效率高于求模运算。这里也蕴含了为什么hashMap的容量必须是2的n次幂的原因。& 表示按位做交运算，1和1得1,有0得0。而2的幂次-1有个特点就是低位全为1，可以尽量减少hash碰撞。以容量分别为16和11做一下对比，16-1二进制表示为 00000000 00000000 00000000 00001111，因为有0得0，所以运算只看后四位。
| 容量16(16-1= 1111) | 容量11(11-1 = 1010) |
|---|---|
| 1111 & 1000 = 8 | 1010 & 1000 = 8 |
| 1111 & 1001 = 9 | 1010 & 1001 = 8 |
| 1111 & 1010 = 10 | 1010 & 1010 = 10 |
| 1111 & 1011 = 11 | 1010 & 1011 = 10 |
| 1111 & 1100 = 12 | 1010 & 1100 = 8 |
相比容量取11.容量取16的时候hash碰撞更少。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
而hash函数中没有直接返回key的hashCode而是将其右移16位并与自身做异或运算，使得hashCode的高位也参与运算，也是为了减少哈希冲突的次数。不过这里的原理，我就不是很明白了。
hashMap解决冲突的办法
尽管hashMap在减少hash碰撞上做了很多努力，但是这并不能避免hash冲突。因为散列值（即计算出的数组索引）总是有限的，而输入空间Key却几乎是无限的，HashMap通过链地址法解决冲突，当发现计算出的索引位置已经有元素之后,则将新加入的节点链接到该节点尾部，形成一个链表，而当链表节点数量大于8时，又会将链表转为更高效的红黑树。
3. hashMap中扩容机制
在HashMap中的putVal方法中，有两处调用了扩容函数resize()。第一次是初始化HashMap时，判断作为容器的Node数组为空的时候，第二次是将新节点加入之后，判断如果size大于threshold,则进行扩容。resize源码较长，只贴出对要研究的问题有用的前半部分代码。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 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
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// ... 后半部分代码就是具体的内容拷贝的代码了
}
resize首先会判断table是否为空，如果为空，说明是第一次put,则会扩容到默认大小即16。而如果table不为空，说明并不是第一次扩容，则将容量扩至原来的2倍，同时将进行下一次扩容的阀值threshold也变为原来的2倍。扩容上限是MAXIMUM_CAPACITY即2的31次方。
扩容阀值threshold=table的length×loadFactor。至于为什么loadFactor是0.75，HashMap源码中的文档给出的解释是这个值是对空间和效率上的一个较好折中，最大程度上减少resize的次数。
4.要作为HashMap中的Key需要满足什么条件
- 重写hashCode方法
- 重写equals方法
- 且需要满足equals相等 hashCode必须相等这一语义
HashMap中putVal方法中有俩个地方都需要判断Key是否已经存在，而Key相等的标准是hash值相等且equals返回true，除此之外，还有containsKey、get等方法都依赖Key对象的HashCode和equals方法，所以我们自定义对象如果不重写equals方法和hashCode方法,则无法正常使用HashMap提供的存储功能。如下面代码User代码没有重写equals方法和hashCode方法，因此打印为null。
HashMap<User,String> map = new HashMap();
User u1 = new User("andy",21);
User u2 = new User("andy",21);
map.put(u1,"andy");
System.out.print(map.get(u2));
而String,Integer等可以直接用来做Key,是以为String等对象已经覆盖了HashCode方法和equals方法。同时HashMap的Key是可以为null的，在计算hash值时，hashMap默认将null值的hash值处理为0。
总结
- HashMap底层结构是数组加链表，也就是说HashMap解决Hash冲突的方法是链地址法。
- JDK1.8中冲突节点是插入链表尾部而不是头部
- HashMap默认初始容量是16，加载因子是0.75
- HashMap扩容阀值等于容量×加载因子，因此第二次扩容是达到16*0.75=12时后进行扩容
- HashMap扩容机制为2倍扩容。即16->32->64
- HashMap链表节点数量大于8时，会将链表转为红黑树
- HashMap容量必须是2的n次幂次
- 最好给予HashMap一个初始容量，尽量避免HashMap扩容 初始容量计算公式：n/0.75f+1f
- HashMap的key必须实现hashCode方法和equals方法，且可以为null
做道题
假设确定需要存放100个键值对，应该初始化容量为多少？因为容量都必须是2的n次幂，而26<100<27次，所以应该初始话为128？
但是128*0.75 = 98，所以当放入第98个元素的时候，会进行扩容。正确的算法应该是100/0.75约等于133.33,取134。而HashMap中构造函数会调用tableSIzeFor方法找到大于该值的最小的2的n次幂。
网友评论