Map

键值对的结构，将键映射到值。一个映射不能包含重复的键；每个键最多只能映射到一个值。

• HashMap,HashTable,ConCurrentHashMap的区别和实现原理？

• 如何实现线程同步？

a- rraymap和hashmap的区别？

HashMap介绍

HashMap是JDK对于数据结构中哈希表的实现，用于保存键值对这样的一个结构。

//平均来看，哈希表的增删查改都是O(1)的时间复杂度。

• 有2个影响性能的参数：初始容量默认16和负载因子默认为0.75，

• 不是同步的，允许null键和null。(最大容量是2的30次方)

原理：

内部采用数组 + 链表 + 红黑树，数组也就是桶，默认大小为16；

• 首先计算索引/数组的下标：

  • 通过hash函数(key的hashcode() ^ key的hashcode右移16位)计算key的hash值,并 & 数组的length - 1（相当于求模）

• 如果没有发生冲突，直接插入

• 发送冲突时首先采用拉链法解决：

  • 当链表长度>=8,数组容量<64时，数组扩容，重新哈希；

  • 当链表长度>=阈值8，数组容量大于等于64时，链表转化为红黑树。

• 链表长度<阈值 6时，红黑树转化为链表

• 插入后，会将size++,检查是否超过 容量 * 负载因子，超过则进行扩容。

1.面试题：HashMap中hash函数是怎么实现的？还有哪些hash函数的实现方式？

对于key的hashCode做hash操作，无符号右移对于key的hashCode做hash操作，无符号右移16位然后做异或运算。
还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移16位异或运算效率是最高的。至于底层是如何计算的我们下面看源码时给大家讲解。

2.面试题：当两个对象的hashCode（实际是hash这个field）相等时会怎么样？

会产生冲突，若key值内容(或者地址相同，或者地址不同equals返回ture内容相同)相同则替换旧的value.不然连接到链表后面，链表长度超过阈值会产生冲突，若key值内容(或者地址相同，或者地址不同equals返回ture内容相同)相同则替换旧的value.不然连接到链表后面，链表长度超过阈值8就转换为红黑树存储。

3.面试题：何时发生哈希碰撞和什么是哈希碰撞,如何解决哈希碰撞？

只要两个元素的只要两个元素的key计算的哈希码值相同就会发生哈希碰撞。jdk8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。

4.面试题：如果两个键的hashcode相同，如何存储键值对？

hashcode相同，通过hashcode相同，通过equals比较内容是否相同。
相同：则新的value覆盖之前的value
不相同：则将新的键值对添加到哈希表中

5.在不断的添加数据的过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

6.JDK1.8和1.7中的HashMap有什么不同

• 底层数据结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构（当链表长度大于8，转为红黑树）

• 1.7中新增节点采用头插法，1.8中新增节点采用尾插法。这也是为什么1.8不容易出现环型链表的原因。

• 1.8rehash时保证原链表的顺序，而1.7中rehash时有可能改变链表的顺序（头插法导致）。

LinkedHashMap（HashMap + 双链表,实现了1个存取有序的HashMap）

1.继承HashMap，其中n内部类Entry继承HashMap的内部类Node，并增加了2个属性，一个befor，1个after,用于指示结点的前1个结点和下一个结点，保持顺序用

2.同时自己有2个属性head,tail,分别用于指示双链表的头和尾

3.另外还有1个重要的属性accessOrder，默认为false时，表示插入顺序；为true时表示访问顺序。

ArrayMap