Java集合学习笔记
Java集合
1.什么是集合
1.1 概念
对象的容器,定义了对多个对象进行操作的常用方法。可以实现数组的功能。
1.2 和数组区别:
- 数组长度固定,集合长度不固定
- 数组可以存储基本类型和引用类型,集合只能引用类型(通过装箱操作将基本类型转换为引用类型)
1.3 位置
java.util.*
2. Collection体系集合
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PZYOwZjt-1604324784310)(C:/Users/CHENLH/AppData/Roaming/Typora/typora-user-images/image-20200811215607411.png)]
2.1 Collection接口
根接口,代表一组对象,称为集合
2.1.1 方法摘要
Modifier and Type | Method and Description |
---|---|
boolean |
add(E e) 确保此集合包含指定的元素(可选操作)。 |
boolean |
addAll(Collection<? extends E> c) 将指定集合中的所有元素添加到此集合(可选操作)。 |
void |
clear() 从此集合中删除所有元素(可选操作)。 |
boolean |
contains(Object o) 如果此集合包含指定的元素,则返回 true 。 |
boolean |
containsAll(Collection<?> c) 如果此集合包含指定 集合 中的所有元素,则返回true。 |
boolean |
equals(Object o) 将指定的对象与此集合进行比较以获得相等性。 |
int |
hashCode() 返回此集合的哈希码值。 |
boolean |
isEmpty() 如果此集合不包含元素,则返回 true 。 |
Iterator<E> |
iterator() 返回此集合中的元素的迭代器。 |
default Stream<E> |
parallelStream() 返回可能并行的 Stream 与此集合作为其来源。 |
boolean |
remove(Object o) 从该集合中删除指定元素的单个实例(如果存在)(可选操作)。 |
boolean |
removeAll(Collection<?> c) 删除指定集合中包含的所有此集合的元素(可选操作)。 |
default boolean |
removeIf(Predicate<? super E> filter) 删除满足给定谓词的此集合的所有元素。 |
boolean |
retainAll(Collection<?> c) 仅保留此集合中包含在指定集合中的元素(可选操作)。 |
int |
size() 返回此集合中的元素数。 |
default Spliterator<E> |
spliterator() 创建一个Spliterator 在这个集合中的元素。 |
default Stream<E> |
stream() 返回以此集合作为源的顺序 Stream 。 |
Object[] |
toArray() 返回一个包含此集合中所有元素的数组。 |
<T> T[] |
toArray(T[] a) 返回包含此集合中所有元素的数组;返回的数组的运行时类型是指定数组的运行时类型。 |
2.1.2 Iterator迭代器
- hasNext();有没有下一个元素
- next();获取下一个元素
- remove();删除当前元素
在迭代器中不能使用Collection自带的remove方法。第一次调用Iterator的next()方法时,它返回序列的第一个元素。
2.2 List接口
2.2.1 特点
- 有序
- 有下标
- 元素可重复
2.2.2 方法摘要
Modifier and Type | Method and Description |
---|---|
void |
add(String item) 将指定的项目添加到滚动列表的末尾。 |
void |
add(String item, int index) 将指定的项目添加到由索引指示的位置的滚动列表中。 |
void |
addActionListener(ActionListener l) 添加指定的动作侦听器以从此列表接收动作事件。 |
void |
addItem(String item) 已弃用换成add(String) 。 |
void |
addItem(String item, int index) 已弃用换成add(String, int) 。 |
void |
addItemListener(ItemListener l) 添加指定的项目侦听器以从该列表接收项目事件。 |
void |
addNotify() 创建列表的对等体。 |
boolean |
allowsMultipleSelections() 已弃用从JDK 1.1版开始,由isMultipleMode() 。 |
void |
clear() 已弃用截至JDK 1.1版,由removeAll() 。 |
int |
countItems() 已弃用从JDK 1.1版开始,替换为getItemCount() 。 |
void |
delItem(int position) 已弃用替换为remove(String) 和remove(int) 。 |
void |
delItems(int start, int end) 已弃用从JDK 1.1版开始,未来不会公开使用。这种方法只能作为一个包私有方法保留。 |
void |
deselect(int index) 取消选择指定索引处的项目。 |
AccessibleContext |
getAccessibleContext() 获取 AccessibleContext 与此相关 List 。 |
ActionListener[] |
getActionListeners() 返回在此列表中注册的所有动作侦听器的数组。 |
String |
getItem(int index) 获取与指定索引关联的项目。 |
int |
getItemCount() 获取列表中的项目数。 |
ItemListener[] |
getItemListeners() 返回在此列表中注册的所有项目侦听器的数组。 |
String[] |
getItems() 获取列表中的项目。 |
<T extends EventListener>T[] |
getListeners(类<T> listenerType) 返回当前注册为 *Foo*Listener 的所有对象的数组,此 List 。 |
Dimension |
getMinimumSize() 确定此滚动列表的最小大小。 |
Dimension |
getMinimumSize(int rows) 获取具有指定行数的列表的最小尺寸。 |
Dimension |
getPreferredSize() 获取此滚动列表的首选大小。 |
Dimension |
getPreferredSize(int rows) 获取具有指定行数的列表的首选尺寸。 |
int |
getRows() 获取此列表中的可见行数。 |
int |
getSelectedIndex() 获取列表中所选项目的索引, |
int[] |
getSelectedIndexes() 获取列表中选定的索引。 |
String |
getSelectedItem() 获取此滚动列表中选定的项目。 |
String[] |
getSelectedItems() 获取此滚动列表中选定的项目。 |
Object[] |
getSelectedObjects() 在对象数组中获取此滚动列表中选定的项目。 |
int |
getVisibleIndex() 获取最后通过方法 makeVisible 可见的项目的索引。 |
boolean |
isIndexSelected(int index) 确定是否选择了此滚动列表中的指定项目。 |
boolean |
isMultipleMode() 确定此列表是否允许多个选择。 |
boolean |
isSelected(int index) 已弃用从JDK 1.1版开始,由isIndexSelected(int) 。 |
void |
makeVisible(int index) 使指定索引处的项目可见。 |
Dimension |
minimumSize() 已弃用从JDK 1.1版开始,替换为getMinimumSize() 。 |
Dimension |
minimumSize(int rows) 已弃用从JDK 1.1版开始,由getMinimumSize(int) 。 |
protected String |
paramString() 返回表示此滚动列表状态的参数字符串。 |
Dimension |
preferredSize() 已弃用从JDK 1.1版开始,替换为getPreferredSize() 。 |
Dimension |
preferredSize(int rows) 已弃用截至JDK 1.1版,由getPreferredSize(int) 。 |
protected void |
processActionEvent(ActionEvent e) 通过将此组件发送到任何已注册的 ActionListener 对象来处理此组件上发生的操作事件。 |
protected void |
processEvent(AWTEvent e) 在此滚动列表中处理事件。 |
protected void |
processItemEvent(ItemEvent e) 通过将它们发送到任何已注册的 ItemListener 对象来处理在此列表上发生的项目事件。 |
void |
remove(int position) 从此滚动列表中移除指定位置的项目。 |
void |
remove(String item) 从列表中删除项目的第一次出现。 |
void |
removeActionListener(ActionListener l) 删除指定的动作侦听器,使其不再从此列表中接收到动作事件。 |
void |
removeAll() 从此列表中删除所有项目。 |
void |
removeItemListener(ItemListener l) 删除指定的项目监听器,使其不再从此列表中接收项目事件。 |
void |
removeNotify() 删除此列表的对等体。 |
void |
replaceItem(String newValue, int index) 使用新的字符串替换滚动列表中指定索引处的项目。 |
void |
select(int index) 选择滚动列表中指定索引处的项目。 |
void |
setMultipleMode(boolean b) 设置确定此列表是否允许多个选择的标志。 |
void |
setMultipleSelections(boolean b) 已弃用从JDK 1.1版开始,替换为setMultipleMode(boolean) 。 |
remove方法
如果想使用remove方法删除两个内容一样的同一对象,可以重写该对象的equals方法。其余方法亦可
2.2.3 ListIterator迭代器
允许程序员沿任一方向遍历列表的列表的迭代器,在迭代期间修改列表,并获取列表中迭代器的当前位置。
方法摘要
Modifier and Type | Method and Description |
---|---|
void |
add(E e) 将指定的元素插入列表(可选操作)。 |
boolean |
hasNext() 返回 true 如果遍历正向列表,列表迭代器有多个元素。 |
boolean |
hasPrevious() 返回 true 如果遍历反向列表,列表迭代器有多个元素。 |
E |
next() 返回列表中的下一个元素,并且前进光标位置。 |
int |
nextIndex() 返回随后调用 next() 返回的元素的索引。 |
E |
previous() 返回列表中的上一个元素,并向后移动光标位置。 |
int |
previousIndex() 返回由后续调用 previous() 返回的元素的索引。 |
void |
remove() 从列表中删除由 next() 或 previous() 返回的最后一个元素(可选操作)。 |
void |
set(E e) 用 指定的元素替换由 next() 或 previous() 返回的最后一个元素(可选操作)。 |
2.3 List实现类
2.3.1 ArrayList
-
数组结构实现,查询快、增删慢
-
JDK1.2加入,运行效率快,线程不安全
-
源码分析:
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
// 默认的容量,如果没有向集合中添加任何元素时(new 一个集合),容量是0。
// 10是在执行第一次add方法时通过grow()方法重新copy了一个长度为10的集合赋值给源集合才改变的。
// 扩容并不是每次增加一,而是通过右移扩容1.5倍
transient Object[] elementData; // 存放元素的数组
private int size; //实际的元素个数
2.3.2 Vector
- 数组结构实现,查询快、增删慢
- JDK1.0加入,运行效率慢,线程安全
2.3.3 LinkedList
-
双向链表结构实现,增删快,查询慢
-
void linkLast(E e) { final Node<E> l = last; // last尾节点 final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
2.4 泛型
Java泛型是JDK1.5中引入的一个新特性,其本质是参数化类型,把类型作为参数传递。
常见形式有泛型类、泛型接口、泛型方法。
语法:
-
<T,…>T称为类型占位符,表示一种引用类型。
-
好处:
- 提高代码的重用性
- 防止类型转换异常,提高代码的安全性
2.5 Set
- 无序
- 不重复
- 没有下标
2.3.1 HashSet
- 基于HashCode计算元素存放位置。
- 当存入元素的哈希码相同时,会调用equals进行确认,如结果为true,则拒绝后者存入。
2.3.2 TreeSet
- 基于排列顺序实现元素不重复。
- 实现了SortedSet接口,对集合元素自动排序。
- 元素对象的类型必须实现Comparable接口,指定排序规则(CompareTo方法返回值为0,认为是重复元素)
- 通过CompareTo方法确定是否为重复元素。
如果在创建集合的时候使用匿名内部类实现了 Comparator接口,则集合元素可以不实现Comparable接口
存储结构:红黑树
2.6 红黑树
二叉查找树
二叉查找树,Binary Search Tree 「BST」,要想了解二叉查找树,我们首先看下二叉查找树有哪些特性呢?
- 某节点的左子树节点值仅包含小于该节点值
- 某节点的右子树节点值仅包含大于该节点值
- 左右子树每个也必须是二叉查找树
看个图就轻松理解上面三句话的意思了:
上图,结合二叉查找树的三条约束来看,非常好,没有什么问题。再来看一个图,依旧符合上面三条约束,感觉有问题吗?
- 这是一个走路一米六,一米八的树
- 这是一个畸形的树,大风一挂很可能被折断的树
从程序的角度来说这个树不够平衡,查找次数或时间复杂度 O(h)可能会随着一条腿长无限增长
理科生在高中学习生物时学过一个关键字「去除顶端优势」,通过去除植物顶端优势,侧芽会迅速生长,慢慢变得强壮和平衡, 红黑树其实就是去除二叉查找树顶端优势的解决方案,从而达到树的平衡
红黑树
红黑树,Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST),树上的每个节点都遵循下面的规则:
- 每个节点都有红色或黑色
- 树的根始终是黑色的 (黑土地孕育黑树根, )
- 没有两个相邻的红色节点(红色节点不能有红色父节点或红色子节点,并没有说不能出现连续的黑色节点)
- 从节点(包括根)到其任何后代NULL节点(叶子结点下方挂的两个空节点,并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点
瞬间懵逼?了解一下印象就行,开始玩魔方都是要照着魔方公式一点点玩的,多玩几次就熟悉了。红黑树也一样,红黑树有两大操作:
- recolor (重新标记黑色或红色)
- rotation (旋转,这是树达到平衡的关键)
我们会先尝试 recolor,如果 recolor 不能达到红黑树的 4 点要求,然后我们尝试 rotation,其实红黑树的关键玩法就是弄清楚 recolor 和 rotation 的规则,接下来看看详细的算法公式吧 千万别着急记忆公式,有图示会逐步说明,就像魔方一样,多玩几次就懂了:
假设我们插入的新节点为 X
- 将新插入的节点标记为红色
- 如果 X 是根结点(root),则标记为黑色
- 如果 X 的 parent 不是黑色,同时 X 也不是 root:
-
3.1 如果 X 的 uncle (叔叔) 是红色
-
- 3.1.1 将 parent 和 uncle 标记为黑色
- 3.1.2 将 grand parent (祖父) 标记为红色
- 3.1.3 让 X 节点的颜色与 X 祖父的颜色相同,然后重复步骤 2、3
话不多说,看下图
跟着上面的公式走:
- 将新插入的 X 节点标记为红色
- 发现 X 的 parent § 同样为红色,这违反了红黑树的第三条规则「不能有两个连续相邻的红色节点」
- 发现 X 的 uncle (U) 同样为红色
- 将 P 和 U 标记为黑色
- 将 X 和 X 的 grand parent (G) 标记为相同的颜色,即红色,继续重复公式 2、3
- 发现 G 是根结点,标记为黑色
- 结束
刚刚说了 X 的 uncle 是红色的情况,接下来要说是黑色的情况
- 如果 X 的 parent 不是黑色,同时 X 也不是 root:
-
3.2 如果 X 的 uncle (叔叔) 是黑色,我们要分四种情况处理
-
- 3.2.1 左左 (P 是 G 的左孩子,并且 X 是 P 的左孩子)
- 3.2.2 左右 (P 是 G 的左孩子,并且 X 是 P 的右孩子)
- 3.2.3 右右 (和 3.2.1 镜像过来,恰好相反)
- 3.2.4 右左 (和 3.2.2 镜像过来,恰好相反)
当出现 uncle 是黑色的时候我们第一步要考虑的是 旋转 ,这里先请小伙伴不要关注红黑树的第 4 条规则,主要是为了演示如何旋转的,来一点点看,不要看图就慌,有解释的 :
左左情况
这种情况很简单,想象这是一根绳子,手提起 P 节点,然后变色即可
左右
左旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的左孩子,然后再应用 左左情况
右右
与左左情况一样,想象成一根绳子
右左
右旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的右孩子,然后再应用 右右情况
你说的动图在哪里,你个大骗子,别着急,现在就为小伙伴们奉上动图演示,来说明公式的使用:
案例一
插入 10,20,30,15 到一个空树中
- 向空树中第一次插入数字 10,肯定是 root 节点
- root 节点标记成黑色
- 向树中插入新节点 20,标记为红色
- 20 > 10,并发现 10 没有叶子节点,将新节点 20 作为 10 的右孩子
- 向树中插入新节点 30,标记为红色
- 30 > 10,查找 10 的右子树,找到 20
- 30 > 20,继续查找 20 的右子树,发现 20 没有叶子节点,将值插在此处
- 30 和 20 节点都为红色,30 为右孩子,20 也为右孩子,触发了 右右情况
- 通过一次旋转,提起 20 节点
- 20 节点是根结点,标记为黑色
- 向树中插入新节点 15,标记为红色
- 通过比对大小和判断是否有叶子节点,最终插值为 10 节点的右孩子
- 15 和 10 节点都为红色,15 的 uncle 节点 30 也为红色
- 按照公式,将 15 的 parent 10 和 uncle 30 更改为黑色
- 让 15 节点 grand parent 20 的颜色与 15 节点的颜色一样,变为红色
- 20 为根结点,将其改为黑色
继续插入其他节点只不过反复应用上面的公式,上面应用到的红黑树工具,可以暂停动画效果,一帧一帧的看红黑树的转换过程,这样通过练习,查看公式,观察变化三管齐下,红黑树的入门理解应该完全不再是问题了
灵魂追问
- jdk 1.8 HashMap 中有使用到红黑树,你知道触发条件是什么吗?有读过源码是如何 put 和 remove 的吗?
- 这里讲的是红黑树的 insert,delete 又是什么规则呢?
- 哪些场景可以应用红黑树?
- 你了解各种树的时间复杂度吗?
- 留个小作业,应用工具将 [10 70 32 34 13 56 32 56 21 3 62 4 ] 逐个插入到树中,理解红黑树 recolor 和 rotation 的转换规则
3.Map体系集合
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1F4VOwc0-1604324784344)(C:/Users/CHENLH/AppData/Roaming/Typora/typora-user-images/image-20200823133431388.png)]
3.1 Map接口
- 存储一对数据,key-value
- 无序
- 无下标
- 键不可重复,值可以重复
遍历
遍历先使用KeySet方法获取所有的key的Set集合,然后对获取到的Set进行遍历
或者通过entrySet()方法获取键值对的Set集合
3.2 HashMap
线程不安全,运行效率快;允许用null作为key或是value。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // 初始容量16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 加载因子,当容量到达目前容量的75%时开始扩容
static final int TREEIFY_THRESHOLD = 8; // 当链表长度大于8数组长度大于64 将链表改为红黑树
- HashMap刚创建时,table是null,为了节省空间,当添加第一个元素是,table容量调整为16
- 当元素个数大于阙值(16*0.75=12)时,会进行扩容,扩容后大小为原来的2倍。目的是减少调整元素的个数
- jdk1.8当每个链表长度大于8,并且元素个数大于等于64时,会调整为红黑树,目的提高执行效率
- jdk1.8当链表长度小于6时,调整成链表
- jdk1.8以前,链表是头插入,jdk1.8以后时是尾插入(为了避免在多线程时形成环形链表)
- 多线程下推荐使用ConcurrentHashMap
3.3 TreeMap
实现接口SortedMap,可以对key自动排序
Collections工具类
- 概念:集合工具类,定义了除了存取以外的集合常用方法。
方法:
-
public static void reverse(List<?> list)//反转集合中元素的顺序
-
public static void shuffle(List<?> list)//随机重置集合元素的顺序
-
public static void sort(List list)//升序排序(元素类型必须实现Comparable接口)
-
…
数组转换为集合,该集合是受限集合,不允许添加删除