漫画：HashSet 和 TreeSet 的实现与原理
人物画像
果哥：一线公司小码农，一直走在求职的路上。
果妹：一线公司美女面试官，一直和小码农们苦苦纠缠。
面试现场
果妹上次真的是太感谢你了，你给我划重点以后我就专项复习了一下，果然第一个问题就是问的集合类，我觉得自己回答的还阔以。
那还不错哦，不过你当时是怎么回答的呢？要不然我试试你的水平？
哈，来吧，来者不拒。
好的，那你说下 TreeSet 和 HashSet 什么区别呢？
它们的区别点主要在他们的底层数据结构不同，HashSet 使用的是 HashMap 来实现，而 TreeSet 使用的是 TreeMap 来实现的。
哦？那你了解 HashMap 和 TreeMap 的区别吗？
HashMap 是一个最常用的数据结构，它主要用于我们有通过固定值(key)获取内容的场景，时间复杂度可以最快优化到 O(1) 哈，当然效果不好的时候时间复杂度是 O(logN) 或者O(n)。虽然固定值查找提高了速度，但是 HashMap 不能保证固定值，也就是 key 的顺序，所以这个时候 TreeMap 就出现了，虽然它的查找、删除、更新的时间复杂度都是 O(logN)，但是他可以保证 key 的有序性。
恩恩，掌握的还不错，那你和我说一下 HashMap 和 TreeMap 的底层实现有什么不同，才导致的他们有这么大的差异？
这个原因主要是它们底层用的实现不同，HashMap 使用的是数组(桶)和哈希的方式实现，巧妙通过 key 的哈希路由到每一个数组用于存放内容，这时候通过 key 获取 value 的时间复杂度就是 O(1)，当然因为 key 的哈希可能碰撞，所以就需要针对碰撞的时候做处理，HashMap 里面每一个数组(桶)里面存的其实是一个链表，key 的哈希冲突以后会追加到链表上面，这时候再通过 key 获取 value 的时候时间复杂度就变成了 O(n)，那么数据碰撞越来越多的时候岂不是查询很慢？最后呢为了优化这个时间复杂度，HashMap 当一个 key 碰撞次数超过 TREEIFY THRESHOLD 的时候就会把链表转换成红黑树，这样虽然插入的时候也增加了时间复杂度，但是对于频繁哈希碰撞的问题的查询效率有很大的提高，使得查询的时间复杂度变成了 O(logN)。哈，说到红黑树就把 HashMap 和 TreeMap 联系到了一起，因为 TreeMap 的底层实现就是红黑树。
呃嗯……要不然这样，我用 Idea 的 Debug 视图更形象的说一下 HashMap 的结构，这样更容易理解。
如图左边是一个测试类，因为 hash 主要调用的是 hashCode 方法，所以我直接重写了 Key 这个类的 hashCode 方法使其碰撞，就出现了右图中的 table[11]里面的 Node 的 next 内容是粉丝方向，因为他们的 hash 值都是 1008315，所以后面的 粉丝方向 被追加到了 Node 链表的尾部。当然 TreeMap 的方式你也一样可以通过这种方式看一下视图哦。不过 IDEA 默认 debug 过滤掉了内部结构视图，你需要勾选掉 Debugger->Data Views->Java->Enable alternative view for Collections class 才可以看到内部视图。
恩恩，既然你说到了红黑树，那么我想问下为什么采用的是红黑树，而不是二叉树搜索树呢？
恩，通常情况当我们听到二叉搜索树的时候以为它是平衡树，其实不是。它只是左子树的值小于根节点，右子树的值大于根节点，如果构建根节点以后插入的数据是有序的，那么构造出来的二叉搜索树就不是平衡树，而是一个链表，那么它的时间复杂度就是 O(n)，如下图。然而红黑树呢？就是通过每个节点标色的方式，每次更新数据以后再进行平衡，以此来保证其查找效率。
恩好的，那既然你说到了这里，那么你再展开说明一下它是怎么做到的每次插入都平衡。
恩，红黑树因为它每个节点都有黑色或者红色两种颜色，当然它也有一些特性，比如
1、根节点是黑色的
2、红色节点的子节点必须是黑色并且父节点也是黑色，
3、任何一条路径的黑色节点个数相同。
它通过这些特性再重新插入的时候做着色处理，配合左旋，右旋来达到最终的平衡。所以可以理解黑色红色其实是为了更好的辅助平衡。当有了这个着色以后配合红黑树的性质，就可以定义出来一个平衡的公式如下，首先插入的元素必须是红色，因为黑色破坏他的性质的几率更大。
假定 X 是新插入的节点，P是父节点，Y是叔父节点，G是祖父节点，P 为 G 的左孩子
当 Y 为红色 -> P、Y 变黑，G 变红，X 变 G
当 Y 为黑色，X 是右孩子 -> 左旋 P，X 变 P
当 Y 为黑色，X 为左孩子 -> G 变红，P变黑，右旋 G
当 P 为 G 的右孩子的时候，直接做镜像操作即可。
这个地方确实有一些不好理解，尤其是口述，来张动图感性的体会下
当然这样还是非常的晦涩，如果还是没直观，可以直接看一下下面的视频讲解版本。
https://www.bilibili.com/video/av23890827
恩掌握的还不错，那你和我说说 HashMap 是不是线程安全的呢？
哎呀，这个我还不太清楚诶，要不然我回去研究下，明天找你再考考我？
点个赞呗