数据结构基础篇-线性表-数组

数组可以说使我们编程中最常见的数据结构了,在代码中随处可见。我们可以很容易使用类似int[] ints = new int[4];这样的语法构建一个整数数组,那么你了解数组底层的原理吗?接下来我们就来结合数组的特点分析一下数组的原理,并实现一个简单的数组来帮助大家理解的原理。

数组的特点

高效的随机访问特性,使数组能够根据下标以O(1)的时间复杂度随机访问数组中的任意元素(请注意这里随机访问不是查询哦)。
相应的,为满足随机访问的特性,需要作出一些牺牲,对数组的元素做一些限制:

  1. 数组需要占用一块连续的物理内存
  2. 数组中元素的类型必须是一致的

只有满足了这两点,才能实现随机访问的特性。

数组如何实现随机访问的

由于数组分配在连续的内存中,我们可以很容易的通过起始地址 + 元素偏移量来定位具体的数组元素的内存地址,然后通过内存地址获取该地址保存的元素:

  1. 数组起始内存地址,即为数组分配的连续内存的起始地址
  2. 数组元素偏移量,即为该元素的下标 * 元素类型的长度
    所以我们得出以下公式:
    1
    下标为i的元素的内存地址 = 数组起始内存地址 + 元素类型长度 * i

可以看到,数组根据下标访问元素时,只需要两次数值计算和一次内存读取操作,非常的高效。

数组的优点和缺点

我们先讨论优点:

  1. 随机访问特性能保证快速访问(包括修改)对应下标的数组元素,这项操作的代价很小(O(1))。
  2. CPU缓冲行的特性能够加速数组的访问,当然缓冲行不是我们这篇文章讨论的重点,我们可以简单的认为,CPU是对数组友好的,当我们访问一个数组元素时,CPU会机智的把这个元素后面的好多个元素一起给你,这样在你访问下一个元素时可能就不需要再去内存中读取了。

那么数组有什么缺点呢:

  1. 数组在初始化的时候必须指定容量,这就很不灵活,如果分配的太大,就会浪费空间,如果分配的太小,就需要动态扩容,而数组的扩容需要重新分配一块更大的空间,然后拷贝元素,很显然,这是一项O(n)时间复杂度的操作。
  2. 数组必须分配连续的内存,如果内存碎片过多,可能会导致内存分配失败。

这里需要补充一点:
理论上,数组的插入和删除操作因为涉及到元素的移动,所以时间复杂度是O(n)的,要差于链表在已知节点情况下的插入和删除操作,数组和链表的查询操作都需要遍历匹配,所以时间复杂度都是O(n)的。
但是事实上,得益于CPU的缓冲行机制,数组的连续存储优势会体现的非常明显,在大部分情况下(元素数量未达到一定规模的时候),数组的的插入、删除、查询都要快于链表,并且具备链表所没有的随机访问特性。

实现一个简单的int数组

理解了数组的原理,我们来动手实现一个int型数组,这里使用java实现,借助了Unsafe类来做内存分配。
源码可以查看我的github

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
public class IntArray {

// 借助 sun.misc.Unsafe 直接分配内存
private static final Unsafe UNSAFE = UnsafeUtil.getUnsafe();

// int类型占用4个字节(byte)
// 下标i的内存地址偏移量 == i * 4 == i << 2
private static final int INDEX_SHIFT = 2;

private final int length;

// 该数组的内存起始地址
private final long memoryAddress;

/**
* new int[length]
*/
public IntArray(int length) {
if (length < 0) {
throw new IllegalArgumentException(String.valueOf(length));
}

this.length = length;
// 分配一块连续的内存,保存这块内存的起始地址
memoryAddress = UNSAFE.allocateMemory(length << INDEX_SHIFT);
// 初始化这块内存
UNSAFE.setMemory(memoryAddress, length << INDEX_SHIFT, (byte) 0);
}

/**
* array[index] = data
*/
public void set(int index, int data) {
ensureIndexRange(index);
// 根据 起始地址+数组下标*类型长度 计算出内存地址,然后将data保存到该地址
UNSAFE.putInt(memoryAddress + (index << INDEX_SHIFT), data);
}

/**
* array[index]
*/
public int get(int index) {
ensureIndexRange(index);
// 根据 起始地址+数组下标*类型长度 计算出内存地址,然后获取该地址的int值
return UNSAFE.getInt(memoryAddress + (index << INDEX_SHIFT));
}

/**
* array.length
*/
public int length() {
return length;
}

private void ensureIndexRange(int index) {
if (index < 0 || index >= length) {
throw new IndexOutOfBoundsException(String.valueOf(index));
}
}

}

本文标题:数据结构基础篇-线性表-数组

文章作者:山坡杨

发布时间:2019年03月10日 - 18:04:17

最后更新:2019年03月25日 - 09:25:41

原始链接:http://www.yangxf.top/1/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

感觉本站内容不错,读后有收获?
0%