继承关系
Collection子类继承结构
Map子类继承关系
List (允许null元素)
List 接口的部分函数原型
1. ArrayList
特性
• 可变大小的数组
• 非线程安全
• 当更多的元素加入到ArrayList时，其大小会动态的增长。每次增长的空间是其size的50%。初始容量是10.
扩容时机
当数组的大小大于初始容量的时候(比如初始为10，当添加第11个元素的时候)，就会进行扩容，新的容量为旧的容量的1.5倍。
扩容方式
扩容的时候，会以新的容量建一个原数组的拷贝，修改原数组，指向这个新数组，原数组被抛弃，会被GC回收。
// for遍历移除多个元素时，size是会改变的，即移除一个元素，size减一，则下一次遍历到的元素实际为i+2；解决：在移除元素后，设置i--
for(int i=0;i<list.size();i++) {
if(list.get(i)==2) {
list.remove(i);
i--;
}
}
// 迭代器中使用ArrayList.remove()，ArrayList.remove()修改了modCount值，而迭代器中的next()方法中每次调用都会检查modCount与expectedModCount是否相等，不等则表示ArrayList结构改变，抛出异常
Iterator<Integer> it=list.iterator();
while(it.hasNext()) {
if(it.next()==2) {
it.remove();
}
}
System.out.println(list.toString());
// for加强循环中使用ArrayList.remove()，因为for加强循环采用迭代器技术进行遍历
for(Integer i: new ArrayList<Integer>(list)) {
if(i==2) {
list.remove((Integer)i);
}
}
2. Vector
特性
• Vector和ArrayList类似，比ArrayList多了线程安全
• 初始容量是10，默认每次动态增加空间是当前大小的2倍
（可在构造函数指定动态增加的大小为capacityIncrement）
3. LinkedList
特性
• 是一个双链表
• 非线程安全
• 在添加和删除元素元素时具有比ArrayList更好的性能
• 实现了Queue接口（非直接实现，是通过实现Queue的子接口Deque间接实现Queue），该接口比List提供了更多方法。包括从尾部添加元素：offer(E)、返回第一个元素但不出队:peek()、返回第一个元素并出队：poll()等。
由于LinkedList不同步,可以通过synchronizedList转化为同步的List
List list= Collections.synchronizedList(new LinkedList());
对比
| 长度可变 | 线程安全 | 初始大小 | 扩容倍数 | |
|---|---|---|---|---|
| ArrayList | 是 | 否 | 10 | 0.5 |
| Vector | 是 | 是 | 10 | 2 |
| LinkedList | 是 | 否 | - | - |
Set
不能包含重复元素的 Collection。
特征
- Set 不包含满足 e1.euqals(e2)
- 最多包含一个 null 元素(这里是指 不支持插入 null) 不可随机访问包含的元素
- Set 没有同步方法。
Set接口部分函数原型
HashSet
HashSet 是基于 HashMap 来实现的。
一次 HashSet 的存取相当于 HashMap 的一次存取，相当于只看中 HashMap 的 Key，不需 要 Value 部分（Value 使用一个 static final 的Object 对象标识）
HashSet 判断对象是否存在集合中
1 . 调用obj.hashCode()，得到对应的hashcode值。
- 如果集合中没有存储这个 hashcode 对应的对象，则直接添加。
hashcode- 如果集合中已经存储了这个hashcode对应的对象，则调用equals判断是否对象相同
重写equals方法，必须重写hashCode函数原因：
如果只重写equals，根据两个对象equals返回true，但是hashCode默认却不同，集合还是会添加新元素。
Queue(不允许null元素)
队列，特点是先进先出。
| 操作 | 推荐方法 | Collection方法 |
|---|---|---|
| 加入元素 | offer() | add() |
| 删除元素 | poll() | remove() |
| 返回队列的第一个元素 | peek() | element() |
Queue 接口的部分函数原型
1.
2. //插入新元素到队列，如果插入成功，返回 true，
3. //如果队列已满，抛出 IllegalStateException 异常
4. boolean add(E e);
5.
6. //插入新元素到队列，如果插入成功返回 true
7. //如果队列已满，返回 false，但不抛出异常
8. boolean offer(E e);
9.
10. //返回第一个元素，并将该元素从队列中删除
11. //如果队列为空，抛出异常
12. E remove();
13.
14. //返回第一个元素，并将该元素从队列中删除
15. //如果队列为空，返回 null
16. E poll();
17.
18. //返回队列的第一个元素，
19. //如果队列为空，抛异常
20. E element();
21.
22. //返回队列的第一个元素， 23. //如果队列为空，返回 null
23. offer()
24. remove()
24. E peek();
BlockingQueue 阻塞队列
| 操作 | 方法 | 描述 |
|---|---|---|
| 插入元素 | put() | 如果队列已满，则一直等待(阻塞) |
| 返回第一个元素并删除 | take() | 如果队里为空，则一直等待(阻塞) |
-
ArrayBlockingQueue和LinkedBlockingQueue是阻塞队列的不同实现，即一个是通过数组方式，一个是通过链 表的方式实现的阻塞队列。
SynchronousQueue
- SynchronousQueue不能存储元素。
- 每个put()都必须等到一个take()，才能解除阻塞, 反之亦然。
ArrayBlockingQueue
- 一旦创建好这个数组，就不能再增加其容量
LinkedBlockingQueue
- 可选的容量范围构造方法参数作为防止队列过度扩展的一种方法。
- 如果未指定容量，则它等于 Integer.MAX_VALUE。除非插入节点会使队列超出容量，否则每次插入后会动态地 创建链接节点 ，容量范围可以在构造方法参数中指定作为防止队列过度扩展。
- 此对象是 线程阻塞-安全的
ArrayBlockingQueue 和 LinkedBlockingQueue 的区别
-
队列中锁的实现不同
ArrayBlockingQueue实现的队列中的锁是没有分离的，即生产和消费用的是同一个锁;。
LinkedBlockingQueue实现的队列中的锁是分离的，即生产用的是 putLock，消费是takeLock -
在生产或消费时操作不同
ArrayBlockingQueue实现的队列中在生产和消费的时候，是直接将枚举对象插入或移除的；
LinkedBlockingQueue实现的队列中在生产和消费的时候，需要把枚举对象转换为node<E>进行插入或移除，会影响性能。 -
队列大小初始化方式不同
ArrayBlockingQueue 实现的队列中必须指定队列的大小;
LinkedBlockingQueue实现的队列中可以不指定队列的大小，但是默认是Integer.MAX_VALUE
特殊的接口 BlockingDeque
既实现了 BlockingQueue 又实现了 Deque,而 BlockingDeque 的实现类：LinkedBlockingDeque
Deque 双向队列
1. void addFirst(E e);
2. void addLast(E e);
3. boolean offerFirst(E e);
4. boolean offerLast(E e);
5. E removeFirst();
6. E removeLast();
7. E pollFirst();
8. E pollLast();
9. E getFirst();
10. E getLast();
11. E peekFirst();
12. E peekLast();
Stack
继承自 Vector(可增长的对象数组)，也是同步的。通过五个操作对类 Vector 进行了扩展，允许将向量视为堆栈。
public E push(E item);
public synchronized E pop();
// 返回栈顶的元素，但不将其出栈
public synchronized E peek();
// 堆栈中查找项并确定对堆栈顶距离
public synchronized int search(Object o);
// 测试堆栈是否为空
public boolean empty();
Map
Map子类继承关系
• 一个映射不能包含重复的键，每个键最多只能映射到一个值
• 使用keySet()抽取key序列，将所有key生成一个Set
• 使用values()抽取value序列，将所有value生成一个Collection
• TreeMap类映射实现可明确保证其顺序，HashMap则不保证顺序
Map接口部分函数原型
1. HashMap (不是线程安全)
HashMap 本质是数组加链表。
- 新插入的在前面。
- 不保证映射顺序，特别是它不保证该顺序恒久不变
- 里面存放的是 键值对(Map.Entry)
HashMap put：
- 首先根据key的hashCode找到对应数组的位置
- 然后遍历该位置的链表，查找key是否已经存在
- 如果key已经存在，则直接更新value,并将旧的value作为函数返回
- 如果key不存在，则通过头插法，将新的键值对放入当前链表的第一个位置
PS: (null key 总是放入数组的第 0 个位置，因为 null 的哈希码为0)
HashMap get：
- 首先根据key的hashCode找到对应数组的位置
- 然后遍历该位置的链表，查找key是否已经存在
HashMap 扩容（loadFactor）加载因子
默认情况下 loadFactor 为 0.75.即当 HashMap 元素超过 length*0.75 时，需要扩大一倍， 然后重新计算元素在数组的位置。
PS: 这是一个非常消耗性能的操作。因此，如果已经预知 HashMap 中元素
个数那么预设元素个数能够有效提高 HashMap 性能。
Fail-Fast(快速失败)机制
HashMap 不是线程安全的，因此在使用迭代器过程中，其他线程修改
了 Map，那么将抛出ConcurrentModificationException异常，这就是 fail-fast 策略。
实现原理为，通过 modCount 域，顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，在迭代器初始化过程会将这个值赋给迭代器的exepctedModCount，迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他的线程修改了 Map。
JDK1.8中HashMap的性能优化
JDK1.8在JDK1.7的基础上针对一个链上数据过多（即拉链过长的情况）导致性能下降，增加了红黑树来进行优化。即当链表超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
put新元素流程:
- 判断该链p是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则执行2
- 链为链表遍历p，判断链表长度是否大于8，如果大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作
红黑树
HashMap结构
LinkedHashMap结构
PS:
图解HashMap原理
图解LinkedHashMap原理
ConcurrentHashMap
在HashMap的基础上,ConcurrentHashMap将数据分为多个segment，默认16个，然后每次操作对一个segment加锁，避免多线程锁的几率，提高并发效率。
Hashtable 和 HashMap 的区别
- HashMap 父类为 AbstractMap，方法不同步，K，V 可为 null。
- HashTable 父类为 Dictionary，方法同步，K，V 不可为 null。
LinkedHashMap——有序的Map
- 使用Map接口的哈希表和链表实现，具有可预知的迭代顺序。此实现与HashMap的不同之处在于：LinkedHashMap维护着一个双向循环链表。此链表定义了迭代顺序，该迭代顺序通常就是存放元素的顺序。
- 如果在Map中重新存入已有的key，那么key的位置不会发生改变，只是将value值替换。
- LinkedHashMap的内部维持了一个双向链表，保存了数据的插入顺序，遍历时，先得到的数据便是先插入的
- 遍历速度比HashMap慢
TreeMap、HashMap、LinkedHashMap 的区别
-
TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序
默认是按键值升序排序，也可以 指定排序的比较器(通过构造器传入 Comparator 对象)，当用 Iterator 遍历 TreeMap 时，得到的记 录是排过序的。 -
LinkedhashMap 是 HashMap 子类，保存了记录的插入顺序
在用 iterator 遍历时，先得到的记录肯定是先插入的，LinkedhashMap可以实现输出的顺序和输入的相同LRU 算法里面使用到 LinkedHashMap，之所以用这个类而不用 LinkedList，主要是 LinkedHashMap 取值速度快，免去 LinkedList 遍历搜索过程。
网友评论