一、哈希表

1.Hashmap和hashtable的区别？
答：1）hashtable的方法是同步的，hashmap的方法是非同步的
2）hashtable的key-value不能存储null值，而hashmap可以存储
3）hashmap只支持迭代器，hashmap的迭代器是快速失败的，hashtable支持迭代器和枚举器，hashtable不是快速失败的。
4）初始容量和扩容机制不同，hashmap的初始容量是16，hashtable的初始容量是11，hashmap扩容是翻倍，hashtable是翻倍+1。
2.hashmap的key和value都是用什么存储结构存储的？
答：hashmap存储一个单元是键值对的方式存在的，叫做Node，hashmap底层根据键值的hash值来决定存放在数组的某个位置，如果该数组位置有存储值，就用链表的方式存储在后面，如果链表长度大于8就转换为红黑树结构。
3.请你说一说hashmap？
答：hashmap是通过哈希表来作为底层存储结构的，哈希表是由数组，链表和树共同来实现的。首先根据要存入数据的键值来计算hash值，再根据这个哈希值来找到对应数组对应位置。如果该数组位置已经有元素了就用对象的equals方法来进行判断，如果返回false就以链表的方式连接在其后面，如果链表长度大于8就会转为树结构。
4.hashmap如何进行扩容的？
答：在hashmap的实现中，有一个变量叫负载因子，默认为0.75，让数组占用的长度达到了0.75倍的数组长度就会进行一次扩容，数组长度设为原来的两倍。
5.为什么hashmap扩容是两倍？
答：加快hash计算和减少hash冲突
在hashmap底层实现中，用位运算来替换取余运算，即用hash&(n-1)，如果扩容不是2的倍数，在哈希值不变的情况下会使元素在新数组中的位置发生变化，而扩容倍数是2的话一般情况下会使一半的元素发生位置变化。
减少哈希冲突，数组长度变为两倍后-1，他的二进制树的最后一位始终为1，经过hash值计算得到的位置可以是奇数可以是偶数，若不是变为两倍，最后一位可能为0，那计算出来的数组位置只能是偶数。
6.什么是哈希冲突？如何解决？
答：不同的key值经过哈希函数计算得到相同的地址，这就叫哈希冲突。
hashmap中将计算得到同一位置的元素用链表连接起来，链表长度达到8的时候会转换为红黑树。
7.哈希一致性算法了解吗？
答：有一个hash环，大小为2^32-1，比如有几个服务器，根据他的特征计算出在hash环中的位置，要存储的数据先计算hash值，然后计算在环中的位置，然后顺时针找到对应的服务器进行存储。
解决问题：如果是以前取模算法的话，如果加了一个服务器那么所有数据的位置都要发生变化，而用哈希一致性算法只需要移动部分数据。
如果服务器计算出来的位置太靠近，这种叫hash环偏斜，这样可以复制一个虚拟节点，每个服务器计算多个hash位置。
8、多线程下HashMap有什么问题？
答：数据覆盖问题，在一个线程对数组位置判空后被另一个线程夺走时间片在该位置放了元素，切换回去会直接覆盖掉原来元素。
在JDK1.7及之前链表采用的是头插法，在扩容阶段，多线程的时候会导致形成循环链表，导致查询出现死循环。
9、为什么ConcurrentHashMap比HashTable效率高？
答：hashtable不管是get还是put锁住的都是整个数组，效率低。
JDK1.7把整个表分成N个部分，每个部分单独加锁，叫锁分段技术，每个段互不影响。
JDK1.8放弃了锁分段，采用的是CAS+synchronized，锁的粒度变更小，锁的是Node。
10、ConcurrentHashMap的数据结构？
答：在JDK1.7中，ConcurrentHashMap的数据结构是segment数组加上HashEntry数组和链表。segment继承于Reentrantlock，可以支持每个segment并发访问。
在JDK1.8中，原来查询效率低，现在它的的数据结构是Node数组+链表/红黑树。
11、ConcurrentHashMap是如何操作数据的？
答：JDK1.7中，segment是继承于Lock的，在使用put的时候会先自旋尝试获得锁，如果达到最大自旋次数的时候会变成阻塞锁。get不加锁，先通过key的哈希定位到具体的segment，然后再以此hash定位到具体的元素上，用volatile保证取到的值是最新的值。
JDK1.8中，concurrenthashmap的put先看是否需要初始化，如果不需要就查看定位的位置是否为空，如果为空就CAS自旋尝试写入，如果不为空，就看需要扩容就先进行扩容操作，都不满足就用synchronized来进行操作。
12、什么是快速失败（fail-fast）和安全失败？
答：快速失败：在迭代遍历过程中如果集合中对象的内容进行了修改就会抛出异常，在集合中使用了一个modCount变量，在遍历过程中如果发生了值修改就会改变这个变量，当遍历过程中发现这个变量发生改变就抛出异常。
安全失败：在遍历的时候不直接在原集合中访问，而是先复制原有集合，在复制的集合上进行遍历。

二、树

1.什么是红黑树？
答：红黑树是一种自平衡的二叉查找树，有基本的二叉查找树特性之外还有几个定义：
1）根节点和叶子节点是黑色的。
2）叶子节点都是空节点。
3）红色节点的两个子节点是黑色的。
4）从任一一节点到其叶子节点的黑色节点数量都相同。
2.B+树和二叉树的区别？
答：二叉树每个节点都只存放一个元素；B+数每个节点存放多个元素，并且只有在叶子节点才存放实际数据。因为是多路查找的，一般情况下，相同数据下，B+数层高会小于二叉树。
3.平衡二叉查找树和红黑树的区别？
答：AVL追求绝对平衡，条件较为苛刻，插入新节点要操作的次数较多，所以适合于查找比较多的情景。
红黑树对平衡要求不那么高，查找插入删除的时间复杂度都为O(logN)，适合于增删比较多的场景。