Java常用集合与实现

HashMap

• 1.8版本的变化

1. 加入红黑树
2. 插入数据方式变为尾插法、
3. hash值计算方式变为2次扰动处理（1次位运算+1次异或）
4. 扩容策略变化，插入后再扩容

• 线程不安全：
  1.7中，扩容采用头插法，可能出现循环链表，为了修复改为尾插法。
  HashMap任意版本中，如果在插入数据时多个线程命中了同一个槽，可能数据覆盖的情况，导致线程不安全。

线程不安全解决方案

1. 给HashMap直接加锁
2. 使用Hashtable，比方法1效率高，原理是在方法上加Synchronized锁
3. 使用concurrentHashMap，本质是减小了锁的粒度，减少线程竞争，更高效。

• 与concurrentHashMap的区别

ConcurrentHashMap

版本区别：

1. 1.7 锁粒度 基于segment 1.8基于entry节点
2. 1.7锁用reentrantLock 1.8用synchronized
3. 底层结构1.7 segment + HashEntry + Unsafe ； 1.8 Synchronized + CAS + Node + Unsafe

ArrayList & LinkedList（双向链表）

1. 对于随机访问，ArrayList 优先，因为基于数组实现，存储空间连续，支持随机访问
2. 对于新增和删除数据，LinkedList优先，因为ArrayList要移动数据。
3. 同样数据量LinkedList所占空间更小，ArrayList需要预留空间便于后续数据增加，而LinkedList只需要增加一个节点。

HashSet

set继承于Collection接口，不允许出现重复元素，并且无序。
HashSet基于HashMap实现，底层用HashMap保存元素。
元素哈希值通过元素hashcode方法来获得，首先判断hashcode，之后判断equals，如果都相同视为同一个元素。