HashMap、HashTable、ConcurrentHash

HashMap

一切对象都可以作为Key值，但使用Object作为Key值的时候，其中一个属性改变，会导致hashCode的值也发生变化，map.get(key)因为hashCode值的变化，而无法找到之前保存的value值，同样，删除也取不到值。

HashMap、ConcurrentHashMap 在1.7跟1.8区别

1、数据结构不一样，7是数组+链表，8则是数组+链表+红黑树结构（当链表长度大于8并且数组长度大于64转为红黑树，时间复杂度从O(n)变成O(logN)提高了效率；长度小于6退化为链表）。
2、JDK8中resize()方法在表为空时，创建表；在表不为空时，扩容；而JDK7中resize()方法负责扩容，inflateTable()负责创建表。
3、8中没有区分键为null的情况，而7版本中对于键为null的情况调用putForNullKey()方法。但是两个版本中如果键为null，那么调用hash()方法得到的都将是0，所以键为null的元素都始终位于哈希表table【0】中。
4、8采用尾插法，7是头插法。这也是为什么8不会出现循环链表的原因。
5、7是用Entry数组来存储数据，8是Node数组来存储数据（但这个Node可能是链表结构，也可能是红黑树结构）；node继承了entry，多了一条指针指向下一条数据
6、7中是通过更改hashSeed值修改节点的hash值从而达到rehash时的链表分散，而8中键的hash值不会改变，rehash时根据（hash&oldCap）==0将链表分散。
7、8rehash时保证原链表的顺序，而7中rehash时有可能改变链表的顺序（头插法导致）。
8、在扩容的时候：7在插入数据之前扩容，而8插入数据成功之后扩容。

当两个对象的hashCode相同会发生什么

从插入，删除，查询等方面叙述，以及冲突严重便会扩resize，转红黑树等
链表长度大于8会扩容，当数组长度大于64，链表长度大于8，则会转红黑树；链表长度小于6，红黑树转回链表;

为什么要用按位与运算 和 按位异或运算

位运算支持底层二进制运算，比取模性能高，
异或运算使哈希值的高位与低位都参与索引的计算，减少哈希冲突

二叉树、自平衡树、红黑树、B树、B+树、B*树区别

二叉树：
自平衡树：为了解决二叉查找树退化成链表的问题，具有二叉树全部特性。每个节点的左子树和右子树的高度差至多等于1。
缺点：每次进行插入/删除节点的时候，几乎都需要通过左旋和右旋来调整至平衡状态，在插入/删除很频繁的场景中，性能低下
红黑树（自平衡二叉树）：
B树：子树越多表示数的高度越低，搜索效率越高；可以在文件查找的时候每次只加载一个磁盘页的内容存入内存来查找。而红黑树在内存中查找非常块，但是如果在数据库和文件系统中，显然B树更优
B+树：与B树相比，数据都存在叶子节点，各页子节点通过指针，形成链表
B*树：在B+树的非根和非叶子结点再增加指向兄弟的指针

为什么B+树用于数据库中的索引呢？

因为在数据库中select常常不只是查询一条记录，常常要查询多条记录。比如：按照id的排序的后10条。如果是多条的话，B树需要做中序遍历，可能要跨层访问。而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能够把所有数据取出来了。

HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap、HashTable区别及其使用场景。

HashTable是在各操作方法上加synchronized，锁粒度小
ConcurrentHashMap使用分段锁，锁粒度大
Hashtable通过synchronized修饰方法 来保证线程安全
ConcurrentHashMap通过synchronized和CAS操作来实现线程安全

由此抛出的问题

为什么要用synchronized，cas不是已经可以保证操作的线程安全吗？

CAS也是适用一些场合的，比如资源竞争小时，是非常适用的，不用进行内核态和用户态之间的线程上下文切换，同时自旋概率也会大大减少，提升性能，但资源竞争激烈时（比如大量线程对同一资源进行写和读操作）并不适用，自旋概率会大大增加，从而浪费CPU资源，降低性能

底层数组长度为何总是2的n次方；为什么默认是16，不是4，不是8

数论——研究整数性质的一门数学分科。
1、当hashMap的数组大小为2的整次幂时，按位与运算与取模运算结果一致
2、输入的数组长度若不是2的整数次幂，HashMap通过位移运算和异或运算得到的肯定是2的幂次数，并且是不小于那个数最近的数字
实现：
通过左移、无符号右移、按位或运算，返回给定目标容量大小的2次方

图片.png 图片.png

HashMap内部节点是有序的吗

是无序的，根据hash值随机插入
有序的Map： LinkedHashMap 和 TreeMap

hashMap中get是如何实现的？

先根据key计算hash值，通过与运算计算下标获取bucket位置，如果在桶的首位上就可以直接返回；如果有hash冲突，则利用equals方法去遍历链表或红黑树中查找节点。

hashMap的loadFactor加载因子，为啥默认是0.75？

提高空间利用率和减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小，太小了空间利用率很低，太大了容易出现哈希碰撞，增加了查询时间成本

hashMap线程不安全？

并发put()；会出现数据覆盖问题
扩容死循环
解决：尾插法

解决哈希冲突的三种方法

hashMap采用的是拉链法（链表+红黑树）
拉链法（链地址法）：冲突了就形成单链表，把数据添加到链表后面
缺点：处理冲突简单，且无堆积现象；链表指针需要额外的空间；适合于造表前无法确定表长的情况；平均查找长度较短
开放地址法：冲突了就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入 。 线性探查法、线性补偿探查法（常数）、随机探测（常数+随机数）
缺点：冲突代价高，删除麻烦
再散列法：冲突后，再次计算哈希值，第二次，第三次~； 直到无冲突
缺点：虽然不会发生聚集，但是增加了计算时间

哪些手段避免哈希冲突的

1、提高哈希算法，将hashCode的高位与低位进行异或运算，使得高位与低位都参与计算索引；减少冲突几率
2、数组长度为2的n次幂
3、加载因子默认0.75，扩容机制