HashMap和Hashtable区别

1)        线程安全性不同

HashMap是线程不安全的，HashTable是线程安全的，其中的方法是Synchronize的，在多线程并发的情况下，可以直接使用Hashtable，但是使用HashMap时必须自己增加同步处理。

2)        是否提供contains方法

HashMap只有containsValue和containsKey方法；Hashtable有contains、containsKey和containsValue三个方法，其中contains和containsValue方法功能相同。

3)        key和value是否允许null值

Hashtable中，key和value都不允许出现null值。HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。

4)        数组初始化和扩容机制

 Hashtable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。

 Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。

TreeSet和HashSet区别

HashSet是采用hash表来实现的。其中的元素没有按顺序排列，add()、remove()以及contains()等方法都是复杂度为O(1)的方法。

TreeSet是采用树结构实现（红黑树算法）。元素是按顺序进行排列，但是add()、remove()以及contains()等方法都是复杂度为O(log (n))的方法。它还提供了一些方法来处理排序的set，如first()，last()，headSet()，tailSet()等等。

注：描述算法复杂度时,常用o(1), o(n), o(logn), o(nlogn)表示对应算法的时间复杂度，是算法的时空复杂度的表示。不仅仅用于表示时间复杂度，也用于表示空间复杂度。