HashMap实现原理

基本构造

内部包含了一个 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同理