LinkedHashMap 继承 HashMap，底层数据结构是：双向链表（HashMap 中元素底层数据结构是数组 + 链表 + 红黑树）
1. 特性
2. 重点属性
// 链表头
transient LinkedHashMap.Entry<K,V> head;
// 链表尾
transient LinkedHashMap.Entry<K,V> tail;
// 继承 Node，为数组的每个元素增加了 before 和 after 属性
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
// 控制两种访问模式的字段，默认 false
// true 按照访问顺序，会把经常访问的 key 放到队尾
// false 按照插入顺序提供访问
final boolean accessOrder;
LinkedHashMap 初始化时，默认 accessOrder 为 false，就是会按照插入顺序提供访问，插入方法使用的是父类 HashMap 的 put 方法，不过覆写了 put 方法执行中调用的 newNode/newTreeNode 和 afterNodeAccess 方法。
newNode/newTreeNode 方法，控制新增节点追加到链表的尾部，这样每次新节点都追加到尾部，即可保证插入顺序了，以 newNode 源码为例：
// 新增节点，并追加到链表的尾部
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// 新增节点
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 追加到链表的尾部
linkNodeLast(p);
return p;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
// 新增节点等于位节点
tail = p;
// last 为空，说明链表为空，首尾节点相等
if (last == null)
head = p;
// 链表有数据，直接建立新增节点和上个尾节点之间的前后关系即可
else {
p.before = last;
last.after = p;
}
}
LinkedHashMap 通过新增头节点、尾节点，给每个节点增加 before、after 属性，每次新增时，都把节点追加到尾节点等手段，在新增的时候，就已经维护了按照插入顺序的链表结构了。
LinkedHashMap 只能按从头到尾的顺序单向访问。
不能像 LinkedList 那样可以双向访问。
1. 访问方式
通过迭代器进行访问，迭代器初始化的时候，默认从头节点开始访问，在迭代的过程中，不断访问当前节点的 after 节点即可。
2. 源码解析
Map 对 key、value 和 entry（节点） 都提供出了迭代的方法，假设我们需要迭代 entry，就可使用 LinkedHashMap.entrySet().iterator() 这种写法直接返回 LinkedHashIterator ，LinkedHashIterator 是迭代器，我们调用迭代器的 nextNode 方法就可以得到下一个节点，迭代器的源码如下：
// 初始化时，默认从头节点开始访问
LinkedHashIterator() {
// 头节点作为第一个访问的节点
next = head;
expectedModCount = modCount;
current = null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)// 校验
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after; // 通过链表的 after 结构，找到下一个迭代的节点
return e;
}
LRU（Least recently used，最近最少使用）策略，是指经常访问的元素会被追加到队尾，很少访问的元素则靠近队首，通过设置删除策略，比如当 Map 元素个数大于多少时，把头节点删除。
1. 元素被转移到队尾
public V get(Object key) {
Node<K,V> e;
// 调用 HashMap get 方法
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果设置了 LRU 策略
if (accessOrder)
// 这个方法把当前 key 移动到队尾
afterNodeAccess(e);
return e.value;
}
不仅是 get 方法，执行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法时，也会通过 afterNodeAccess 方法，把当前访问节点移动到了队尾，通过不断的把经常访问的节点移动到队尾，那么靠近队头的节点，自然就是很少被访问的元素了。
2. 删除策略
LinkedHashMap 实现了 put 方法中的调用 afterNodeInsertion 方法，这个方式实现了删除策略，源码如下：
// 删除很少被访问的元素，被 HashMap 的 put 方法所调用
void afterNodeInsertion(boolean evict) {
// 得到元素头节点
LinkedHashMap.Entry<K,V> first;
// removeEldestEntry 来控制删除策略，如果队列不为空，并且删除策略允许删除的情况下，删除头节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// removeNode 删除头节点
removeNode(hash(key), key, null, false, true);
}
}
1. 说一说 HashMap 底层数据结构
答：HashMap 底层是数组 + 链表 + 红黑树的数据结构，数组的主要作用是方便快速查找，时间复杂度是 O(1)，默认大小是 16，数组的下标索引是通过 key 的 hashcode 计算出来的，数组元素叫做 Node，当多个 key 的 hashcode 一致，但 key 值不同时，单个 Node 就会转化成链表，链表的查询复杂度是 O(n)，当链表的长度大于等于 8 并且数组的大小超过 64 时，链表就会转化成红黑树，红黑树的查询复杂度是 O(log(n))，简单来说，最坏的查询次数相当于红黑树的最大深度。
2. HashMap、TreeMap、LinkedHashMap 三者有啥相同点，有啥不同点？
答：相同点：
不同点：
3. 说一下 Map 的 hash 算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key 在数组中的位置公式：
tab[(n - 1) & hash]
这其实是一个数学问题，源码中就是通过以上代码来计算 hash 的，首先计算出 key 的 hashcode，因为 key 是 Object，所以会根据 key 的不同类型进行 hashcode 的计算，接着计算 h ^ (h >>> 16) ，这么做的好处是使大多数场景下，算出来的 hash 值比较分散。
一般来说，hash 值算出来之后，要计算当前 key 在数组中的索引下标位置时，可以采用取模的方式，就是索引下标位置 = hash 值 % 数组大小，这样做的好处，就是可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上，但取模操作对于处理器的计算是比较慢的，数学上有个公式，当 b 是 2 的幂次方时，a % b = a &（b-1），所以此处索引位置的计算公式我们可以更换为： (n-1) & hash。
此问题可以延伸出四个小问题：
1）为什么不用 key % 数组大小，而是需要用 key 的 hash 值 % 数组大小。
答：如果 key 是数字，直接用 key % 数组大小是完全没有问题的，但我们的 key 还有可能是字符串，是复杂对象，这时候用 字符串或复杂对象 % 数组大小是不行的，所以需要先计算出 key 的 hash 值。
2）计算 hash 值时，为什么需要右移 16 位？
答：hash 算法是 h ^ (h >>> 16)，为了使计算出的 hash 值更分散，所以选择先将 h 无符号右移 16 位，然后再与 h 异或时，就能达到 h 的高 16 位和低 16 位都能参与计算，减少了碰撞的可能性。
3）为什么把取模操作换成了 & 操作？
答：key.hashCode() 算出来的 hash 值还不是数组的索引下标，为了随机的计算出索引的下表位置，我们还会用 hash 值和数组大小进行取模，这样子计算出来的索引下标比较均匀分布。
取模操作处理器计算比较慢，处理器对 & 操作就比较擅长，换成了 & 操作，是有数学上证明的支撑，为了提高了处理器处理的速度。
4）为什么提倡数组大小是 2 的幂次方？
答：因为只有大小是 2 的幂次方时，才能使 hash 值 % n(数组大小) == (n-1) & hash 公式成立。
4.解决 hash 冲突的办法有哪些？
答：1：好的 hash 算法，细问的话复述一下上题的 hash 算法;
2：自动扩容，当数组大小快满的时候，采取自动扩容，可以减少 hash 冲突;
3：hash 冲突发生时，采用链表来解决;
4：hash 冲突严重时，链表会自动转化成红黑树，提高遍历速度。
1. HashMap 是如何扩容的？
答：扩容的时机：
扩容的负载因子是 threshold，每次扩容时 threshold 都会被重新计算，阈值等于数组的大小 * 影响因子（0.75）。
新数组初始化之后，需要将旧数组的值拷贝到新数组上，链表和红黑树都有自己拷贝的方法。
2. 怎么解决 hash 冲突？
答：hash 冲突指的是 key 值的 hashcode 计算相同，但 key 值不同的情况。
如果桶中元素原本只有一个或已经是链表了，新增元素直接追加到链表尾部；
如果桶中元素已经是链表，并且链表个数大于等于 8 时，此时有两种情况：
这里不仅仅判断链表个数大于等于 8，还判断了数组大小，数组容量小于 64 没有立即转化的原因，猜测主要是因为红黑树占用的空间比链表大很多，转化也比较耗时，所以数组容量小的情况下冲突严重，我们可以先尝试扩容，看看能否通过扩容来解决冲突的问题。
3. 为什么链表个数大于等于 8 时，链表要转化成红黑树了？
答：当链表个数太多了，遍历可能比较耗时，转化成红黑树，可以使遍历的时间复杂度降低，但转化成红黑树，有空间和转化耗时的成本，我们通过泊松分布公式计算，正常情况下，链表个数出现 8 的概率不到千万分之一，所以说正常情况下，链表都不会转化成红黑树，这样设计的目的，是为了防止非正常情况下，比如 hash 算法出了问题时，导致链表个数轻易大于等于 8 时，仍然能够快速遍历。
延伸问题：红黑树什么时候转变成链表。
答：当节点的个数小于等于 6 时，红黑树会自动转化成链表，主要还是考虑红黑树的空间成本问题，当节点个数小于等于 6 时，遍历链表也很快，所以红黑树会重新变成链表。
4. HashMap 在 put 时，如果数组中已经有了这个 key，我不想把 value 覆盖怎么办？取值时，如果得到的 value 是空时，想返回默认值怎么办？
答：如果数组有了 key，但不想覆盖 value ，可以选择 putIfAbsent 方法，这个方法有个内置变量 onlyIfAbsent，内置是 true ，就不会覆盖，我们平时使用的 put 方法，内置 onlyIfAbsent 为 false，是允许覆盖的。
取值时，如果为空，想返回默认值，可以使用 getOrDefault 方法，方法第一参数为 key，第二个参数为你想返回的默认值，如 map.getOrDefault(“2”,“0”)，当 map 中没有 key 为 2 的值时，会默认返回 0，而不是空。
5. 通过以下代码进行删除，是否可行？
HashMap<String,String > map = Maps.newHashMap();
map.put("1","1");
map.put("2","2");
map.forEach((s, s2) -> map.remove("1"));
答：不行，会报错误 ConcurrentModificationException。
1. DTO 作为 Map 的 key 时，有无需要注意的点？
答：DTO 就是一个数据载体，可以看做拥有很多属性的 Java 类，我们可以对这些属性进行 get、set 操作。
2. LinkedHashMap 中的 LRU 是什么意思，是如何实现的？
答：LRU ，英文全称：Least recently used，中文叫做最近最少访问，在 LinkedHashMap 中，也叫做最少访问删除策略，我们可以通过 removeEldestEntry 方法设定一定的策略，使最少被访问的元素，在适当的时机被删除，原理是在 put 方法执行的最后，LinkedHashMap 会去检查这种策略，如果满足策略，就删除头节点。
保证头节点就是最少访问的元素的原理是：LinkedHashMap 在 get 的时候，都会把当前访问的节点，移动到链表的尾部，慢慢的，就会使头部的节点都是最少被访问的元素。
3. 为什么推荐 TreeMap 的元素最好都实现 Comparable 接口？但 key 是 String 的时候，我们却没有额外的工作呢？
答：因为 TreeMap 的底层就是通过排序来比较两个 key 的大小的，所以推荐 key 实现 Comparable 接口，是为了往你希望的排序顺序上发展， 而 String 本身已经实现了 Comparable 接口，所以使用 String 时，我们不需要额外的工作，不仅仅是 String ，其他包装类型也都实现了 Comparable 接口，如 Long、Double、Short 等等。
