集合类（二）

Set如何保证元素不重复?

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

1、TreeSet 是二叉树实现的，TreeSet中的数据是自动排好序的，不允许放入 null值；
2、HashSet 是哈希表实现的，HashSet中的数据是无序的，可以放入 null值，但只能放入一个null，两者中的值都不能重复，就如数据库中的唯一约束。

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

TreeSet的底层是TreeMap的keySet()，而TreeMap是基于红黑树实现的，红黑树是一种平衡二叉查找树，它能保证任何一个节点的左右子树的高度差不会超过较矮的那棵的一倍。

TreeMap是按key排序的，元素在插入TreeSet时compareTo()方法要被调用，所以TreeSet中的元素要实现Comparable接口。TreeSet作为一种Set，它不允许出现重复元素。TreeSet是用compareTo()来判断重复元素的。

HashMap、HashTable、ConcurrentHashMap区别

HashMap和HashTable有何不同？

线程安全：HashTable中的方法是同步的，而HashMap中的方法在默认情况下是非同步的。在多线程并发的环境下，可以直接使用HashTable，但是要使用HashMap的话就要自己增加同步处理了。

继承关系：HashTable是基于陈旧的Dictionary类继承来的。HashMap继承的抽象类AbstractMap实现了Map接口。

允不允许null值：HashTable中，key和value都不允许出现null值，否则会抛出NullPointerException异常。HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。

默认初始容量和扩容机制：HashTable中的hash数组初始大小是11，增加的方式是old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。

哈希值的使用不同 ：HashTable直接使用对象的hashCode。HashMap重新计算hash值。

遍历方式的内部实现上不同 ：Hashtable、HashMap都使用了Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。HashMap实现Iterator，支持fast-fail，Hashtable的Iterator遍历支持fast-fail，用Enumeration不支持fast-fail。

HashMap 和 ConcurrentHashMap 的区别？

ConcurrentHashMap和HashMap的实现方式不一样，虽然都是使用桶数组实现的，但是还是有区别，ConcurrentHashMap对桶数组进行了分段，而HashMap并没有。

ConcurrentHashMap在每一个分段上都用锁进行了保护。HashMap没有锁机制。所以，前者线程安全的，后者不是线程安全的。

PS：以上区别基于jdk1.8以前的版本。