HashMap 实现Map接口，用来存放键值对，是java常用的集合之一。
jdk1.8之前是由数组+链表 来实现，链表是为了解决hash冲突而存在的（拉链法）。
jdk1.8之后（包括1.8）是使用数组 + 链表或者红黑树 来实现，当链表长度大于8（阈值）时，
将链表转为红黑树。当然将链表转为红黑树的前提是当前数组的长度小于64，否则会先将数组进行扩容，
而不是将链表转为红黑树。将链表转为红黑树可以减少搜索时间，提升查询效率。
HashMap 允许 key 和 value 都为空，当然只能有一个key为null，但可以有多个value为null。
ps：
线程安全的Map， key和value都不允许为null，像ConcurrentHashMap，HashTable 等，
key不能为null的原因不明，
value不能为null的原因主要是因为不能通过containsKey来区分是否存在key 对应的null值。
即不存在这个key，还是key对应的value为null 这两种情况不确定，调用containsKey方法的
时候可能已经发生变化了，即可能由不存在这个key变成这个key对应的value为null。
其中 HashMap 变量 loadFactor（加载因子），loadFactor越大，数组就先不扩容，
而是链表长度变得越来越长，查找效率越低。
loadFactor越小，链表长度就越短，但是数组就会不断进行扩容，导致使用数组变大。
loadFactor设置的大小就是时间和空间的取舍，loadFactor越大，数组占用空间就越小，但是查找时间就会 变长。loadFactor越小，数组不断扩容，占用空间就越大，相应的链表长度就越短，查找时间就会越短。
HashMap 默认数组大小为16，loadFactor为0.75，扩容阈值为16*0.75=12
put方法， 添加元素
执行步骤：
1.首先根据key计算hash值
2.判断数组是否为null或者长度为0，如果是的话进行初始化或者扩容。执行resize 方法。
3.根据hash值找到对应数组位置的链表，如果链表为null，则初始化链表，并将首节点设置为当前元素。否则转到4
4.如果根据hash值找到的链表不为null，则看链表第一个元素的key是否和要插入的key相同。如果相同，则
覆盖旧的value值。否则转到5
- 判断是否为红黑树，如果是，则插入到树中。否则遍历链表找到对应的位置，如果找到相同的key，则覆盖旧值。否则将新元素放到链表尾部。
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;
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;
}
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;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
执行put操作过程中，可能会引发链表转为红黑树 和数组的扩容。
链表转为红黑树的阈值是链表长度大于8（前提是数组大小小于64），
数组扩容时机为链表转为红黑树或者数组新增链表节点时。
数组的扩容则是当前HashMap元素数量大于 阈值（数组容量 * 加载因子），数组扩容时容量增大一倍，
即变为原来的两倍大小。
HashMap容量一定是2的n次方是因为
hash%length==hash&(length-1)的前提是 length 是2的 n 次方
在put或者get操作时的时候，都是根据key的hash值和数组长度来得到链表位置
put操作
if ((p = tab[i = (n - 1) & hash]) == null)
get操作
(first = tab[(n - 1) & hash]) != null) {
get方法，查找元素
根据key获得hash值，如果数组为null或者大小为0，则直接返回null。
如果数组大小大于0，则根据hash值获得数组中对应的链表，先判断首元素key是否就是需要查找的key，
如果是，则直接返回对应的值。否则判断是否为红黑树，如果是，则根据树的查找方式查找对象。如果也不是红黑树，则一定是链表，就遍历链表，找到相同的key。否则返回null。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
网友评论