链接：https://pan.baidu.com/s/1U46QMGWbtFovweaKlm2FCA 

提取码：qqay 

 

1. List和Set的区别

List和Set都是继承自Collection接口，List是有序可重复的，Set是无序不可重复的。Set放入元素的位置是根据其hashCode决定的，把一个Object放入一个Set前，必须都equals（）方法进行定义。List可以用for循环和迭代器查询，Set只能用迭代器查询。List查询快，插入和删除效率低；Set相反。

2. HashSet如何元素不重复

先用Hashcode判断地址是否相等，如相等再用equals方法比较。

3. HashMap ，HashTable和concurrentHashMap

HashMap 线程不安全的 ，HashTable 线程安全的任一时间只有一个线程能写Hashtable，CurrentHashMap线程安全的，引入分段锁。

HashMap结构

   Jdk1.8前   数组+链表

   JDK1.8后   数组+链表+红黑树（链表长度默认8）

Hash值的操作

   Hashcode的高16位和低16位进行异或计算，这个操作也叫作扰动函数。

这么设定的原因：

a.尽量减少hash碰撞，越分散越好

b.算法一定要高效，因为是高频操作所以要高效，用位运算

c.混合原始哈希码的高位和低位，可加大低位的随机性，减少碰撞

只有重写过hashcode和equals方法的对象才能作为hashmap的key.

HashTable是直接在操作方法上加synchronized关键字，锁住整个数组。从而达到线程安全。无论key还是value都不能为null

ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术

有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。

4. 红黑树

红黑树是一颗平衡二叉树。

特性：

a.根节点是黑色的；

b.每个叶子节点是黑色的；

c.节点非红即黑；

d.每个红节点的两个子节点必定是黑的；

e.任一节点到叶子节点的路径包含相同个数的的黑色节点。

5. java 8对hashmap的优化

由 数组+链表 的结构改为 数组+链表+红黑树。

拉链过长会严重影响hashmap的性能，所以1.8的hashmap引入了红黑树。

在链表元素数量超过8时改为红黑树，少于6时改为链表，中间7不改是避免频繁转换降低性能。

相对于链表，改为红黑树后碰撞元素越多查询效率越高。链表O(n)，红黑树O(logn)。

  优化了高位运算的hash算法：h^(h>>>16)

将hashcode无符号右移16位，让高16位和低16位进行异或。

  扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。

不需要重新计算hash，只需要根据原来hash值新增的bit是1还是0分别放进两个链表lo和hi（非红黑树的情况）里，0的话索引没变，1的话索引变为原索引加原来的数组长度。

因为用的尾插法所以新数组链表不会倒置，多线程下不会出现死循环。

 

6. Hashmap为什么由头插法改为尾插法？

A.因为头插法会造成死链 

B.JDK7用头插是考虑到了一个所谓的热点数据的点(新插入的数据可能会更早用到)，但这其实是个伪命题,因为JDK7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置(就是因为头插) 所以最后的结果 还是打乱了插入的顺序