HashMap、HashSet、TreeMap、LinkedHa

HashMap

1. HashMap底层实现是数组+链表。数组大小不满足时要进行扩容操作，扩容是将容量扩展为原先的2倍，并需要重新计算已经在HashMap中存储的key的hash值，因此在明确知道要多大HashMap数组大小的情况下在初始化HashMap的时指定大小能有效提高性能；

容量计算：
数组元素个数大于数组大小*装填因子，装填因子默认大小是0.75。
如果装填因子设置较小，hash冲突的概率降低，Entry链较短，添加和删除元素的效率提高，但会造成内存空间的浪费，;
装填因子大，会减少内存空间的浪费，但是添加删除操作的效率会降低。

2. HashMap进行put操作时，先对key计算出对应的hash值，然后找到这个hash值在数组中的index，并检查此处是否存在Entry链，如果存在则查看是否有键值对的key与当前key相等，有的话则用新值覆盖掉原先键值对中的value值，没有的话，则将当前键值对插入到Entry链的链头就可以了；get操作：计算出key值对应的hash值，找到该hash值在数组中的位置，再在该位置处的Entry链中查看是否存在与当前key值相等的key存在，存在的话返回value，不存在返回null；
3. 在JDK1.8之后，HashMap的实现不再是简单的数组+链表的方式了，而是数组+链表+红黑树，引入红黑树的目的在于使用HashMap的时频繁的进行put和get操作，而这两个操作又都会用到查询方法(即计算出key的hash值之后，会去查找指定hash值处的冲突链表，而链表的查找操作时间复杂度是O(n)的，因此引入了红黑树的方式来减少查询操作所带来的时间开销，红黑树的查找时间复杂度是O(lgn))。

以put方法为例：
将元素插入到指定hash对应的冲突列表(JDK1.7之前都是链表)时，首先检查当前列表是否为null，
为null则直接插入当前键值对；不为null则比较当前列表中的key值是否和当前key值相等，
相等的话将其value替换成当前要插入的值，不等的话则会判断当前列表中的元素属性是不是TreeNode，
如果是TreeNode则将当前键值对按照红黑树的规则进行插入操作，如果不是TreeNode则判断当前列表长度是否大于8，
如果大于则将当前列表转换成红黑树，然后将当前键值对插入红黑树，如果不大于8的话，则以链表的方式插入；

HashSet

1. HashSet的底层实现是HashMap，通过HashSet中的key值唯一性来达到HashSet中元素的唯一性，如果我们将要put进去的元素的key值等于已经存在在HashSet中的元素的话，那么是不会将当前元素添加到HashSet里面操作的；

TreeMap

TreeMap不同于HashMap的一点在于，TreeMap是可以按照key来进行排序的，至于排序规则的话，我们在创建TreeMap的时候可以传入一个实现了Comparator的比较器，比较规则我们可以自己制定，如果不指定比较器的话，将以ket值默认的顺序进行排序，对于key值是Integer类型的话，我测试了下将按照升序的方式进行排序，也正是因为TreeMap在插入或者删除的时候需要排序，因此在效率上不如HashMap的；

LinkedHashMap

LinkedHashMap与HashMap最大的区别在于他会保证我们添加到map中值的顺序，其实具体实现还是在HashMap中的put方法里面的，查看put源码会发现执行了recordAccess方法，而这个方法在HashMap里面是没有实现的，而LinkedHashMap继承自HashMap，对该方法进行了覆写，因此执行的就是LinkedHashMap里面的recordAccess方法了，在该方法里面默认情况下是会对插入的数据进行类似于链表排序处理的，当然你可以指定不进行排序，那么此时LinkedHashMap将和HashMap没什么区别了；

总结：

HashMap和HashTable的区别：
    (1)：HashMap是非线程安全的，HashTable是线程安全的，因此HashMap的效率相对来说比HashTable要高；
    (2)：HashMap的迭代器是会出现fail-fast现象的，我们可以用ConcurrentHashMap来替换；HashTable的迭代器不会出现fast-fail现象；
    (3)：HashMap是允许key或者value为null的，而HashTable是不允许的；
HashMap和LinkedHashMap的区别：
    (1)：两者都是非线程安全的，在迭代的过程中都会出现fast-fail现象；
    (2)：遍历LinkedHashMap的时候，其输出元素的顺序和我们插入顺序是一致的，但是HashMap在这方面是得不到保证的，他是随机的；
    (3)：当HashMap容量很大，但是里面实际元素的个数比较少的时候，使用HashMap遍历起来要比LinkedHashMap慢，因为LinkedHashMap的遍历只与存储的是实际元素的个数有关系，但是和map的存储容量没关系，而HashMap是和存储容量有关系的；但是一般情况下的话，HashMap的遍历效率要高于LinkedHashMap；
HashMap和TreeMap的区别：
    (1)：TreeMap是可以按照key进行排序的，排序规则是我们通过实现Comparator接口自己实现的，如果没有指定排序器的话，默认是按照key的升序存储的，但是HashMap是随机的，不会按照key的升序进行存储；
    (2)：两者都是非线程安全的；