Java常用集合与原理解析
作者:青年痴呆 发布时间:2023-04-01 14:26:42
Java 最初版本只为常用的数据结构提供了很少的一组类:Vector、Stack、Hashtable、BitSet 与 Enumeration 接口
迭代器
public interface Collection<E>
{
boolean add(E element);
Iterator<E> iterator();
...
}
// ITerator 接口包含4个方法
public interface Iterator<E>
{
E next();
boolean hasNext();
void remove();
default void forEachRemainint(Consumer<? super E> action);
}
通过反复调用 next 方法,可以朱哥访问集合中的每个元素。但是,如果到达了集合的末尾,next 方法将抛出一个 NoSuchElementException。因此,需要在调用 next 之前调用 hasNext 方法。
Collection<String> c = ...;
// 普通循环
Iterator<String> iter = c.iterator();
while(iter.hasNext())
{
String element = iter.next();
// do something with element
}
// 此外,使用 for-each 循环可以更简练的表示同样的操作。编译器简单地将其转换为带有迭代器的循环
for(String element : c)
{
// do something with element
}
// 也可以不写循环,而是调用方法并提供一个Lambda表达式
Iterator<String> iter = c.iterator();
iterator.forEachRemaining(element -> /* do something with it */ );
Java 集合类库中的迭代器查找操作与位置变更更紧密耦合,查找元素的唯一方法是调用 next,而在执行查找操作的同时,迭代器的位置就会随之向前移动。
因此,可以认为 Java迭代器位于两个元素之间。当调用 next 时,迭代器就越过下一个元素,并返回刚刚越过的那个元素的引用。
Iterator 接口的 remove 方法会删除上次调用 next 方法时返回的元素。 next 方法和 remove 方法调用之间存在依赖性。如果调用 remove 之前没有调用 next,将会抛出一个 IllegalStateException 异常。
// 如果想删除两个相邻的元素,不能直接这样调用
it.remove();
it.remove(); // ERROR
// 实际上,需要先next越过将要删除的元素
it.remove();
it.next();
it.remove(); // OK
集合框架中的接口
集合有两个基本接口: Collection 和 Map
List 是一个有序集合。可以采用两种方式访问元素:迭代器访问,或者使用一个整数索引来访问。后面这种方法称为随机访问,因此这样可以按任意顺序访问元素。与之不同,使用迭代器访问时,必须顺序地访问元素。
**纰漏**:集合框架在这个地方设计得不好。实际上有两种有序集合,其性能开销有很大差异。
1. 数组支持的有序集合,可以快速地随机访问,因此适合使用List方法并提供一个整数索引访问
2. 链表尽管也是有序的,但是随机访问**很慢**,所以最好使用迭代器进行遍历、
为了避免对链表完成随机访问操作, Java 1.4 引入了一个*标记接口*`RandomAccess`,这个接口不包含任何方法,不过可以用来测试一个特定的集合是否支持高效的随机访问:
` if(c instanceof RandomAccess) { /* use random access algorithm */ }`
` else { /* use qequential access algorithm */ }`
Set 接口等同于 Collection 接口,不过其方法的行为有更严谨的定义。
具体集合
集合类型 | 描述 |
---|---|
ArrayList | 可以动态增长和缩减的一个索引序列 |
LinkedList | 可以在任何位置高效插入和删除的一个有序序列 |
ArrayDeque | 实现为循环数组的一个双端队列 |
HashSet | 没有重复元素的一个无需集合 |
TreeSet | 一个有序集 |
EnumSet | 一个包含枚举类型值得集 |
LinkedHashSet | 一个可以记住元素插入次序的集 |
PriorityQueue | 允许高校删除最小元素的一个集合 |
HashMap | 存储键/值 关联的一个数据结构 |
TreeMap | 键有序的一个映射 |
EnumMap | 键属于枚举类型的一个映射 |
LinkedHashMap | 可以记住键/值 项添加次序的一个映射 |
WeakHashMap | 值不会再别出使用时就可以被垃圾回收的一个映射 |
IdentityHashMap | 用== 而不是equal 比较键的一个映射 |
散列码
散列码可以用于快速第查找对象
在 Java 中,散列表用链表数组实现。每个列表被称为桶。 在 Java 8 中,桶满时会从链表变为平衡二叉树,以提高性能。标准类库使用的桶数是 2 的幂,默认值为 16(为表大小提供的任何值都将自动地转换为 2 的下一个幂值)。
如果散列表太满,就需要再散列。此时,就需要创建一个桶数更多的表,并将所有的元素插入到这个新表中,然后丢弃原来的表。装填因子(默认0.75)可以确定何时对散列表进行散列,新表的桶数是原来的两倍。
树集
树集是一个有序集合,可以以任意顺序将元素插入到集合中。
每次将一个元素添加到树中,都会将其放置在正确的排序位置上。因此,迭代器总是以有序的顺序访问每个元素。
将一个元素添加到树中要比添加到散列表中慢。但是,检查数组或链表中的重复元素时,树会快很多。
注: 要使用树集,必须能够比较元素。这些元素必须实现 Comparable 接口,或者构造集时必须提供一个 Comparator。
队列
队列允许高校地在尾部添加元素,并在头部删除元素。不支持在队列中间添加元素
Java 6 中引入了 Deque 接口,ArrayDeque 和 LinkedList 类实现了这个接口。
优先队列
优先队列中的元素可以按照任意的顺序插入,但会按照有序的顺序进行检索。
无论何时调用 remove 方法,总会获得当前优先队列中最小的元素。优先队列并没有对所有元素进行排序,而是使用了一个高效地数据结构——堆。堆是一个可以自组织的二叉树,其添加与删除操作可以让最小的元素移动到根,而无需花费时间对元素进行排序。
映射
映射数据结构用于存放键/值对,知道某些关键信息,可以查找与之关联的元素。
基本映射
Java类库我映射提供了两个通用的实现:HashMap
和TreeMap
。
映射视图
集合框架不认为映射本身是一个集合。(其他数据结构框架认为映射是一个键/值对集合,或者是按键索引的值集合)。不过,可以得到视图——实现了 Collection 接口或某个子接口的对象。
keySet()
、values()
、entrySet()
注: keySet 不是 HashSet 或 TreeSet,而是实现了 Set 接口的另外某个类的对象。
可以在集视图中删除元素,它们将从该映射中删除,但是不能添加任何元素
弱散列映射
WeakHashMap
类使用弱引用保存键。WeakReference 对象将包含另一个对象的引用,在这里,就是一个散列表键。正常情况下,如果垃圾回收器发现某个特定的对象已经没有他人引用,就会将其回收。
然而,如果某个对象只能由 WeakReference 引用,垃圾回收器也会将其回收,但会将这个对象的弱引用放进一个队列。WeakHashMap 将周期性地检查队列,以便找出新添加的弱引用。一个若引用进入队列意味着这个键不再被他人使用,并且已经回收。于是,WeakHashMap 将删除相关联的映射。
链接散列集合映射
LinkedHashMap
和LinkedHashSet
会记住插入元素项的顺序。
枚举集与映射
EnumSet
是一个枚举类型元素集的高效实现。内部用位序列实现。
EnumMap
是一个键类型为枚举类型的映射
标识散列映射
IdentityHashMap
类有特殊用途。该类中,键的散列值由 System.identityHashCode 计算,是根据对象的内存地址计算散列码所使用的方法。因此在比较对象时采用==
,不同的键对象即使内容相同,也被视为不同的对象。
在实现对象遍历算法(如对象串行化)时,这个类十分有用,可以用来跟踪哪些对象已经遍历过。
来源:https://blog.csdn.net/qq_25358293/article/details/119146801


猜你喜欢
- Gson是Google的一个开源项目,可以将Java对象转换成JSON,也可能将JSON转换成Java对象。Gson里最重要的对象有2个Gs
- 在新建Java项目时,run运行main方法时,报错 “java: 错误: 无效的源发行版:16”,
- 这个其实很简单,思路是这样的,就是拿view的宽度,除以点的点的宽度+二个点 之间的间距,就可以算出大概能画出几个点
- 今天想和小伙伴们来聊一聊 Spring Security 中的角色继承问题。角色继承实际上是一个很常见的需求,因为大部分公司治理可能都是金字
- 什么是RabbitMQ?RabbitMQ是由erlang语言开发的一个基于AMQP(Advanced Message Queuing Pro
- 本文实例讲述了C#多线程学习之生产者和消费者用法。分享给大家供大家参考。具体实分析如下:前面的文章说过,每个线程都有自己的资源,但是代码区是
- 一.添加控件IrisSkin2.dll。方法:  
- 一、简介 TextureMapFragment:用于显示地图片段。 二、示例3--Demo03MapFragment.c
- 前言上篇博文把表连接查询和三种对应关系的写法记录总结了,本篇要把 mybatis 中的动态sql 的使用以及缓存知识记录下来。动态SQL在解
- 1:Group的功能Group可以管理一组节点Group可以对管理的节点进行增删改查的操作Group可以管理节点的属性1.2:看看JDKSE
- 本文实例演示了Java多线程死锁。分享给大家供大家参考,具体如下:package com.damlab.fz;public class De
- 前言我们都知道memberwiseclone 会将浅克隆。什么是浅克隆?如何深克隆呢?正文public class good{
- 假设有两个线程在并发运行,一个线程执行的代码中含有一个死循环如:while(true)....当该线程在执行while(true)中代码时,
- 一些公共的模板############################################### 对于一些基本指令的添加####
- 我们肯定遇到过打开别人的项目时一直处于Building‘XXX'Gradle project info的情况。本文通过两种方法带领大
- 最近项目里涉及到自定义View的东西还是挺多的,所以打算在自定义View上多花点时间,也顺便分享给大家。先总结下自定义View的步骤:1、自
- 企业级的系统和我们平常桌面、手机上运行的软件有着很重要的区别,其中比较重要的一点就是环境(包括第三方的系统的不同接口以及各系统的不同版本、安
- String ipArr[]={"127.0.0.1","127.0.0.2"}; &n
- 在Thread中注入Bean无效在Spring项目中,有时需要新开线程完成一些复杂任务,而线程中可能需要注入一些服务。而通过Spring注入
- 将BeanFactory和ApplicationContext作为容器使用在Spring中,BeanFactory和ApplicationC