HashSet和TreeSet的实现与原理

HashSet和TreeSet有什么区别呢？

　　他们的区别主要在他们底层的数据结构不同。HashSet使用的HashMap来实现的，而TreeSet使用的TreeMap来实现的。

HashMap和TreeMap的区别呢？

　　HashMap是一个最常用的数据结构，它主要用于我们又通过固定值（key）获取内容的场景，时间复杂度可以最快优化到O(1)，当然效果不好的时候时间复杂度是O(logN)或者O(n)。虽然固定值查找提高了速度，但是HashMap不能保证固定值，也就是key的顺序，所以这个时候TreppMap就出现了，虽然它的查找、删除、更新的时间复杂度都是O(logN)，但是它保证了key的有序性。

HashMap和TreeMap的底层实现有什么不同呢？

　　　HashMap使用的是数组和哈希的方式实现，巧妙通过可以的哈希路由到每个数组用于存放内容，这时候通过key获取value的时间复杂度就是O(1)，当然因为key的哈希可能碰撞，所以就需要针对碰撞的时候做处理，HashMap里面每一个数组里面存的其实是一个链表，key的哈希冲突以后会追加到链表上面，这个时候再通过key获取value的时候时间复杂度就是O(n)，那么碰撞越多的时候查询是不是会变得很慢呢？最后为了优化这个时间复杂度，HashMap当一个key碰撞次数超过treeify threshold的时候就会把链表转化成红黑树，这样虽然插入的时候也增加了时间复杂度变成了O(logN)，说到红黑树就把HashMap和TreeMap联系到一起了，因为TreeMap的底层实现就是红黑树。

那为什么用红黑树而不用二叉搜索树呢？

　　二叉搜索树是左子树的值小于根节点，右子树的值大于根节点，如果构建根节点以后插入的数据是有序的，那么构造出来的二叉搜索树就不是平衡树，二十一个链表，那么它的时间复杂度就是O(n)。红黑树因为每个节点都是黑色或者红色两种颜色，当然他也有一些特性，

　　　　1.根节点是黑色的

　　　　2.红色节点的子节点和父节点都是黑色

　　　　3.任何一条路经的黑色节点个数相同。

HashSet和TreeSet的实现与原理

原文：https://www.cnblogs.com/xp0813/p/11695443.html