[架构基本功]TreeSet排序研究

近来在优化一些写好的排序，所以会对数据结构考虑得更深入，为什么面试都喜欢面试数据结构，面试对数据结构得熟悉层度，很大的情况下是因为只有数据结构熟悉了，才能用更少时间找到优化时间和空间的方法。

估计很多人都有过 排序 的经验，估计也很多会用到Collections里面的一些数据结构，例如List Set 等等。

这一节我们讨论的是TreeSet。

TreeSet有什么好处呢？

插入的同时就立刻进行排序，你只需要设定好比较器，就能按照设定来进行排序，因为他是一个红黑树，树的特征是拥有排序。同时他是个Set，只要比较器认为是同一个，就会被去重。

TreeSet使用的结构

其内部是使用了TreeMap，Set值保存在Map的key中，value存了一个Object，Map中如果Key值相同会被认为是同一个，这样就能够实现数据去重。TreeMap内部维护的是一个红黑树。因为是树状结构，那么其查询效率和插入效率都是log(n)，当然对应耗时，会因为红黑树平衡调整，会有相应的耗时。

TreeSet不是线性安全的，线性安全需要使用ConcurrentSkipListSet。内部是SkipList（跳表）结构实现，在理论上能够在O(log(n))时间内完成查找、插入、删除操作。

跳表本质是一个链表，只是链表节点中会记录一定跨度后的的链表节点地址。

####属性变更问题 TreeSet可以指定比较器Comparator，可以通过类中继承Comparable来进行比较迭代。但是里面的属性变化了，不会重新触发排序。需要重新插入排序。例如，TreeSet保存的类文件，类中包含一些列表，列表数据组装并且同时插入到TreeSet，正好比较器需要比较列表中元素的属性，这时候，因为列表是一直在变化的。会出现，类文件插入到TreeSet的时候，再变更类文件中列表的属性，是无法触发TreeSet中自动排序的。TreeSet无法判断到其对象变更情况。

你可以采取的策略是

1.插入到TreeSet前需要确定类文件属性不再变更。

2.触发变更的时候，重新将其赋值到TreeMap当中，更新比较。

####去重问题 如果比较器中返回为0 ，Set中认为是相等的，会执行去重操作。如果比较器逻辑有问题，可能会触发死循环比较。

####比较器效率问题 TreeSet是边插入边比较，而Collections.sort函数应用场景是List队列当中，两者都能是用比较器来完成操作。

ThreeSet的底层实现是红黑树，它在创建set的过程中实现排序。Collections.sort是在对整个集合进行排序，按道理来说使用TreeSet插入集合元素直至建立整个TreeSet过程中实现排序在时间方面要比Collections.sort对整个集合进行排序效率要高很多，因为它在每次搜索要插入的位置时耗费的时间为log(n)，n代表的是当前集合的长度，但实验表明使用Collections.sort对集合进行排序时间耗费要少些。

出现这种情况的原因是

1.TreeSet的搜索时间为log(n)，明显上是比List有优势的。

2.TreeSet在插入的时候需要先创建节点，而List比较并不需要增加额外节点。

3.TreeSet基于红黑树，那么其每次插入都需要检查和维护红黑树平衡，如果失衡会触发红黑树结构调整。

基于2，3两点，无疑会比List更加耗时，数据越多，效率差距越明显。当然这里没有加入List的插入创建节点时间，就算将插入时间加入进来，估计效率上海市Collections.sort占优。