基本构造
内部包含了一个 Entry 类型的数组 Node，存放四个字段，hashCode, key, value, Entry next。每个位置当做一个桶，存放了一个链表，链表存放hash值相同的Entry。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
HashMap 允许插入键为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法，也就无法确定该键值对的桶下标，只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对。
解决冲突方法
常用的是链地址法：hashmap默认大小为16，通过除留余数法得到桶下标，以头插法方式进行插入到链表中
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
开放地址法：发生冲突时，寻找下一个空的散列地址
再哈希法：用其他哈希函数计算地址
put操作
put操作，如果已经存在键为key的键值对，则进行更新并返回oldValue值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
取模
确定桶下标的最后一步是将 key 的 hash 值对桶个数取模：hash%capacity，如果能保证 capacity 为 2 的 n 次方，那么就可以将这个操作转换为位运算，即h & (length - 1)
扩容
设 HashMap 的 table 长度为 M，需要存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此平均查找次数的复杂度为 O(N/M)
hashmao扩容的时候capacity也是按2的次方来扩容;同时，扩容含有临界值threshold和装载因子loadFactor(默认0.75)，键值对数量size超过threshold则需要进行扩容（rehashing），扩为原来的两倍
扩容时需要将oldTable所有键值对重新经过哈希，放到newTable中，过程比较费时
在线程安全方面，多线程竞争map的扩容时，可能会导致ABA的死循环问题
未扩容前，链表太长如何解决
从 JDK 1.8 开始，一个桶存储的链表长度大于 8 时会将链表转换为红黑树,同时做删除操作后链表长度小于6则将红黑树转换为链表
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
转换过程
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
与HashTable对比
- hashTable用sy同步，保证线程安全
- 不允许null-key,null-value
- ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好
- HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常
关于fail-fast迭代器
Fail-fast和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator，然后其它的线程试图“结构上”更改集合对象，将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的，因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改，再调用set()方法，将会抛出IllegalArgumentException异常。
为什么使用String，Integer这样的wrapper类适合作为键？
因为String是不可变的，也重写了equals和hashcode方法，防止键的改变，Integer同理
网友评论