HashMap集合

1. HashMap容量为什么是2的幂次？

如果我们创建HashMap没有指定容量（默认就是16）
如果指定了初始容量n，则容量是大于等于n的最小2次幂。

这个是我们给定初始容量，最终会调用tableSizeFor(n)这个方法进行判断初始容量。使用无符号右移，或运算。（就是找出大于等于n的最小2次幂）

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
1
2
3
4
5
6
7
8
9

HashMap长度为2的幂次方的原因是为了减少Hash碰撞，尽量使Hash算法的结果均匀。

首先看一下HashMap中putVal方法的源码

其中有个( n - 1) & hash的方法，那么这个方法是干什么的呢？
HashMap为了存取高效，就要尽量减少碰撞，将数据分配均匀，那么如何分配均匀，此时主要靠将数据存入到那个链表中的算法，这个算法就是( n - 1) & hash。& 是按位与运算，是一个位运算，而在计算机中位运算的效率很高，这就是不用%运算的原因。
按位与&的计算方式为当对应位置的数据都为1时，运算结果也为1。因此当HashMap的容量是2的幂次方时，( n - 1)的2进制都是111…11的形式，在与添加元素的hash值进行位运算时能够充分的散列，使添加的元素能均匀的分布在HashMap的每个位置上，减少hash碰撞。

2. 为什么HashMap使用红黑树而不是AVL树？

1. 红黑树和AVL树都是常见的平衡二叉树，它们的查找，删除，修改的时间复杂度都是 O(log n)
2. AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树红黑树更适合插入修改密集型任务通常，AVL树的旋转比红黑树的旋转更加难以平衡和调试

总结

1. AVL以及红黑树都是高度平衡的树形结构，它们非常的相似，真正的区别在于任何添加、删除操作时完成的旋转操作次数
2. 两种时间复杂度都是O(logN)，其中N是叶子的数量，但实际上AVL树在查找密集型任务上更快，利用更好的平衡，树遍历平均更短，另一方面，插入和删除上，AVL树较慢，因为需要更高的旋转次数才能在修改时正确地重新平衡数据结构
3. 在AVL树中，从根到任何叶子节点的最短路径和最长路径之间的差异最多为1，在红黑树中，差异可以是2倍
4. 两个都是O(logN)查找，但是平衡二叉树可能需要 O(logN)旋转，而红黑树需要最多两次旋转使其达到平衡（尽可能需要检查O(logN)节点以确定旋转的位置），旋转本身是O(1)操作，因为你只需要移动指针。

3. 默认的加载因子0.75，为什么设置 0.75 这个值呢？

简单来说就是时间和空间的权衡。
若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，
若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。

4. 为什么HashMap桶中节点个数超过8才转为红黑树？

简单来说就是时间和空间的权衡。（这里面使用一个数学中的泊松分布定理 ）
数量小于等于8的时候，链表比较适合
数量大于8的时候，红黑树比较适合

5.put方法的详解

//put方法，会先调用一个hash()方法，得到当前key的一个hash值，
//用于确定当前key应该存放在数组的哪个下标位置
//这里的 hash方法，我们姑且先认为是key.hashCode()，其实不是的，一会儿细讲
public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

//把hash值和当前的key，value传入进来
//这里onlyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入false
//evict只有在方法 afterNodeInsertion(boolean evict) { }用到，可以看到它是一个空实现，因此不用关注这个参数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
	Node<K,V>[] tab; Node<K,V> p; int n, i;
	//判断table是否为空，如果空的话，会先调用resize扩容
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	//根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，
	//若没有，则把key、value包装成Node节点，直接添加到此位置。
	// i = (n - 1) & hash 是计算下标位置的，为什么这样算，后边讲
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	else { 
		//如果当前位置已经有元素了，分为三种情况。
		Node<K,V> e; K k;
		//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，
		//则把p赋值给e，跳转到①处，后续需要做值的覆盖处理
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		//2.如果当前是红黑树结构，则把它加入到红黑树 
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		else {
		//3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {
					//如果头结点的下一个节点为空，则插入新节点
					p.next = newNode(hash, key, value, null);
					//如果在插入的过程中，链表长度超过了8，则转化为红黑树
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					//插入成功之后，跳出循环，跳转到①处
					break;
				}
				//若在链表中找到了相同key的话，直接退出循环，跳转到①处
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		//①
		//说明发生了碰撞，e代表的是旧值，因此节点位置不变，但是需要替换为新值
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			//用新值替换旧值，并返回旧值。
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			//看方法名字即可知，这是在node被访问之后需要做的操作。其实此处是一个空实现，
			//只有在 LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，hashmap不提供排序功能
			// Callbacks to allow LinkedHashMap post-actions
			//void afterNodeAccess(Node<K,V> p) { }
			afterNodeAccess(e);
			return oldValue;
		}
	}
	//fail-fast机制
	++modCount;
	//如果当前数组中的元素个数超过阈值，则扩容
	if (++size > threshold)
		resize();
	//同样的空实现
	afterNodeInsertion(evict);
	return null;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

整体流程：

1. 先判断hashmap是否为空，如果为空，进行初始化扩容，容量为16
2. 然后根据hash算法计算出key的hash值，然后找到对应的位置，判断该位置上是否有元素。
3. 如果该位置上为空，则把key、value包装成Node节点，直接添加到此位置。
4. 如果当前位置已经有元素了，分为三种情况。
5. 第一种情况：1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，直接覆盖处理
6. 第二种情况：2.判读是否是红黑树结果，如果当前是红黑树结构，则把它加入到红黑树
7. 第三种情况：3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部。如果在插入的过程中，链表长度超过了8，则转化为红黑树（转成红黑树的条件是数组大于等于64，链表大于等于8），如数组小于64则进行扩容操作。
8. 添加完之后，size++,这个时候判断，如果当前数组中的元素个数超过阈值，则扩容。

6. 什么时候才需要扩容？----resize()

1. 当HashMap中的元素个数超过数组大小（数组长度）*loadFactor(负载因子)时，就会进行数组扩容，loadFactor的默认值(DEFAULT_LOAD_FACTOR)是0.75,这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中的元素个数超过16×0.75=12（这个值就是阈值或者边界值threshold值）的时候，就把数组的大小扩展为2×16=32,即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预知元素的个数能够有效的提高HashMap的性能。
2. 补充：
   当HashMap中的其中一个链表的对象个数如果达到了8个，此时如果数组长度没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链表会变成红黑树，节点类型由Node变成TreeNode类型。当然，如果映射关系被移除后，下次执行resize方法时判断树的节点个数低于6，也会再把树转换为链表。