数组--数据结构--黑马

数组

定义

数组有一组元素(值或变量)组成的数据结构，每个元素有至少一个索引或键来标识

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

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

当知道数组中0索引的地址，假设为 $b$，那么索引为1的地址为 $b+4$ ，因为是整数数组，一个元素占用4个字节，其他索引的地址是 $b+size\ast i$ ，其中 $size$ 为整数占用字节大小4。

由此，知道数组的数据起始地址 $BaseAddress$ ，可由公式 $BaseAddress+size\ast i$ 计算出索引 $i$ 处的元素地址

• $i$ 即为索引，在Java、C等语言中索引从0开始；
• $size$ 为每个元素占用的字节大小，例如，$int$ 占4个字节，$double$ 占8个字节，$char$ 占一个字节，$short$ 占2个字节等，如下所示。
  

小测试

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

已知array的数据的起始地址为 $0x7138f94c8$ ，那么索引为2元素为3的地址为多少？

因为是byte，则一个元素占用一个字节，索引为2的地址为起始地址 + 2 * 1，即，$0x7138f94c8+2\ast 1=0x7138f94ca$ ，因为是十六进制，索引8+2为10，即为a,

性能

空间占用

Java中的数据结构为

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

例如

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

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

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

随机访问

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

动态数组

public class DynamicArray implements Iterable<Integer>{
    private int size = 0;  // 逻辑大小，控制数组中的元素个数
    private int capacity = 8; // 数组能存储元素的最大容量
    // private int[] array = new int[capacity];
    
    private int[] array = {};  // 初始，空数组占用空间比开始长度为capacity的数组占用空间小，在添加元素检查时，初始化容量为capacity的数组
	
    // 尾部添加元素
    public void addLast(int vlaue) {
        add(size, value);
    }
    
    // 在指定索引位置插入元素
    pubic void add(int index, int value) {
        if (index < 0 || index > size) {
            System.out.println("索引错误");
        }
		// 检查数组容量是否满，size == capacity
        checkAndGrow();
        if (index >= 0 && index < size) {
			System.arraycopy(array, index, array, index + 1, size - index);
        }  
        array[index] = value;
        size++;
    }
    
    // 删除指定索引的元素
    public int remove(int index) {
        int value = array[index];
        if  (index < size - 1) {
            System.arraycopy(array, index + 1, array, index, size - index - 1);
        }
        size--;
        return value;
    }
    
    // 根据索引查找元素
    public int get(int index) {
        return array[index];
    }
    
    // 遍历数组元素，使用foreach
    public void foreach() {
        for(int i = 0; i < size; i++) {
            System.out.println(i);
        }
    }
    
    // 遍历方法1 使用函数式接口作为参数传递
    public void foreach1(Consumer<Integer> consumer) {
        for(int i = 0; i < size; i++) {
            consumer.accept(array[i]);
        }
    }
    
    // 遍历方法2 迭代器遍历
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int index = 0;
            @Override
            public boolean hasNext() {  // 是否有下一个元素
                return index < size;
            }
            
            @Override
            public Integer next() {  // 返回当前索引元素，并移动到下一个元素
                return array[index++];
            }
        };
    }
    
    // 遍历方法3 使用流的方法
    public IntStream stream() {
        return IntStream.of(Array.copyOfRange(array, 0, size)); // 拷贝左闭右开
    }
    
    // 检查容量是否满
    public void checkAndGrow() {
        if (size == 0) {
            return new int[capacity];
        }
        if (size == capacity) {
            // 进行扩容
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }
    
}
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

性能

查询

根据索引查询元素，时间复杂度为 $O(1)$ ;

插入或删除

头部插入，时间复杂度 $O(n)$

中间插入，时间复杂度 $O(n)$

尾部插入，时间复杂度 $O(1)$

二维数组

int[][] array = {
    {11, 12, 13, 14，15},
    {21, 22, 23, 24，25},
    {31, 32, 33, 34, 35},
};
1
2
3
4
5

• 二维数组占32个字节，其中 array[0]，array[1]，array[2] 三个元素分别指向三个一维数组的引用；
• 三个一维数组占用40个字节
• 它们在内存布局上是连续的

局部性原理

只讨论空间局限性

• cpu读取内存数组后，会将其放入到高速缓存中(速度快)，如果后面的计算使用到此数据，只需要到高速缓存中获取，不需要到内存中读取，从而节省时间。
  个字节，其中 array[0]，array[1]，array[2] 三个元素分别指向三个一维数组的引用；
• 三个一维数组占用40个字节
• 它们在内存布局上是连续的

局部性原理

只讨论空间局限性

• cpu读取内存数组后，会将其放入到高速缓存中(速度快)，如果后面的计算使用到此数据，只需要到高速缓存中获取，不需要到内存中读取，从而节省时间。
• 缓存的最小存储单元为一个缓存行(cache line)， 一般为64bytes，一次读取数据若少不划算，因此最少读64bytes填满缓存行，因此在读取某个数据时，会将临近数据一起读取，即为空间局部性 。