Java中的LinkedList和ArrayList以及HashMap和TreeMap

ops/2024/10/25 13:49:52/

在Java的集合框架中，`LinkedList`和`ArrayList`都是用来存储一组对象的容器，但它们在内部实现、性能特点等方面存在着一些差异。

## 一、内部实现
1. **ArrayList**
   - `ArrayList`是基于数组实现的动态数组。它在内存中是一块连续的存储空间。当创建`ArrayList`时，会初始化一个默认大小的数组（初始容量为10）。随着元素的添加，如果数组容量不足，会进行扩容操作，通常是将原数组复制到一个更大容量的新数组中。
   - 例如，以下代码创建了一个`ArrayList`并添加元素：
```java
import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("Apple");
        arrayList.add("Banana");
        arrayList.add("Cherry");
        System.out.println(arrayList);
    }
}
```
2. **LinkedList**
   - `LinkedList`是基于双向链表实现的。每个节点包含了数据元素、指向前一个节点的引用和指向后一个节点的引用。这种结构不需要连续的内存空间，在内存中的存储是分散的。
   - 例如，创建和使用`LinkedList`的代码如下：
```java
import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Dog");
        linkedList.add("Cat");
        linkedList.add("Mouse");
        System.out.println(linkedList);
    }
}
```

## 二、性能特点
1. **随机访问**
   - **ArrayList**：由于`ArrayList`基于数组实现，它支持快速的随机访问。通过索引访问元素的时间复杂度为 $O(1)$。例如：
```java
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
// 快速访问索引为1的元素
System.out.println(arrayList.get(1));
```
   - **LinkedList**：对于`LinkedList`，随机访问元素效率较低，因为需要从链表的头部（或尾部）开始遍历，时间复杂度为 $O(n)$。例如：
```java
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
// 访问索引为1的元素，效率较低
System.out.println(linkedList.get(1));
```
2. **插入和删除操作**
   - **ArrayList**：在`ArrayList`的中间插入或删除元素时，需要移动后面的元素，时间复杂度为 $O(n)$（$n$为元素个数）。但是在末尾添加元素的时间复杂度为 $O(1)$（不考虑扩容情况）。例如：
```java
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
// 在索引为1的位置插入元素4
arrayList.add(1, 4);
System.out.println(arrayList);
```
   - **LinkedList**：在`LinkedList`中插入和删除元素（特别是在链表中间）只需要修改节点之间的引用，时间复杂度为 $O(1)$。例如：
```java
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
// 在第二个位置插入元素4
linkedList.add(1, 4);
System.out.println(linkedList);
```

## 三、适用场景
1. **ArrayList**
   - 当需要频繁进行随机访问元素的操作，并且数据量相对稳定或者增长可预测时，`ArrayList`是一个较好的选择。例如，在存储数据库查询结果集并需要频繁根据索引获取元素时。
2. **LinkedList**
   - 当需要频繁进行插入和删除操作（特别是在集合中间）时，`LinkedList`更合适。例如，在实现一个队列或者栈数据结构时，可以使用`LinkedList`，因为队列的入队和出队操作，栈的入栈和出栈操作都可以高效地在链表头部或者尾部进行。

综上所述，在Java编程中，根据具体的需求选择`LinkedList`或者`ArrayList`可以提高程序的性能和效率。

接下来我们来了解一下Map集合。

# Java中的HashMap与TreeMap

在Java的集合框架中，`HashMap`和`TreeMap`都是用于存储键 - 值对（`key - value`）的数据结构，但它们在内部实现、功能特性以及适用场景等方面存在着明显的差异。

## 一、内部实现
1. **HashMap**
   - `HashMap`基于哈希表实现。它通过计算键（`key`）的哈希值来确定元素在数组中的存储位置。在`JDK 1.8`之前，`HashMap`采用数组 + 链表的结构。当发生哈希冲突（即不同的键计算出相同的哈希值）时，新元素会以链表的形式存储在对应数组索引的位置。在`JDK 1.8`之后，如果链表长度超过一定阈值（默认为8），链表会转换为红黑树，以提高查找效率。
   - 例如，以下是创建和使用`HashMap`的示例代码：
```java
import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        hashMap.put("Apple", 1);
        hashMap.put("Banana", 2);
        hashMap.put("Cherry", 3);
        System.out.println(hashMap.get("Apple"));
    }
}
```
2. **TreeMap**
   - `TreeMap`基于红黑树（一种自平衡二叉查找树）实现。它会根据键（`key`）的自然顺序或者自定义的比较器来对键值对进行排序。每次插入元素时，都会按照红黑树的规则调整树的结构，以保持树的平衡。
   - 例如：
```java
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("Dog", 1);
        treeMap.put("Cat", 2);
        treeMap.put("Mouse", 3);
        System.out.println(treeMap.get("Cat"));
    }
}
```

## 二、功能特性
1. **排序特性**
   - **TreeMap**：由于基于红黑树实现，`TreeMap`中的键值对是有序的。默认按照键的自然顺序（如果键实现了`Comparable`接口）进行排序。例如，如果键是字符串类型，那么会按照字典序排序。也可以通过自定义比较器来指定排序规则。
   - 以下是自定义比较器的示例：
```java
import java.util.Comparator;
import java.util.TreeMap;

public class CustomComparatorTreeMap {
    public static void main(String[] args) {
        // 按照字符串长度进行排序的比较器
        Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        };
        TreeMap<String, Integer> treeMap = new TreeMap<>(comparator);
        treeMap.put("long", 1);
        treeMap.put("short", 2);
        treeMap.put("medium", 3);
        System.out.println(treeMap);
    }
}
```
   - **HashMap**：`HashMap`不保证元素的顺序，元素的存储顺序取决于哈希函数的计算结果以及哈希冲突的处理方式。
2. **性能特性**
   - **HashMap**：在插入、删除和查找操作方面，`HashMap`通常具有较好的性能。对于插入和查找操作，平均时间复杂度接近 $O(1)$。但是在最坏情况下（哈希冲突严重时），查找操作可能退化为 $O(n)$，不过这种情况在实际应用中很少出现。
   - **TreeMap**：插入、删除和查找操作的时间复杂度为 $O(\log n)$，其中 $n$ 是树中的节点数量。虽然在平均情况下，`TreeMap`的性能比`HashMap`略差，但它提供了有序性的保证。

## 三、适用场景
1. **HashMap**
   - 当不需要对键值对进行排序，并且需要快速的插入、删除和查找操作时，`HashMap`是首选。例如，在存储用户的配置信息，其中键是配置项名称，值是配置项的值，不需要按照特定顺序存储这些信息时。
2. **TreeMap**
   - 当需要对键值对按照键进行排序时，例如在实现一个排行榜系统，键是用户的排名分数，值是用户信息，需要按照分数对用户进行排序时，`TreeMap`就非常合适。

总之，在Java编程中，根据实际需求合理选择`HashMap`或者`TreeMap`可以提高程序的性能和功能的准确性。


http://www.ppmy.cn/ops/128351.html

相关文章

移动开发（五）：.NET MAUI中自定义主题设置

移动开发（五）：.NET MAUI中自定义主题设置

目录 一、.NET MAUI主题设置原理 二、.NET MAUI主题设置案例 2.1 创建主题文件 2.2 修改App.xaml 文件 2.3 设置默认主题的三种方式 2.4 通过按钮切换主题 三、.NET MAUI主题设置技巧 四、总结 今天给大家分享.NET MAUI应用中如何自定义主题&#xff0c;提升APP本身个性…
阅读更多...
数据结构——树——二叉树——大小堆

数据结构——树——二叉树——大小堆

目录 1>>导言 2>>树 2.1>>树的相关术语 2.2>>树的表示和应用场景 3>>二叉树 3.1>>完全二叉树 3.2>>大小根堆 4>>结语 1>>导言 上篇小编将队列的内容给大家讲完了&#xff0c;这篇要步入新的篇章&#xff0c;请宝…
阅读更多...
Nginx服务器反向代理MinIO配置

Nginx服务器反向代理MinIO配置

文章目录 配置请求代理到该域名的根目录请求代理到该域名的非根目录 参考网址 配置 请求代理到该域名的根目录 # 代理minio 上传server {listen 80;listen [::]:80;server_name minio.example.net;# 允许在HTTP头中使用特殊字符ignore_invalid_headers off;# 禁用代理…
阅读更多...
CTFHUB技能树之XSS——过滤关键词

CTFHUB技能树之XSS——过滤关键词

开启靶场&#xff0c;打开链接&#xff1a; 看上去跟上一题应该差不多&#xff0c;应该只是添加多点过滤规则吧 直接拿xss平台的代码试试&#xff1a; <sCRiPt sRC//xs.pe/6b6></sCrIpT> 这时候突然听到xss平台的上线语音提醒&#xff1a; 成功得到flag&#xff1…
阅读更多...
微信小程序canvas 生成二维码图片，画图片，生成图片，将两个canvas结合并保存图片

微信小程序canvas 生成二维码图片，画图片，生成图片，将两个canvas结合并保存图片

**需求实现步骤如下 先定义两个canvas一个canvas myQrcode画二维码的图片另一个canvas mycanvas画一个背景图&#xff0c;并把二维码画到这个canvas上&#xff0c;mycanvas这个canvas生成一张图片&#xff0c;返回图片的临时路径最后保存图片到手机** 首先wxml,新版微信小程序…
阅读更多...
《IDE 巧用法宝：使用技巧全解析与优质插件推荐》

《IDE 巧用法宝：使用技巧全解析与优质插件推荐》

在日常撸代码的时候&#xff0c;相信兄弟们在IDEA 中用到不少插件&#xff0c;利用插件&#xff0c;不仅可以提高工具效率&#xff0c;撸起代码来&#xff0c;也格外的娃哈哈…… 一、IntelliJ IDEA 作为一个资深 Java 程序员&#xff0c;除了 IDEA 中默认的插件&#xff0c;我…
阅读更多...
如何训练 RAG 模型

如何训练 RAG 模型

训练 RAG&#xff08;Retrieval-Augmented Generation&#xff09;模型涉及多个步骤&#xff0c;包括准备数据、构建知识库、配置检索器和生成模型&#xff0c;以及进行训练。以下是一个详细的步骤指南&#xff0c;帮助你训练 RAG 模型。 1. 安装必要的库 确保你已经安装了必…
阅读更多...
【纯血鸿蒙】鸿蒙专项测试

【纯血鸿蒙】鸿蒙专项测试

一、初步了解 随着信息技术的高速发展，移动应用与人们生活日益紧密，面向各类场景的应用层出不穷，什么样的应用更受用户青睐呢？在满足用户功能需求之上，一个好的应用要能运行稳定、流畅不卡顿、占用内存小、安全等级高，此外，最好还能提供更多创新便捷的附加能力。 为了匹…
阅读更多...
最新文章

Copyright @ 2022~2023