Collection接口&& Map相关子类

2020-05-19  本文已影响0人  卡路fly

继承关系

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接口部分函数原型

HashSet

HashSet 是基于 HashMap 来实现的。
一次 HashSet 的存取相当于 HashMap 的一次存取，相当于只看中 HashMap 的 Key，不需 要 Value 部分（Value 使用一个 static final 的Object 对象标识）

HashSet 判断对象是否存在集合中

1 . 调用obj.hashCode()，得到对应的hashcode值。

  1. 如果集合中没有存储这个 hashcode 对应的对象，则直接添加。
    hashcode
  2. 如果集合中已经存储了这个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() 如果队里为空，则一直等待(阻塞)

SynchronousQueue

ArrayBlockingQueue

LinkedBlockingQueue

ArrayBlockingQueue 和 LinkedBlockingQueue 的区别

  1. 队列中锁的实现不同
    ArrayBlockingQueue实现的队列中的锁是没有分离的，即生产和消费用的是同一个锁;。
    LinkedBlockingQueue实现的队列中的锁是分离的，即生产用的是 putLock，消费是takeLock

  2. 在生产或消费时操作不同
    ArrayBlockingQueue实现的队列中在生产和消费的时候，是直接将枚举对象插入或移除的；
    LinkedBlockingQueue实现的队列中在生产和消费的时候，需要把枚举对象转换为node<E>进行插入或移除，会影响性能。

  3. 队列大小初始化方式不同
    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 本质是数组加链表。

HashMap put：

  1. 首先根据key的hashCode找到对应数组的位置
  2. 然后遍历该位置的链表，查找key是否已经存在
  3. 如果key已经存在，则直接更新value,并将旧的value作为函数返回
  4. 如果key不存在，则通过头插法，将新的键值对放入当前链表的第一个位置

PS: (null key 总是放入数组的第 0 个位置，因为 null 的哈希码为0)

HashMap get：

  1. 首先根据key的hashCode找到对应数组的位置
  2. 然后遍历该位置的链表，查找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新元素流程:

  1. 判断该链p是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则执行2
  2. 链为链表遍历p，判断链表长度是否大于8，如果大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作
    红黑树
HashMap结构 LinkedHashMap结构

PS:

图解HashMap原理

图解LinkedHashMap原理

ConcurrentHashMap

在HashMap的基础上,ConcurrentHashMap将数据分为多个segment，默认16个，然后每次操作对一个segment加锁，避免多线程锁的几率，提高并发效率。

Hashtable 和 HashMap 的区别

LinkedHashMap——有序的Map

TreeMap、HashMap、LinkedHashMap 的区别

上一篇下一篇

猜你喜欢

热点阅读