Hashmap

对key进行hash，放到数组对应的位置 p = tab[i = (n - 1) & hash] 。i的位置为i = (n - 1) & hash

从JDK8以后结构为：数组 + 链表 + 红黑树，从原来的hash冲突时由纯链表变为，当链表长度大于8以后变为红黑树。

fail-fast机制是什么东西，这个在开发的时候是一个比较常见的异常，ConcurrentModificationException

核心变量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//应该是数组的默认的初始大小，是16，这个跟ArrayList是不一样的，初始的默认大小是10
//这个数组的大小，一般会自己手动指定一下，就跟你用ArrayList一样，你需要去预估一下你的这个数据结构里会放多少key-value对，指定的大一些，避免频繁的扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认的负载因子，如果你在数组里的元素的个数达到了数组大小（16） * 负载因子（0.75f），默认是达到12个元素，就会进行数组的扩容
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}
//这是一个很关键的内部类，他其实是代表了一个key-value对，里面包含了key的hash值，key，value，还有就是可以有一个next的指针，指向下一个Node，也就是指向单向链表中的下一个节点
//通过这个next指针，就可以形成一个链表
transient Node<K,V>[] table;
//这个是什么东东？Node<K, V>[]，这个数组就是所谓的map里的核心数据结构的数组，数组的元素就可以看到是Node类型的，天然就可以挂成一个链表，单向链表，Node里面只有一个next指针
transient int size;
//这个size代表的是就是当前hashmap中有多少个key-value对，如果这个数量达到了指定大小 * 负载因子，那么就会进行数组的扩容
int threshold;
//这个值，其实就是说capacity（就是默认的数组的大小），就是说capacity * loadFactory，就是threshold，如果size达到了threshold，那么就会进行数组的扩容，如果面试这么回答，你就是在打自己的脸。扩容的时机是size>threshold

//负载因子，默认值，threshold，扩容，扩容，rehash的算法，JDK 1.7以前的rehash是怎么做的，性能有多差，JDK 1.8以后是如何优化的rehash的算法，东西很多的

final float loadFactor;
//默认就是负载因子，默认的值是0.75f，你也可以自己指定，如果你指定的越大，一般就越是拖慢扩容的速度，一般不要修改

1.8优化

降低冲突概率的算法

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

h »> 16，对h进行无符号右移，即将高位16hash值移到低位。

然后使用^进行异或操作。将高低位异或，计算出来的值减少hash冲突

寻址算法优化

(length - 1) & hash等价于hash%n（当length为2的倍数时，jdk强制length为2的倍数）。但按位与&比取模算法效率高。

哈希冲突时，链表处理方式

使用拉链法，在冲突的地方链接一个双向链表。若还有冲突，则继续在链表中插入。

**jdk7使用头插法，jdk8使用尾插法。**优化原因，头插法resize的时候会有并发问题，尾插法则不会。虽然并发访问不适合用此类，但jdk8源码开发者还是改了此处。原因是防止指令重排后，resize和插入元素会有重复XX问题？ 待确认

链表大于8时，将链表转换为红黑树

优化原因，大量哈希冲突，会导致get操作性能急剧下降。链表查询为O(n)，转换为红黑树后查询时间变为O(logn)

扩容原理

2倍扩容，并且rehash。有hash冲突的元素，rehash后的位置变为index+oldCap或位置不变。2倍扩容的方式同样避免了低效的取模运算，使用按位与提高效率

源码：newTab[e.hash & (newCap - 1)] = e;

LinkedHashMap

插入的时候调用了linkNodeLast方法，插入到了双链表尾部。维护了插入的顺序，遍历的时候会以插入顺序进行输出

TreeMap

底层将hashmap的数组改为使用红黑树来存放数据，默认使用key的自然顺序来排序，当然也可以指定自定义的排序规则。使用key的排序规则来进行迭代输出

迭代器的fail fast机制

ConcurrentModificationException，并发修改的异常，这个机制就叫做fail fast.

使用modCount来记录对数据的修改操作，当在迭代的时候修改此迭代器。则会抛出此异常。

因为集合包中的类，都是非线程安全的。所以设计了针对并发修改集合的问题，都有fail fast机制，使用modCount来实现。一旦expectedModCount!=modCount，抛出异常。