HashMap、HashTable、TreeMap、ConcurrentHashMap、二叉树、红黑树
1. hashmap底层原理
详见：HashMap源码分析(一)(超级详细)
翻译自JDK8官方文档：
基于哈希表的Map接口的实现。该实现提供所有Map相关操作，且允许空值（value）和空键）（key）。（HashMap类与Hashtable大致等效，不同之处在于它是异步的，并且允许为null。）该类不保证映射的顺序。尤其是，它不能保证顺序会随着时间的推移保持不变。
HashMap非线程安全，是无序的，key和value都允许null，如果你用一个HashMap表示每个节点（value）的父节点（key），就可以用null。
JDK1.8以前，HashMap是采用“数组+链表”存储的，如果hash值相同，那这些数据会存放到同一个链表中去，该链表又称为存储桶（buckets），当一个数据中要存储到Map的时候会根据它的Key的值来计算出它的hash，通过hash来确认存储到数组的位置，如果发生哈希碰撞（跟其他数据的hash值相同）就以链表的形式存储，但是这样如果链表过长来的话，查询效率就会大打折扣。
JDK1.8主要新特性之一就是HashMap引入了红黑树，故而结构变得复杂了，但是效率也大大提升，主要体现在数据量大的时候。当桶内元素达到8个（TREEIFY_THRESHOLD）的时候，HashMap会把这个链表转换成红黑树来存储。链表查找性能是O(n)，而树结构能将查找性能提升到O(log(n))。
至于为什么是8，可以看看这篇文章：阿里面试题：为什么Map桶中个数超过8才转为红黑树
HashMap最多允许一对键值对的Key为Null，允许多对键值对的value为Null。
题外话：HashMap继承了AbstractMap，而AbstractMap类实现了Map接口，那为什么HashMap还要在实现Map接口呢？同样在ArrayList中LinkedList中都是这种结构。据说Josh Bloch自己说是写法错误。Why does LinkedHashSet extend HashSet and implement Set
2. concurrenthashmap底层实现
详见：CurrentHashMap的实现原理
HashMap是线程不安全的，在多线程环境下，使用Hashmap进行put操作会引起死循环（详见：并发HashMap的put操作引起死循环），导致CPU利用率接近100%，所以在并发情况下不能使用HashMap。
So，concurrentHashMap应运而生。大量利用了volatile，final，CAS等lock-free技术以减少锁竞争对于性能的影响。
避免全局加锁，改用局部加锁，极大地提高了并发环境下的操作速度，ConcurrentHashMap在JDK1.7和1.8中的区别较大。
JDK1.7中ConcurrentHashMap采用了数组+分段锁(Segment)的方式实现。
Segment：类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。
JDK1.8舍弃Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。采用synchronized+CAS+HashEntry+红黑树。
Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。
结构基本上和Java8的HashMap一样，不过保证线程安全性。
(1)、数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
(2)、保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
(3)、锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
(4)、链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
(5)、查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。
3. HashTable
HashTable和HashMap的实现原理几乎一样，差别无非是
HashTable不允许key和value为null。
HashTable是线程安全的。
但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。
多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，高并发时性能究极差。
4. 二叉查找树
详见：30张图带你彻底理解红黑树
Binary Search Tree。
(1)某节点的左子树节点值仅包含小于该节点值
(2)某节点的右子树节点值仅包含大于该节点值
(3)左右子树每个也必须是二叉查找树
也就是说，节点左边的值一定比它小，右边节点的值比它大，且每个节点最多两个直接子节点。
看图的话就是这样
当然，上图比较理想，我们看到左右两侧分布比较和谐，再来看一个符合BST规则但是看上去比较怪异的树：
这个也是二叉树，看上去不太平衡，而且如果你要找57，可能还没有你变成树结构之前花的时间少，为了达到这种平衡，我们就引入了红黑树，其实就是加了平衡的二叉树，即平衡二叉树。
5. 红黑树
Red-Black Tree。
自平衡的二叉查找树(BST)，但是也不是绝对平衡。
(1)节点只能是红色或者黑色；
(2)根节点是黑色，叶子节点（NULL）也是黑色的；
(3)红色节点不相邻（相邻指有连线），也就是跟红色节点直接相连的必是黑节点，兄弟节点不算；
(4)从任一节点到其任何后代NULL节点(叶子结点下方挂的两个空节点，并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点，这句话可能有点绕，就是说，整个树中的任何一个节点，到它的任一NULL后代节点，这个NULL后台节点说的是叶子节点；任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
从(4)又可以推导出，如果一个结点存在黑子结点，那么该结点肯定有两个子结点。
红黑树主要两大操作：标记（变色）和旋转（左旋、右旋）。
一般先尝试标记，如果无法标记成红黑树，就会开始尝试旋转。
当然，红黑树也不是完美的平衡二叉树，我们无法保证树完全对称，但是可以看出，左右子树黑节点层级是一样的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点，就是性质(4)，这种称为黑色完美平衡。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图1。
只影响旋转结点和其右子树的结构，因为把右子树的左结点往左子树挪了。
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图2。
只影响旋转结点和其左子树的结构，因为把左子树的右结点往右子树挪了。