Java数据结构

2023-03-04 15:54| 来源: 网络整理| 查看: 265

前置内容：一、数组概述

定义：

在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识

In computer science, an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key

因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如：

java int[] array = {1,2,3,4,5}

知道了数组的数据起始地址 $BaseAddress$，就可以由公式 $BaseAddress + i * size$ 计算出索引 $i$ 元素的地址

$i$ 即索引，在 Java、C 等语言都是从 0 开始$size$ 是每个元素占用字节，例如 $int$ 占 $4$，$double$ 占 $8$

小测试

java byte[] array = {1,2,3,4,5}

已知 array 的数据的起始地址是 0x7138f94c8，那么元素 3 的地址是什么？

答：0x7138f94c8 + 2 * 1 = 0x7138f94ca

空间占用

Java 中数组结构为

8 字节 markword4 字节 class 指针（压缩 class 指针的情况）4 字节数组大小（决定了数组最大容量是 $2^{32}$）数组元素 + 对齐字节（java 中所有对象大小都是 8 字节的整数倍[^12]，不足的要用对齐字节补足）

例如

java int[] array = {1, 2, 3, 4, 5};

的大小为 40 个字节，组成如下

8 + 4 + 4 + 5*4 + 4(alignment)

随机访问性能

即根据索引查找元素，时间复杂度是 $O(1)$

二、动态数组

Java版本：

public class DynamicArray implements Iterable { private int size = 0; // 逻辑大小 private int capacity = 8; // 容量 private int[] array = {}; /** * 向最后位置 [size] 添加元素 * * @param element 待添加元素 */ public void addLast(int element) { add(size, element); } /** * 向 [0 .. size] 位置添加元素 * * @param index 索引位置 * @param element 待添加元素 */ public void add(int index, int element) { checkAndGrow(); // 添加逻辑 if (index >= 0 && index > 1; int[] newArray = new int[capacity]; System.arraycopy(array, 0, newArray, 0, size); array = newArray; } } /** * 从 [0 .. size) 范围删除元素 * * @param index 索引位置 * @return 被删除元素 */ public int remove(int index) { // [0..size) int removed = array[index]; if (index

缓存的第一行数据已经被新的数据 $[8,0] ... [8,13]$ 覆盖掉了，以后如果再想读，比如 $[0,1]$，又得到内存去读了

同理可以分析 ij 函数则能充分利用局部性原理加载到的缓存数据

举一反三

I/O 读写时同样可以体现局部性原理数组可以充分利用局部性原理，那么链表呢？答：链表不行，因为链表的元素并非相邻存储越界检查

java 中对数组元素的读写都有越界检查，类似于下面的代码

bool is_within_bounds(int index) const { return 0

【本文地址】

公司简介

联系我们