学习总结(2022.04.25-2022.04.30)
数组和链表
数组添加的时间复杂度: o(n)
数组删除的时间复杂度: o(n)
数组按下标查找的时间复杂度: o(1)
无序数组按值查找的时间复杂度: o(n)
有序数组按值查找的时间复杂度: o(logn)
链表的添加时间复杂度: o(1)
链表的删除时间复杂度: o(1)
链表的查找时间复杂度: o(n)
泛型
泛型,就是参数化类型,在不确定传入的类型时,可以先设置一个参数来代指(类似于形参)。
基本语法如下:
1 | |
可以定义多个泛型,但是最好不超过两个,如果需要两个以上的泛型,说明设计有问题。
在泛型类上定义的泛型,作用域仅在类名和类体内,即使是子类也不能继承。
泛型通配:?为泛型通配符,没有明确,就是Object以及任意类;? extends E为向下限定,只能是E及其子类;? super E为向上限定,只能是E及其父类。
泛型擦除:java中的泛型并不是真正的泛型,在编译之后,泛型会变成Object以及类型强转,泛型只是防止程序员对类型的随意转换。
红黑树
红黑树是一个特殊的二叉搜索树,每个节点有红色和黑色两种颜色。
其中根节点和叶子(nil,叶子节点下的空节点)必须是黑色;父子节点不能都是红色节点;从叶子到根节点的路径上,黑色节点的数目是一样的。(黑高平衡)
红黑树通过旋转(类似于二叉搜索树)和分裂(类似于B树,向上和向下)保证黑高平衡和无连续红色节点。
集合类Collection
Collection是Collection集合体系的顶级接口,定义为一个数据容器。
Collection的子实现一些存储元素有序,一些存储元素无序;一些允许存储重复元素,一些不允许存储重复元素;一些允许存储null,一些不允许存储null。
API:
1 | |
并发修改异常:collection的一些子实现是线程不安全的,在使用Iterator遍历时会产生线程安全问题。所以一些子实现会维护一个标记,记录修改次数,每次修改次数都会增加。
Iterator对象遍历前,都会检查修改次数是否与原集合类一致,如果不一致,就会认为数据被其他线程修改,从而抛出并发修改异常。
但是即使在单线程情况下,如果在遍历过程中直接使用集合类的修改方法,也会抛出并发修改异常。所以在Iterator对象遍历时不要修改数据。
List
List是Collection的子接口,描述的数据结构是线性表。
List有序,允许存储重复元素,允许存储null。
API:
1 | |
ArrayList
ArrayList是List的子实现,描述的数据结构是线性表。
其底层结构是数组,数组默认长度为10,扩容倍数为1.5倍。
ArrayList存储结构有序,允许存储重复元素,允许存储null。
ArrayList线程不安全。
构造方法:
1 | |
API:
1 | |
Vector
Vector是List的子类。描述的数据结构是线性表。
其底层结构是数组,数组默认长度为10,扩容倍数为2倍。
Vector存储结构有序,允许存储重复元素,允许存储null。
Vector线程安全。
LinkedList
LinkedList是List的子实现,也是Deque的子实现。描述的数据结构是线性表/队列/双端队列/栈
其底层是双向链表。
LinkedList存储结构有序,允许存储重复元素,允许存储null。
LinkedList线程不安全。
构造方法:
1 | |
API:
1 | |
Queue
Queue是Collection的子接口,描述的数据结构是队列。
Queue存储元素有序,允许存储重复元素,不允许存储null。(因为Queue的poll方法返回null表示队列无元素,为避免混淆,所以不允许存储null)
API:
1 | |
Deque
Deque是Queue接口的一个子接口,描述的数据结构是队列/双端队列/栈。
Deque存储元素有序,允许存储重复元素,不允许存储null。
ArrayDeque
ArrayDeque是Deque接口的子实现。描述的数据结构是队列/双端队列/栈。
其底层结构是循环数组,数组默认长度为16,扩容倍数为2倍。
ArrayDeque存储元素有序,允许存储重复元素,不允许存储null。
ArrayDeque线程不安全。
BlockingQueue
BlockingQueue是Queue的一个子接口,描述的数据结构是阻塞队列。
阻塞队列:大小有限的队列,常用于线程池。队满时,添加线程等待;队空时,删除线程等待。
Set
Set接口是Collection的一个子接口,描述的数据结构是集合。
Set的子实现一些有序,一些无序;都不允许存储重复元素;一些允许存储null,一些不允许存储null。
HashSet
HashSet是Set接口的子实现。
其底层结构是HashMap,HashSet添加的对象其实是HashMap的key值。
HashSet存储元素无序;不允许存储重复元素;允许存储null。
HashSet线程不安全。
构造方法:
1 | |
LinkedHashSet
LinkedHashSet是HashSet的子类.
其底层结构是LinkedHashMap。
LinkedHashSet存储元素有序;不允许存储重复元素;允许存储null。
LinkedHashSet线程不安全。
TreeSet
TreeSet是Set接口的子实现。
其底层结构是TreeMap。
TreeSet存储元素有序;不允许存储重复元素;不允许存储null。
TreeSet线程不安全。
Map
Map是Map集合体系的顶级接口,存储key-value数据。
Map的子实现一些存储元素有序,一些存储元素无序;都不允许存储重复数据;一些允许存储null,一些不允许存储null(仅仅指key)
API:
1 | |
HashMap
HashMap是Map接口的具体子实现,底层结构是数组+链表+红黑树。数组的默认初始容量为16,扩容机制为2倍,默认的加载因子为0.75。 (加载因子用来控制HashMap的饱和度,默认阈值为16 * 0.75 = 12,如果超过12对键值对,HashMap扩容)
HashMap存储元素无序;不允许存储重复的key;允许存储null作为key。
HashMap线程不安全。
HashMap中键值对的Hash值计算:(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
如果一个新加入的key-value对,它的key值与已经存在的key值满足hash值相等,而且也满足值相等(==或equals),说明key值重复,此时会将新value值覆盖掉旧value值,并将旧value值返回出来。
HashMap在某一链表长度大于8时进行以下其中一种操作:当数组长度小于64时,会扩容数组并进行再散列;当数组长度大于等于64时,则会将链表转化为红黑树。
HashMap在删除节点时,如果删除的是红黑树上的节点,且该节点是红黑树的根节点/根节点的左右节点/根节点的左节点的左节点,此时会认为红黑树上节点过少,从而使红黑树转化为链表;HashMap在扩容进行再散列时,红黑树会被拆分,如果拆分后红黑树中的节点小于6个,红黑树转化为链表。
构造方法:
1 | |
HashMap没有额外的API,基本继承了Map接口的API。
LinkedHashMap
LinkedHashMap是HashMap的一个子类,基本上完全复用了HashMap的底层结构和方法。
LinkedHashMap额外维护了一个双向链表保证迭代顺序。
LinkedHashMap存储元素有序;不允许存储重复的key;允许存储null作为key。
LinkedHashMap线程不安全。
TreeMap
TreeMap是Map接口的子实现,描述的数据结构是红黑树。
其底层结构是链表。
TreeMap存储的元素有序;不允许存储重复的key;不允许存储null作为key。
因为TreeMap底层的数据结构是红黑树,所以key值需要比较大小,此时有两种实现比较的方式:存储的key值自身可以实现自然排序;TreeMap提供比较器。
构造方法:
1 | |
API:
1 | |
HashTable
HashTable是Map的子实现。
其底层结构是数组+链表。数组的初始容量为11,扩容倍数为2倍+1。
HashTable存储的元素无序;不允许存储重复的key;不允许存储null作为key,也不允许存储null作为value。
HashTable线程安全。
Stream
Stream流是jdk1.8时提供的一种处理集合数据的方法。它提供一种内部迭代的方式,允许我们用多个中间操作来串联成一个管道,如同流式风格,避免了我们在对数据集合进行操作时带来的代码冗长问题。
一个Stream流包括三个模块:
- 一个数据源,创建流。
- 多个中间操作,形成流。
- 一个终止操作,执行流,生成结果。
创建流:
1 | |
形成流:
1 | |
执行流:
1 | |