Set是如何保证元素不重复的

Znyoung

Set是如何保证元素不重复的

在Java的Set体系中，根据实现方式不同主要分为两大类。HashSet和TreeSet。

HashSet 是哈希表实现的，HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束；底层基于HashMap

在HashSet中，基本的操作都是有HashMap底层实现的，因为HashSet底层是用HashMap存储数据的。当向HashSet中添加元素的时候，首先计算元素的hashCode值，然后通过扰动计算和按位与的方式计算出这个元素的存储位置，如果这个位置为空，就将元素添加进去；如果不为空，则用equals方法比较元素是否相等，相等就不添加，否则找一个空位添加。

TreeSet 是二叉树实现的，TreeSet中的数据是自动排好序的，不允许放入null值；底层基于TreeMap。

TreeSet的底层是TreeMap的keySet()，而TreeMap是基于红黑树实现的，红黑树是一种平衡二叉查找树，它能保证任何一个节点的左右子树的高度差不会超过较矮的那棵的一倍。
TreeMap是按key排序的，元素在插入TreeSet时compareTo()方法要被调用，所以TreeSet中的元素要实现Comparable接口。TreeSet作为一种Set，它不允许出现重复元素。TreeSet是用compareTo()来判断重复元素的。

HashSet，TreeSet，LinkedHashSet，BitSet有何区别

功能不同：HashSet是功能最简单的Set，只提供去重的能力；LinkedHashSet不仅提供去重功能，而且还能记录插入和查询顺序；TreeSet提供了去重和排序的能力；BitSet不仅能提供去重能力，同时也能减少存储空间的浪费，不过对于普通的对象不太友好，需要做额外处理。
实现方式不同：HashSet基于HashMap，去重是根据HashCode和equals方法的；LinkedHashSet是基于LinkedHashMap，通过双向链表记录插入顺序；TreeSet是基于TreeMap的，去重是根据compareTo方法的；BitSet基于位数组，一般只用于数字的存储和去重。
其实BitSet只是叫做Set而已，它既没有实现Collection接口，也和Iterable接口没有什么关系，但是是名字相似而已