Java集合框架

昨天的时候 刚好做了个小练习关于集合

那今天就顺便先把集合框架复习了 后面因为用到java集合的地方太多了,经常需要考虑到选择合适的容器

在之后的Java8新特性流操作也为集合提供了更方便的操作方式 等后面再进行整理

容器

容器,用来容纳和管理数据

数组就是一种容器,可以放置对象或基本数据类型

优势

简单的线性序列,可以快速访问数组元素,效率高. 如果从效率和类型检查的角度讲,数组是最好的

劣势

不灵活.容量需要事先定义好,不能随着需求变化而扩容.

数组不能满足我们管理和组织数据的需求,所以需要一种更强大,容量随时可扩的容器来装载我们的对象.

这就是容器(Collection)也称之为集合

容器结构

Collection接口

集合类的基本接口

两个基本方法

1
2
boolean add(E e);
boolean remove(Object o);

Iterator接口

包含四个方法

1
2
3
4
5
6
7
8
9
10
11
12
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}

for each循环可以处理任何实现了Iterable接口的对象 任何集合都可以使用for each遍历

  • remove和next之间存在依赖性,如果调用remove之前没有调用next 将是不合法的 会抛出IllegalStateException异常

单列集合

将数据一个一个进行存储 就是单列集合

单列集合继承关系图

Queue

在队列的尾部添加元素,在队列的头部删除元素,”先进先出”

Java6 引入了双端队列(deuqe)

两种实现方式: 循环数组(实现类ArrayDeque 是一个双端队列),

​ 链表(实现类LinkedList)

循环数组比链表更高效,因此多数人优先选择循环数组 代价是循环数组是一个有界集合

进入源码查看queue接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public interface Queue<E> extends Collection<E> {

boolean add(E e);
//使用容量受限的容器时 常使用以下方法
boolean offer(E e);

//如果为空 remove会报错 但是poll不会
E remove();
//吐出去头元素
E poll();

E element();

/**
* 提取 但是不移除
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E peek();
}

优先队列(Priority queue)

元素可以按照任意的顺序插入,但会按照有序的顺序进行检索. 也就是说,无论何时调用remove,总会获得当前优先队列中最小的元素,不过优先队列并没有对元素进行排序.

优先队列使用了一个精巧且高效的数据结构,称为堆(heap)

List

List: 存储有序,可重复,”动态”数组

链表 LinkedList

  • 链表不支持快速随机访问(使用数组或者ArrayList) 如果查看链表中的第n个元素,就必须从头开始,越过n-1个元素
  • 使用链表的唯一理由就是尽可能减少在列表中间插入或者删除元素的开销

Set

Set: 存储无序,不可重复,数学中的”集合”

  • Set接口等同于Collection接口,但是add方法不允许添加重复的元素,要适当的定义集的equals方法.只要两个集包含同样的元素就认为他们是相等的. hashCode的方法的定义要保证包含相同元素的两个集会得到相同的散列码.

散列集

如果想查看某个指定的元素,却又不记得它的位置,就需要访问所有的元素,知道找到为止

有一种众所周知的数据结构,可以用于快速地查找对象,这就是散列表

散列表为每一个对象计算一个整数,成为散列码

散列表用链表数组实现 每个列表被称为桶(bucket)

想要查找表中对象的位置,就要先计算它的散列码,然后与桶的总数取余,所得到 的结果就是保存这个元素桶的索引

例如:

如果某个对象的散列码76268 并且有128个桶 那么这个对象应该保存在第108号桶中(因为76268%128的余数是108)

有时候会遇到桶已经被填充的情况,这种现象被称为散列冲突(hash collision)

Java8中 桶满的时候 会从链表变为平衡二叉树

如果知道最终会有多少元素插入到散列表中,就可以设置桶数,通常,将桶数设置为预计元素个数的75%~150%

标准类库使用的桶数是2的幂,默认是16

如果散列表太满,就需要再散列

装填因子可以决定何时对散列表进行再散列,0.75就是表示表中已经装满了75%以上,新表的桶数是原来的两倍

树集

TreeSet类与散列集十分相似,不过它比散列集有所改进.树集是一个有序集合,

在集合进行遍历的时候 自动按排序的顺序呈现

实现用的是红黑树

要使用树集 必须实现Comparable接口

写到这里 昨晚的名字 按字母排序可以直接丢进去Set接口

双列集合

基于Key和Value的结构存储数据

双列集合继承关系图

  • 由于映射包含键值对 所以需要用put 插入 用get 读取

  • Java类库为映射提供了两个通用的实现: HashMap和TreeMap 这两个类都实现了Map接口

  • 散列映射对键进行散列,树映射根据键的顺序将元素组织成为一个搜索树.散列或比较函数只应用于键.与键关联的值不进行散列或比较.

  • Null 返回值可能不方便 有时对应没有出现在映射中的键,可以使用一个好的默认值. 然后使用getOrDefault方法

    1
    int score = scores.getOrDefault(id,0)
  • 要迭代处理映射中的键和值,最容易的方法是使用forEach方法.可以提供一个接收键和值的lambda表达式.映射中的每一项会依序调用这个表达式

    1
    2
    3
    scores.forEach((k,v) ->
    System.out.println("key="+k+",value="+v)
    );

映射视图

集合框架不认为映射本身是一个集合.(其他数据结构框架认为映射是一个键/值对集合,或者是按键索引的值集合)

不过,可以得到映射的视图(View)

弱散列映射

如果有一个值,它对应的键已经不在程序中的任何地方使用,将会出现什么情况呢?假定对某个键的最后一个引用已经消失,那么不再有任何途径可以引用这个值的对象了.但是,由于程序中的任何部分不会再有这个键,所以,无法从映射中删除这个键值对.为什么垃圾回收器不能删除它呢?删除无用的对象不就是垃圾回收器的工作吗?

垃圾回收器会跟踪活动的对象.只要映射对象是活动的,其中所有的桶也是活动的,他们不能被回收,因此,需要由程序负责从长期存活的映射表中删除那些无用的值.或者可以使用 WeakHashMap

当对键的唯一引用来自于散列表映射条目时候,这个数据结构将与垃圾回收器协同工作一起删除键值对

链接散列集与映射

LinkedHashSet和LinkedHashMap 类会记住插入元素项的顺序.这样就可以避免散列表中的项看起来顺序是随机的. 在表中插入元素项的时候,就会并入到双向链表中.

资料参考: Java核心技术 (总感觉这本书讲集合框架好像不是很有逻辑, 边看边写笔记做完还是要再整理一遍)