集合

集合的分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Collection 接口的接口 对象的集合（单列集合）
├——-List 接口：元素按进入先后有序保存，可重复
│—————-├ LinkedList 接口实现类， 链表， 插入删除， 没有同步， 线程不安全
│—————-├ ArrayList 接口实现类， 数组， 随机访问， 没有同步， 线程不安全
│—————-└ Vector 接口实现类 数组， 同步， 线程安全
│ ———————-└ Stack 是Vector类的实现类
└——-Set 接口： 仅接收一次，不可重复，并做内部排序
├—————-└HashSet 使用hash表（数组）存储元素
│————————└ LinkedHashSet 链表维护元素的插入次序
└ —————-TreeSet 底层实现为二叉树，元素排好序

Map 接口 键值对的集合 （双列集合）
├———Hashtable 接口实现类， 同步， 线程安全
├———HashMap 接口实现类 ，没有同步， 线程不安全
│—————–├ LinkedHashMap 双向链表和哈希表实现
│—————–└ WeakHashMap
├ ——–TreeMap 红黑树对所有的key进行排序
└———IdentifyHashMap

List、Map、Set 接口存取元素特点

1. List 以特定索引来存取元素，可以有重复元素。

2. Set 不能存放重复元素（用对象的equals()方法来区分元素是否重复）。

3. Map 保存键值对（key-value pair）映射，映射关系可以是一对一或多对一。

Collection 和 Collections 的区别

1. Collection是集合类的上级接口，继承与它的接口主要有Set 和 List.
2. Collections是针对集合类的一个帮助类，它提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

ArrayList 和 LinkedList 的区别

1. ArrayList 和 LinkedList 都实现了List接口
2. ArrayList是实现了基于动态数组的数据结构，LinkedList实现了基于链表的数据结构。
3. 对于随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要移动指针。
4. 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
5. ArrayList和LinkedListed都是非线程安全的，但可通过工具类Collections中的synchronizedList方法转换成线程安全容器

HashMap 和 Hashtable 的区别

1. 继承的父类

• 都实现了Map、Cloneable（可复制）、Serializable（可序列化）接口。
• HashMap: 继承自AbstractMap类。
• HashTable: 继承自Dictionary类。

2. HashMap 是线程不安全的，效率高；HashTable 线程安全，效率低。

3. HashMap允许键和值是null，而Hashtable不允许键或者值是null

Iterator 和 ListIterator 的区别

1. Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。
2. Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。
3. ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。

Java集合类里面最基本的接口

• Collection：代表一组对象，每一个对象都是它的子元素。
• Set：不包含重复元素的Collection。
• List：有顺序的collection，并且可以包含重复元素。
• Map：可以把键(key)映射到值(value)的对象，键不能重复。

ConcurrentHashMap

1. ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment
2. HashEntry 用来封装映射表的键 / 值对
3. Segment 用来充当锁的角色
4. Concurrenthashmap线程安全的

TreeMap

1. TreeMap是一个有序的key-value集合，基于红黑树（Red-Black tree）的 NavigableMap实现。
2. 该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator进行排序，具体取决于使用的构造方法。
3. 红黑树性质：

• 每个节点要么是红色，要么是黑色。
• 根节点永远是黑色的。
• 所有的叶节点都是空节点（即 null），并且是黑色的。
• 每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
• 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

HashMap

1. 如果HashMap的key是自定义的类，就必须重写hashcode()和equals()。
2. HashMap在JDK1.8的版本中引入了红黑树结构做优化
3. 当链表元素个数大于等于8时，链表转换成树结构，小于等于6时，树结构还原成链表。
4. 如果一个HashMap不停的插入、删除元素，并且链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低