Java 学习-集合-01

1.List、Set、Map 的区别

		元素有序	允许重复元素
List		是	是
Set	AbstractSet	否	否
	HashSet
	TreeSet	是（用二叉树排序）
Map	AbstractMap	否	Key值必须唯一，Value可重复
	HashMap
	TreeMap	是（用二叉树排序）

---

2.ArrayList 和 LinkedList 的区别

• 数据结构实现:
  ArrayList 是 动态数组 的数据结构实现；LinkedList 是 双向链表 的数据结构实现
• 随机访问效率:
  ArrayList 比 LinkedList 快，因为 ArrayList 是动态数组，每次查询都会查询整个数组，而 LinkedList 是双向链表，是线性的数据存储方式，需要移动指针从前往后一次查找
• 增加和删除效率:
  在首位的增加和删除操作，LinkedList 要比 ArrayList 效率高，因为 ArrayList 增删操作要影响数组内其他数据的下标，而 LinkedList 只需要移动指针即可

---

3.HashMap 和 HashTable 有什么区别，其底层实现是什么

• 线程安全：
  HashMap 非线程安全，HashTable 内部方法有 synchronized 处理是线程安全，但要保证线程安全，推荐使用 ConcurrentHashMap
• 效率：
  由于线程安全问题，HashMap 比 HashTable 效率高,HashTable 基本被淘汰
• 对 Null key 和 Null value 的支持：
  HashMap 支持 Null key 和 Null value；HashTable 不支持，会跑出空指针异常
• 底层实现原理
  HashMap1.7 是数组+链表，1.8 是数组+链表+红黑树
  HashTable 是数组+链表

---

4.ConcurrentHashMap 原理，jdk7 和 jdk8 的区别

• 原理：
  JDK1.7版本，ConcurrentHashMap内部使用 段（Segment） ，ConcurrentLevel有16个分段，这16个分段有独立的锁机制，每个独立的机制都是一张表，表的下面是链表，这样就可以支持并发的同时保证每张表的线程安全，提高效率

JDK1.8版本，ConcurrentHashMap内部使用synchronized + volatile + CAS 的实现，降低锁的粒度，提高效率

• 区别：
  • JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）
  • JDK1.8版本的数据结构变得更加简单，使得操作更加清晰流畅。因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构，由于粒度的降低，实现的复杂度也增加了
  • JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样效率更高