Ykuri98
文章46
标签14
分类1
学习总结(2022.04.25-2022.04.30)

学习总结(2022.04.25-2022.04.30)

数组和链表

数组添加的时间复杂度: o(n)

数组删除的时间复杂度: o(n)

数组按下标查找的时间复杂度: o(1)

无序数组按值查找的时间复杂度: o(n)

有序数组按值查找的时间复杂度: o(logn)

链表的添加时间复杂度: o(1)

链表的删除时间复杂度: o(1)

链表的查找时间复杂度: o(n)

泛型

泛型,就是参数化类型,在不确定传入的类型时,可以先设置一个参数来代指(类似于形参)。

基本语法如下:

1
2
3
class 类名<泛型类型1,…>
interface 接口名<泛型类型1…>
public <泛型类型> 返回类型 方法名(泛型类型 .)

可以定义多个泛型,但是最好不超过两个,如果需要两个以上的泛型,说明设计有问题。

在泛型类上定义的泛型,作用域仅在类名和类体内,即使是子类也不能继承。

泛型通配:?为泛型通配符,没有明确,就是Object以及任意类;? extends E为向下限定,只能是E及其子类;? super E为向上限定,只能是E及其父类。

泛型擦除:java中的泛型并不是真正的泛型,在编译之后,泛型会变成Object以及类型强转,泛型只是防止程序员对类型的随意转换。

红黑树

红黑树是一个特殊的二叉搜索树,每个节点有红色和黑色两种颜色。

其中根节点和叶子(nil,叶子节点下的空节点)必须是黑色;父子节点不能都是红色节点;从叶子到根节点的路径上,黑色节点的数目是一样的。(黑高平衡)

红黑树通过旋转(类似于二叉搜索树)和分裂(类似于B树,向上和向下)保证黑高平衡和无连续红色节点。

集合类Collection

Collection是Collection集合体系的顶级接口,定义为一个数据容器。

Collection的子实现一些存储元素有序,一些存储元素无序;一些允许存储重复元素,一些不允许存储重复元素;一些允许存储null,一些不允许存储null。

API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// ------------------------------增删改查相关的api------------------------------
// boolean add(E e)
// 确保此 collection 包含指定的元素(可选操作)。
// boolean addAll(Collection<? extends E> c)
// 将指定 collection 中的所有元素都添加到此 collection 中(可选操作)。
// boolean contains(Object o)
// 如果此 collection 包含指定的元素,则返回 true。
// boolean containsAll(Collection<?> c)
// 如果此 collection 包含指定 collection 中的所有元素,则返回 true。
// boolean remove(Object o)
// 从此 collection 中移除指定元素的单个实例,如果存在的话(可选操作)。
// boolean removeAll(Collection<?> c)
// 移除此 collection 中那些也包含在指定 collection 中的所有元素(可选操作)。
// boolean retainAll(Collection<?> c)
// 仅保留此 collection 中那些也包含在指定 collection 的元素(可选操作)。



// ---------------------------------------集合类都具有的辅助方法-----------------
// void clear()
// 移除此 collection 中的所有元素(可选操作)。
// boolean equals(Object o)
// 比较此 collection 与指定对象是否相等。
// int hashCode()
// 返回此 collection 的哈希码值。
// boolean isEmpty()
// 如果此 collection 不包含元素,则返回 true。
// int size()
// 返回此 collection 中的元素数。



// ------------------------------------------特殊方法--------------------------
// Object[] toArray()
// 返回包含此 collection 中所有元素的数组。
// <T> T[] toArray(T[] a)
// 返回包含此 collection 中所有元素的数组;返回数组的运行时类型与指定数组的运行时类型相同。
// 只有数组类型与存储的数据类型相匹配,才能正常运行;如果传入的数组够长,那么返回的数组和传入的数组是一个数组,反之则不是;如果传入的数组过长,那么空位位置会置为null。

// Iterator<E> iterator()
// 返回在此 collection 的元素上进行迭代的迭代器。

// Iterator类型的方法:
// hasNext(): 向后还有没有元素可以遍历
// next(): 向后遍历
// remove(): 删除刚刚遍历过的元素;

// 注意:java中的增强for循环就是由iterator方法实现的(数组不一样,数组的增强for循环在编译中是变成普通的fori循环)

并发修改异常:collection的一些子实现是线程不安全的,在使用Iterator遍历时会产生线程安全问题。所以一些子实现会维护一个标记,记录修改次数,每次修改次数都会增加。

Iterator对象遍历前,都会检查修改次数是否与原集合类一致,如果不一致,就会认为数据被其他线程修改,从而抛出并发修改异常。

但是即使在单线程情况下,如果在遍历过程中直接使用集合类的修改方法,也会抛出并发修改异常。所以在Iterator对象遍历时不要修改数据。

List

List是Collection的子接口,描述的数据结构是线性表。

List有序,允许存储重复元素,允许存储null。

API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//        void add(int index, E element)
// 在列表的指定位置插入指定元素(可选操作)。
// boolean addAll(int index, Collection<? extends E> c)
// 将指定 collection 中的所有元素都插入到列表中的指定位置(可选操作)。
// E get(int index)
// 返回列表中指定位置的元素。
// int indexOf(Object o)
// 返回此列表中第一次出现的指定元素的索引;如果此列表不包含该元素,则返回 -1。
// int lastIndexOf(Object o)
// 返回此列表中最后出现的指定元素的索引;如果列表不包含此元素,则返回 -1。
// E remove(int index)
// 移除列表中指定位置的元素(可选操作)。
// E set(int index, E element)
// 用指定元素替换列表中指定位置的元素(可选操作)。

// ListIterator<E> listIterator()
// 返回此列表元素的列表迭代器(按适当顺序)。
// ListIterator<E> listIterator(int index)
// 返回列表中元素的列表迭代器(按适当顺序),从列表的指定位置开始。

// ListIterator类型的方法:
// hasNext(): 向后还有没有元素可以遍历
// next(): 向后遍历
// remove(): 删除刚刚遍历过的元素;
// hasPrevious(): 向前是否可以遍历
// previous(): 向前遍历

// List<E> subList(int fromIndex, int toIndex)
// 返回列表中指定的 fromIndex(包括 )和 toIndex(不包括)之间的部分视图。
// subList并不是从源集合类中复制了数据,而是维护了一些标记指向源数据,在subList上操作,本质还是在操作源数据。
// 所以不建议在使用subList中修改源数据,可能抛出并发修改异常。

ArrayList

ArrayList是List的子实现,描述的数据结构是线性表。

其底层结构是数组,数组默认长度为10,扩容倍数为1.5倍。

ArrayList存储结构有序,允许存储重复元素,允许存储null。

ArrayList线程不安全。

构造方法:

1
2
3
4
5
6
// 		  ArrayList() 
// 构造一个初始容量为 10 的空列表。
// ArrayList(Collection<? extends E> c)
// 构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
// ArrayList(int initialCapacity)
// 构造一个具有指定初始容量的空列表。

API:

1
2
3
4
5
6
//        Object clone()
// 返回此 ArrayList 实例的浅表副本。
// void ensureCapacity(int minCapacity)
// 如有必要,增加此 ArrayList 实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数。
// void trimToSize()
// 将此 ArrayList 实例的容量调整为列表的当前大小。

Vector

Vector是List的子类。描述的数据结构是线性表。

其底层结构是数组,数组默认长度为10,扩容倍数为2倍。

Vector存储结构有序,允许存储重复元素,允许存储null。

Vector线程安全。

LinkedList

LinkedList是List的子实现,也是Deque的子实现。描述的数据结构是线性表/队列/双端队列/栈

其底层是双向链表。

LinkedList存储结构有序,允许存储重复元素,允许存储null。

LinkedList线程不安全。

构造方法:

1
2
3
4
//		  LinkedList() 
// 构造一个空列表。
// LinkedList(Collection<? extends E> c)
// 构造一个包含指定 collection 中的元素的列表,这些元素按其 collection 的迭代器返回的顺序排列。

API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//        队列API
// boolean offer(E e)
// 将指定元素添加到此列表的末尾(最后一个元素)。
// E poll()
// 获取并移除此列表的头(第一个元素)
// E peek()
// 获取但不移除此列表的头(第一个元素)。

// 双端队列API
// boolean offerFirst(E e)
// 在此列表的开头插入指定的元素。
// boolean offerLast(E e)
// 在此列表末尾插入指定的元素。
// E peekFirst()
// 获取但不移除此列表的第一个元素;如果此列表为空,则返回 null。
// E peekLast()
// 获取但不移除此列表的最后一个元素;如果此列表为空,则返回 null。
// E pollFirst()
// 获取并移除此列表的第一个元素;如果此列表为空,则返回 null。
// E pollLast()
// 获取并移除此列表的最后一个元素;如果此列表为空,则返回 null。

// 栈API
// E pop()
// 从此列表所表示的堆栈处弹出一个元素。
// void push(E e)
// 将元素推入此列表所表示的堆栈。

Queue

Queue是Collection的子接口,描述的数据结构是队列。

Queue存储元素有序,允许存储重复元素,不允许存储null。(因为Queue的poll方法返回null表示队列无元素,为避免混淆,所以不允许存储null)

API:

1
2
3
4
5
6
7
8
9
10
11
12
//		  boolean offer(E e)
// 在队列中添加数据
// E peek()
// 查看队头元素
// E poll()
// 出队头
// boolean add(E e)
// 添加数据
// E element()
// 查看头元素
// E remove()
// 删除头元素

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
2
3
4
5
6
7
8
//			HashSet() 
// 构造一个新的空 set,其底层 HashMap 实例的默认初始容量是 16,加载因子是 0.75。
// HashSet(Collection<? extends E> c)
// 构造一个包含指定 collection 中的元素的新 set。
// HashSet(int initialCapacity)
// 构造一个新的空 set,其底层 HashMap 实例具有指定的初始容量和默认的加载因子(0.75)。
// HashSet(int initialCapacity, float loadFactor)
// 构造一个新的空 set,其底层 HashMap 实例具有指定的初始容量和指定的加载因子。
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
        // -----------------------增删改查的api-------------------------
// V put(K key, V value)
// 将指定的值与此映射中的指定键关联(可选操作)。
// void putAll(Map<? extends K,? extends V> m)
// 从指定映射中将所有映射关系复制到此映射中(可选操作)。
// V remove(Object key)
// 如果存在一个键的映射关系,则将其从此映射中移除(可选操作)。
// V get(Object key)
// 返回指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null。
// boolean containsKey(Object key)
// 如果此映射包含指定键的映射关系,则返回 true。
// boolean containsValue(Object value)
// 如果此映射将一个或多个键映射到指定值,则返回 true。

// -----------------------集合类都有的api-------------------------
// void clear()
// 从此映射中移除所有映射关系(可选操作)。
// boolean equals(Object o)
// 比较指定的对象与此映射是否相等。
// int hashCode()
// 返回此映射的哈希码值。
// boolean isEmpty()
// 如果此映射未包含键-值映射关系,则返回 true。
// int size()
// 返回此映射中的键-值映射关系数。

// -----------------------视图方法-------------------------
// Set<K> keySet()
// 返回此映射中包含的键的 Set 视图。
// Collection<V> values()
// 返回此映射中包含的值的 Collection 视图。
// Set<Map.Entry<K,V>> entrySet()
// 返回此映射中包含的映射关系的 Set 视图。

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
2
3
4
5
6
7
8
//		    HashMap() 
// 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
// HashMap(int initialCapacity)
// 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
// HashMap(int initialCapacity, float loadFactor)
// 构造一个带指定初始容量和加载因子的空 HashMap。
// HashMap(Map<? extends K,? extends V> m)
// 构造一个映射关系与指定 Map 相同的新 HashMap。

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
2
3
4
5
6
7
8
//			TreeMap() 
// 使用键的自然顺序构造一个新的、空的树映射。
// TreeMap(Comparator<? super K> comparator)
// 构造一个新的、空的树映射,该映射根据给定比较器进行排序。
// TreeMap(Map<? extends K,? extends V> m)
// 构造一个与给定映射具有相同映射关系的新的树映射,该映射根据其键的自然顺序 进行排序。
// TreeMap(SortedMap<K,? extends V> m)
// 构造一个与指定有序映射具有相同映射关系和相同排序顺序的新的树映射。

API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// ------------------------TreeMap定义大小操作相关的api------------------------
// Map.Entry<K,V> ceilingEntry(K key)
// 大于等于给定key的最小键值对
// K ceilingKey(K key)
// 大于等于给定key的最小key
// Map.Entry<K,V> floorEntry(K key)
// 小于等于key的最大的键值对
// K floorKey(K key)
// 小于等于key最大的key
// Map.Entry<K,V> higherEntry(K key)
// 大于给定key的最小键值对
// K higherKey(K key)
// 大于给定key的最小key
// Map.Entry<K,V> lowerEntry(K key)
// 小于key的最大的键值对
// K lowerKey(K key)
// 小于key最大的key

// Map.Entry<K,V> firstEntry()
// 返回最小的键值对
// K firstKey()
// 返回最小的key
// Map.Entry<K,V> lastEntry()
// 返回最大的键值对
// K lastKey()
// 返回最大的key

// Map.Entry<K,V> pollFirstEntry()
// 删除最小的键值对
// Map.Entry<K,V> pollLastEntry()
// 删除最大的键值对


// ---------------------视图方法-----------------------------
// NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
// 返回此映射的部分视图,其键的范围从 fromKey 到 toKey。
// SortedMap<K,V> subMap(K fromKey, K toKey)
// 返回此映射的部分视图,其键值的范围从 fromKey(包括)到 toKey(不包括)。
// SortedMap<K,V> tailMap(K fromKey)
// 返回此映射的部分视图,其键大于等于 fromKey。
// NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
// 返回此映射的部分视图,其键大于(或等于,如果 inclusive 为 true)fromKey。
// SortedMap<K,V> headMap(K toKey)
// 返回此映射的部分视图,其键值严格小于 toKey。
// NavigableMap<K,V> headMap(K toKey, boolean inclusive)
// 返回此映射的部分视图,其键小于(或等于,如果 inclusive 为 true)toKey。

HashTable

HashTable是Map的子实现。

其底层结构是数组+链表。数组的初始容量为11,扩容倍数为2倍+1。

HashTable存储的元素无序;不允许存储重复的key;不允许存储null作为key,也不允许存储null作为value。

HashTable线程安全。

Stream

Stream流是jdk1.8时提供的一种处理集合数据的方法。它提供一种内部迭代的方式,允许我们用多个中间操作来串联成一个管道,如同流式风格,避免了我们在对数据集合进行操作时带来的代码冗长问题。

一个Stream流包括三个模块:

  1. 一个数据源,创建流。
  2. 多个中间操作,形成流。
  3. 一个终止操作,执行流,生成结果。

创建流:

1
2
Collection collection = new ArrayList();
Stream stream = collection.stream();

形成流:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
        List<Person> personList = StudentList.personList;

// filter:用于通过设置条件过滤元素
// 获取所有北京地区的同学
List<Person> collect = personList.stream()
.filter(d -> d.getAddress().equals(Person.Address.BJ))
.collect(Collectors.toList());

// distinct:去除重复元素
// 去除重复的同学
List<Person> collect = personList.stream()
.distinct()
.collect(Collectors.toList());

// limit:获取指定数量的元素
// 获取三个年龄大于22岁的同学
List<Person> collect = personList.stream()
.filter(d -> d.getAge() > 22)
.limit(3)
.collect(Collectors.toList());

// skip:跳过前n个元素
// 获取年龄大于22岁的同学并跳过第一个
List<Person> collect2 = personList.stream()
.filter(d -> d.getAge() > 22)
.skip(1)
.collect(Collectors.toList());

// map:映射每个元素到对应的结果
// 获取所有学生姓名
List<String> collect = personList.stream()
.map(a -> a.getName())
.collect(Collectors.toList());

// sorted:对流进行排序
// 对高于180的同学根据身高进行排序
List<Person> collect = personList.stream()
.filter(a -> a.getHeight() > 180)
.sorted(Comparator.comparing(Person::getHeight))
.collect(Collectors.toList());

执行流:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// anyMatch:检查是否匹配一个元素
// 判断是否存在北京的同学
boolean b1 = personList.stream()
.anyMatch(a -> {
return a.getAddress() == Person.Address.BJ;
});

// allMatch:检查是否匹配所有元素
// 判断是否都是北京的同学
boolean b1 = personList.stream()
.allMatch(a -> {
return a.getAddress() == Person.Address.BJ;
});

// nonematch:检查是否没有匹配元素
// 判断是否不存在深圳的同学
boolean b1 = personList.stream()
.noneMatch(a -> {
return a.getAddress() == Person.Address.SZ;
});

// findAny:返回任意元素(默认第一个)
// Optional类作为一个容器代表一个值存在或不存在,方法如下
// isPresent(): 如果 Optional包含值返回true, 否则返回false
// ifPresent(代码块): 会将Optional包含的值, 传给指定的代码块
// get(): 如果Optional包含值, 返回包含的值, 否则抛出异常
// orElse(默认值): 如果Optional包含值, 返回包含的值, 否则返回默认值
// 返回任意一个同学
Optional<Person> any = personList.stream()
.findAny();

// findFirst:返回第一个元素
// 获得年龄最小的同学
Optional<Person> first = personList.stream()
.sorted(Comparator.comparing(Person::getAge))
.findFirst();

// forEach:遍历输出元素
// 遍历列表,输出学生姓名
personList.stream()
.sorted(Comparator.comparing(Person::getAge))
.forEach(a -> System.out.println(a.getName()));

// count:返回元素数量
// 北京同学的数量
long count = personList.stream()
.filter(a -> a.getAddress() == Person.Address.BJ)
.count();

// reduce:计算元素
// reduce有双参方法,第一个元素为identity,为计算的初始值
// 班级同学年龄总和
Optional<Integer> reduce1 = personList.stream()
.map(Person::getAge)
.reduce((a, b) -> {
return a + b;
});

// collect:收集结果
// 收集结果可以放进List、Map、Set、Collection中
// 获取所有学生姓名,放进List中
List<String> collect = personList.stream()
.map(a -> a.getName())
.collect(Collectors.toList());
本文作者:Ykuri98
本文链接:https://ykuri98.github.io/2022/04/30/%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93%EF%BC%882022-04-25-2022-04-30%EF%BC%89/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
×