luckydog

V1

2022/03/31阅读:35主题:默认主题

Collection集合

Collection集合(单列集合)

  • 集合是一种容器
  • 和数组容器的区别
  • 1.数组长度固定,集合长度可变
  • 2.数组存储同一类型元素,并且可以存储基本类型和对象;集合只能存储对象,而且可以存储不同类型。

List(接口)

存取有序,带索引,重复
遍历方式:1.普通for 2.迭代器 3.for each

ArrayList(实现类)

线程不安全
Arraylist的底层是用动态object数组来实现的
初始化一个arraylist集合还没有添加元素时,其实它是个空数组,只有当我们添加第一个元素时,内部会调用calculateCapacity方法并返回最小容量10,也就是说arraylist初始化容量为10。 当最小容量大于当前数组的长度时,便开始可以扩容了,arraylist扩容的真正计算是在一个grow()里面,新数组大小是旧数组的1.5倍,如果扩容后的新数组大小还是小于最小容量,那新数组的大小就是最小容量的大小,后面会调用一个Arrays.copyof方法,这个方法是真正实现扩容的步骤。

LinkedList(实现类)

implements List, Deque
LinkedList底层是双向循环链表(查询慢,增删快)

  • 实现了List接口,Deque接口(因此可以被当作双端队列,队列,栈来使用)
  • 根据index查找的时候会先判断index和size/2的关系,决定从head向前还是向后查找

Vector(实现类)

线程安全 同步 Vector和ArrayList的实现方式可以看出非常像,既然Vector类建议尽量少的使用,还是最好不要用了,通过上面的源码发现,每个方法中都添加了synchronized的关键字来保证同步,所以它是线程安全的,但正是这些方法的同步,让它的效率大大的降低了,比ArrayList的效率要慢.

Set(接口)

不允许重复元素,没有索引
通过重写hashcode 和 equals方法实现不重复(调用hashmap的那几个)
遍历方式:1.迭代器 2.for each

HashSet(实现类)

HashSet的底层通过HashMap实现的
HashMap在1.7之前使用的是数组+链表实现,在1.8+使用的数组+链表+红黑树实现。HashSet的方法也是借助HashMap的方法来实现的

LinkedHashSet extends HashSet 所有构造方法都是super调用父类HashSet的构造方法

private transient HashMap<E,Object> map;
public HashSet() {
    map = new HashMap<>();
}
//这个是linkedHashSet调用的
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

TreeSet(实现类)

(implements NavigableSet extends SortedSet)

  • comparator接口实现保证元素不重复(SortedSet中的)
  • TreeSet的底层是用TreeMap实现
  • 在构造方法中会创建一个TreeMap实例,用于存放元素,另外TreeSet是有序的,也提供了制定比较器的构造函数,如果没有提供比较器,则采用key的自然顺序进行比较大小,如果指定的比较器,则采用指定的比较器,进行key值大小的比较。

Queue队列(接口)

Deque extends Queue
Deque(Double ended Queue)双端队列(可以当作栈使用) LinkedList implements Deuqe

ArrayDeque (实现类)

implements Deque

  • 环形数组
  • 使用了可变数组,所以没有容量上的限制
  • 可以作为栈来使用,效率高于Stack;也可以作为队列来使用,效率高于LinkedList。需要注意的是,ArrayDeque不支持null值。

PriorityQueue(实现类)

PriorityQueue实现了Queue接口
不允许放入null元素

  • 通过堆实现,具体说是通过完全二叉树(complete binary tree)实现的小顶堆(任意一个非叶子节点的权值,都不大于其左右子节点的权值),也就意味着可以通过数组来作为PriorityQueue的底层实现

分类:

后端

标签:

Java

作者介绍

luckydog
V1