map HashMap HashTable ConcurrentHashMap (必须阅读源码，必问题目)

  1. 父类不同 HashTable 继承 Dictionary， HashMap 继承 abstractMap，它们都是Map接口的实现类 ，都是键值对集合。
  2. 最重要的区别：多线程同步特性不同 HashMap同一时间允许多个线程同时进行操作，效率相对较高 但是可能出现并发错误；Hashtable 同一时间只允许一个线程进行操作，效率相对较低 但是不会出现并发错误。
  3. 它们对于null的处理不同 HashMap 无论主键还是值对象，都可以存放null，只不过主键要求唯一，所以只能存放一个null；Hashtable对null零容忍，无论主键还是值 都不能添加null，否则直接出现异常。
  4. 它们底层实现的细节不同 HashMap 底层默认分16个小组 分组组数可以指定，但最终结果一定是2的n次方数（为什么呢）因为计算散列小组的时候 使用：x & (分组组数-1)，效率高； Hashtable 底层默认分11个小组，分组组数可以任意指定，计算散列小组的时候 使用：x %分组组数。
  5. 底层数据结构 JDK 1.8 前， 两者【底层数据结构】 = 【链表 + 数组 】；JDK1.8之后 HashMap 底层数据结构变化 ，链表长度过长(默认超过8时)，则链表树化为红黑树，提高搜索效率。
  6. 它们出现的版本不同 HashMap since JDK1.2； Hashtable since JDK1.0

说说String中hashcode的实现

源码：

public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
    char val[] = value;
    for (int i = 0; i < value.length; i++) {
        h = 31 * h + val[i];
    }
    hash = h;
}
return h;
}

String类中的hashCode计算方法还是比较简单的，就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。

哈希计算公式可以计为s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]

那为什么以31为质数

主要是因为31是一个奇质数，所以31i=32i-i=(i<<5)-i，这种位移与减法结合的计算相比一般的运算快很多。

说说jdk1.8中hashmap有什么变化

  1. 由数组+链表的结构改为数组+链表+红黑树。
  2. 优化了高位运算的hash算法：h^(h>>>16)
  3. 扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。
    发生hash碰撞时，java 1.7 会在链表的头部插入，而java 1.8会在链表的尾部插入。
    在java 1.8中，Entry被Node替代(换了一个马甲）
    最后一条是重点，因为最后一条的变动，hashmap在1.8中，不会在出现死循环问题。

为什么在解决hash冲突的时候，不直接用红黑树， 而选择先用链表，再转红黑树

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。 当元素小于8个当时候，此时做查询操作，链表结构已经能保证查询性能。
当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

我不用红黑树，用二叉查找树可以么

可以。但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。

当链表转为红黑树后，什么时候退化为链表

为6的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。
假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，
如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

HashMap在并发编程环境下有什么问题

  1. 多线程扩容，引起的死循环问题
  2. 多线程put的时候可能导致元素丢失
  3. put非null元素后get出来的却是null

    在jdk1.8中还有这些问题么

    在jdk1.8中，死循环问题已经解决。其他两个问题还是存在。

你一般怎么解决这些问题的？

比如ConcurrentHashmap，Hashtable等线程安全等集合类。

解决hash冲突的方法

比较出名的有四种

  1. 开放定址法 一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入.
  2. 链地址法 链地址法的基本思想是：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。
  3. 再哈希法 再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
  4. 公共溢出区域法 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

几种数组copy方法的速度差异

  1. for 循环逐一复制 for循环适合于小型数组
  2. System.arraycopy()
  3. Arrays.copyOf() 本质上调用的是System.arraycopy(）方法
  4. 使用clone() Object类中的一个本地方法，这里虽然返回Object，看着需要强制类型转换，但Object子类重写了这个方法，会返回相应的类型。

ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

  1. 粒度降低了；
  2. JVM 开发团队没有放弃 synchronized，而且基于 JVM 的 synchronized 优化空间更大，更加自然。
  3. 在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存。