Home Tags Posts tagged with "数据结构"

数据结构

0 39

本文整理来自于 《极客时间—数据结构与算法之美》王争

一、带着问题去学习

Word 这种文本编辑器你平时应该经常用吧,那你有没有留意过它的拼写检查功能呢?一旦我们在 Word 里输入一个错误的英文单词,它就会用标红的方式提示“拼写错误”。Word 的这个单词拼写检查功能,虽然很小但却非常实用。你有没有想过,这个功能是如何实现的呢?

二、散列思想(散列表的理论基础)

散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash 表”,你一定也经常听过它

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

我用一个例子来解释一下。假如我们有 89 名选手参加学校运动会。为了方便记录成绩,每个选手胸前都会贴上自己的参赛号码。这 89 名选手的编号依次是 1 到 89。现在我们希望编程实现这样一个功能,通过编号快速找到对应的选手信息。

你会怎么做呢?

我们可以把这 89 名选手的信息放在数组里。编号为 1 的选手,我们放到数组中下标为 1 的位置;编号为 2 的选手,我们放到数组中下标为 2 的位置。以此类推,编号为 k 的选手放到数组中下标为 k 的位置。因为参赛编号跟数组下标一一对应,当我们需要查询参赛编号为 x 的选手的时候,我们只需要将下标为 x 的数组元素取出来就可以了,时间复杂度就是 O(1)。这样按照编号查找选手信息,效率是不是很高?实际上,这个例子已经用到了散列的思想。在这个例子里,参赛编号是自然数,并且与数组的下标形成一一映射,所以利用数组支持根据下标随机访问的时候,时间复杂度是 O(1) 这一特性,就可以实现快速查找编号对应的选手信息。

你可能要说了,这个例子中蕴含的散列思想还不够明显,那我来改造一下这个例子。

假设校长说,参赛编号不能设置得这么简单,要加上年级、班级这些更详细的信息,所以我们把编号的规则稍微修改了一下,用 6 位数字来表示。比如 051167,其中,前两位 05 表示年级,中间两位 11 表示班级,最后两位还是原来的编号 1 到 89。这个时候我们该如何存储选手信息,才能够支持通过编号来快速查找选手信息呢?

思路还是跟前面类似。尽管我们不能直接把编号作为数组下标,但我们可以截取参赛编号的后两位作为数组下标,来存取选手信息数据。当通过参赛编号查询选手信息的时候,我们用同样的方法,取参赛编号的后两位,作为数组下标,来读取数组中的数据。这就是典型的散列思想

其中,参赛选手的编号我们叫做键(key)或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散列函数(或“Hash 函数”“哈希函数”),而散列函数计算得到的值就叫作散列值(或“Hash 值”“哈希值”)。

通过这个例子,我们可以总结出这样的规律:散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。

三、散列函数

散列函数,顾名思义,它是一个函数。

我们可以把它定义成 hash(key),其中 key 表示元素的键值,hash(key) 的值表示经过散列函数计算得到的散列值。那第一个例子中,编号就是数组下标,所以 hash(key) 就等于 key。

改造后的例子,写成散列函数稍微有点复杂。我用伪代码将它写成函数就是下面这样:

 

int hash(String key) {
// 获取后两位字符
string lastTwoChars = key.substr(length-2, length);
// 将后两位字符转换为整数
int hashValue = convert lastTwoChas to int-type;
return hashValue;
}

刚刚举的学校运动会的例子,散列函数比较简单,也比较容易想到。但是,如果参赛选手的编号是随机生成的 6 位数字,又或者用的是 a 到 z 之间的字符串,该如何构造散列函数呢?

如何设计散列函数?(三点基本要求)

我总结了三点散列函数设计的基本要求:

  • 散列函数计算得到的散列值是一个非负整数;
  • 如果 key1 = key2,那 hash(key1) == hash(key2);
  • 如果 key1 ≠ key2,那 hash(key1) ≠ hash(key2)。(很难做到,几乎不可能,所以产生了散列冲突问题)

我来解释一下这三点。

其中,第一点理解起来应该没有任何问题。因为数组下标是从 0 开始的,所以散列函数生成的散列值也要是非负整数。

第二点也很好理解。相同的 key,经过散列函数得到的散列值也应该是相同的。

第三点理解起来可能会有问题,我着重说一下。这个要求看起来合情合理,但是在真实的情况下,要想找到一个不同的 key 对应的散列值都不一样的散列函数,几乎是不可能的。

即便像业界著名的MD5、SHA、CRC等哈希算法,也无法完全避免这种散列冲突。

而且,因为数组的存储空间有限,也会加大散列冲突的概率。所以我们几乎无法找到一个完美的无冲突的散列函数,即便能找到,付出的时间成本、计算成本也是很大的,所以针对散列冲突问题,我们需要通过其他途径来解决。

四、散列冲突(再好的散列函数也无法避免散列冲突,因此采用开放寻址发和链表法)

再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢?

我们常用的散列冲突解决方法有两类,开放寻址法(open addressing)链表法(chaining)。

1. 开放寻址法(线性探测,二次探测,双重探测)

开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

那如何重新探测新的位置呢?我先讲一个比较简单的探测方法,线性探测(Linear Probing)。当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。我说的可能比较抽象,我举一个例子具体给你说明一下。这里面黄色的色块表示空闲位置,橙色的色块表示已经存储了数据。

从图中可以看出,散列表的大小为 10,在元素 x 插入散列表之前,已经 6 个元素插入到散列表中。x 经过 Hash 算法之后,被散列到位置下标为 7 的位置,但是这个位置已经有数据了,所以就产生了冲突。

于是我们就顺序地往后一个一个找,看有没有空闲的位置,遍历到尾部都没有找到空闲的位置,于是我们再从表头开始找,直到找到空闲位置 2,于是将其插入到这个位置。

在散列表中查找元素的过程有点儿类似插入过程。我们通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素。如果相等,则说明就是我们要找的元素;否则就顺序往后依次查找。如果遍历到数组中的空闲位置,还没有找到,就说明要查找的元素并没有在散列表中。

散列表跟数组一样,不仅支持插入、查找操作,还支持删除操作。

对于使用线性探测法解决冲突的散列表,删除操作稍微有些特别。

我们不能单纯地把要删除的元素设置为空。这是为什么呢?还记得我们刚讲的查找操作吗?在查找的时候,一旦我们通过线性探测方法,找到一个空闲位置,我们就可以认定散列表中不存在这个数据。但是,如果这个空闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被认定为不存在。这个问题如何解决呢?我们可以将删除的元素,特殊标记为 deleted。当线性探测查找的时候,遇到标记为 deleted 的空间,并不是停下来,而是继续往下探测。

你可能已经发现了,线性探测法其实存在很大问题。

当散列表中插入的数据越来越多时,散列冲突发生的可能性就会越来越大,空闲位置会越来越少,线性探测的时间就会越来越久。极端情况下,我们可能需要探测整个散列表,所以最坏情况下的时间复杂度为 O(n)。

同理,在删除和查找时,也有可能会线性探测整张散列表,才能找到要查找或者删除的数据。

对于开放寻址冲突解决方法,除了线性探测方法之外,还有另外两种比较经典的探测方法,二次探测(Quadratic probing)双重散列(Double hashing)。

所谓二次探测,跟线性探测很像,线性探测每次探测的步长是 1,那它探测的下标序列就是 hash(key)+0,hash(key)+1,hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”,也就是说,它探测的下标序列就是 hash(key)+0,hash(key)+12,hash(key)+22……

所谓双重散列,意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key),hash2(key),hash3(key)……我们先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置。

 

装载因子

不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。

为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位。

我们用装载因子(load factor)来表示空位的多少。装载因子的计算公式是:散列表的装载因子=填入表中的元素个数/散列表的长度装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

 

2. 链表法

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个“桶(bucket)”或者“槽(slot)”会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。

插入操作

当插入的时候,我们只需要通过散列函数计算出对应的散列槽位,将其插入到对应链表中即可,所以插入的时间复杂度是 O(1)。

查找和删除操作

当查找、删除一个元素时,我们同样通过散列函数计算出对应的槽,然后遍历链表查找或者删除。

那查找或删除操作的时间复杂度是多少呢?实际上,这两个操作的时间复杂度跟链表的长度 k 成正比,也就是 O(k)。对于散列比较均匀的散列函数来说,理论上讲,k=n/m,其中 n 表示散列中数据的个数,m 表示散列表中“槽”的个数。

 

解答开篇

有了前面这些基本知识储备,我们来看一下开篇的思考题:

Word 文档中单词拼写检查功能是如何实现的?

常用的英文单词有 20 万个左右,假设单词的平均长度是 10 个字母,平均一个单词占用 10 个字节的内存空间,那 20 万英文单词大约占 2MB 的存储空间,就算放大 10 倍也就是 20MB。

对于现在的计算机来说,这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。当用户输入某个英文单词时,我们拿用户输入的单词去散列表中查找。

如果查到,则说明拼写正确;如果没有查到,则说明拼写可能有误,给予提示。借助散列表这种数据结构,我们就可以轻松实现快速判断是否存在拼写错误。

内容小结

今天我讲了一些比较基础、比较偏理论的散列表知识,包括散列表的由来、散列函数、散列冲突的解决方法。散列表来源于数组,它借助散列函数对数组这种数据结构进行扩展,利用的是数组支持按照下标随机访问元素的特性。散列表两个核心问题是散列函数设计和散列冲突解决。散列冲突有两种常用的解决方法,开放寻址法和链表法。散列函数设计的好坏决定了散列冲突的概率,也就决定散列表的性能。针对散列函数和散列冲突,今天我只讲了一些基础的概念、方法,下一节我会更贴近实战、更加深入探讨这两个问题。

课后思考

  1. 假设我们有 10 万条 URL 访问日志,如何按照访问次数给 URL 排序?
  2. 有两个字符串数组,每个数组大约有 10 万条字符串,如何快速找出两个数组中相同的字符串?

回答:

1. 假设我们有 10 万条 URL 访问日志,如何按照访问次数给 URL 排序?

遍历 10 万条数据,以 URL 为 key,访问次数为 value,存入散列表,同时记录下访问次数的最大值 K,时间复杂度 O(N)。

如果 K 不是很大,可以使用桶排序,时间复杂度 O(N)。如果 K 非常大(比如大于 10 万),就使用快速排序,复杂度 O(NlogN)。

2. 有两个字符串数组,每个数组大约有 10 万条字符串,如何快速找出两个数组中相同的字符串?

以第一个字符串数组构建散列表,key 为字符串,value 为出现次数。再遍历第二个字符串数组,以字符串为 key 在散列表中查找,如果 value 大于零,说明存在相同字符串。时间复杂度 O(N)。

0 40

好久之前就了解过动态数组了,这次自己来实现一个。

先上代码

    /**
     * 实现一个动态数组
     *
     * @author 杨深建
     */
public class ArrayImpl<T> implements ArrayInterface<T> {

    private int size; // 表示的是数组的大小
    private T[] data; // 定义一个数组

    public ArrayImpl(int capciaty) {
        data = (T[]) new Object[capciaty]; // 创建一个数组
        size = 0;
    }

    public ArrayImpl() {
        this(10);
    }

    /**
     * 获取数组的容量
     *
     * @return
     */
    @Override
    public int getCapciaty() {
        return data.length;
    }

    /**
     * 获取数组的大小
     *
     * @return
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判断数组是否为空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 向数组的指定位置添加元素。
     *
     * @param index
     * @param element
     */
    @Override
    public void add(int index, T element) {
        // 1、判断index 是否合法。
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        // 2、判断是否为满
        if (size == data.length) {
            resize(size*2);  //进行扩容操作
        }
        // 3、进行插入操作,数据迁移
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        // 4、进行赋值插入
        data[index] = element;
        // 5、元素个数加1
        size++;
    }

    /**
     * 进行扩容操作
     * @param i
     */
    private void resize(int index) {
        T  [] data2=(T[]) new  Object[index];
        for(int i=0;i<size;i++){  //进行赋值操作
            data2[i]=data[i];
        }
        data=data2;
    }

    /**
     * 在数组的头部插入元素
     */
    @Override
    public void addFirst(T element) {
        add(0, element);
    }

    /**
     *
     * 在数组中的尾部插入元素
     */
    @Override
    public void addLast(T element) {
        add(size, element);
    }

    /**
     * 获取index索引位置的元素
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        // 1、判断index 是否合法。
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        return data[index];
    }

    /**
     * 修改index索引位置的元素为e
     *
     * @param index
     * @param element
     */
    @Override
    public void set(int index, T element) {
        // 1、判断index 是否合法。
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        data[index] = element;
    }

    /**
     * 显示所有的数组元素
     */
    @Override
    public void print() {
        for (int i = 0; i < size; i++) {
            System.out.println(data[i]);
        }
    }

    /**
     * 查找数组中是否有元素e
     */
    @Override
    public boolean contains(T e) {
        for (int i = 0; i < size; i++) {
            if (e.equals(data[i])) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
     */
    @Override
    public int find(T e) {
        for (int i = 0; i < size; i++) {
            if (e.equals(data[i])) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 从数组中删除index位置的元素, 返回删除的元素
     */
    @Override
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        T res = data[index]; // 获取结果
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i]; // data[index]
        }
        size--;  //进行元素个数-1
        if(size == data.length/4 && data.length/2!=0)  resize(data.length/2);  //如果元素的个数小于容量的1/4 ,我们就进行缩容操作 到容量的1/2
        return res;
    }

    /**
     * 从数组中删除第一个元素, 返回删除的元素
     */
    @Override
    public T removeFirst() {
        T res = remove(0);
        return res;
    }

    /**
     * 从数组中删除最后一个元素, 返回删除的元素
     */

    @Override
    public T removeLast() {
        T res = remove(size - 1);
        return res;
    }

    /**
     * 从数组中删除元素e
     */
    @Override
    public void removeElement(T element) {
        int index = find(element);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public String toString() {
        //使用 线程不安全的StringBuilder 效率更高
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }
}


说明:我所采用的是for循环复制元素扩容,但这种扩容是有一些问题的
缺陷: 拷贝一部分元素需要计算索引,比较复杂
2.System.arraycopy()
3.Arrays.copyOf扩容

* 观察copyOf方法的源码:

* public static int[] copyOf(int[] original, int newLength) {

* int[] copy = new int[newLength];

* System.arraycopy(original, 0, copy, 0,

* Math.min(original.length, newLength));

* return copy;

* }

4.利用Object类中一个 clone 方法,该方法是真正意义上的复制数组(默认浅拷贝,如果覆写则是深拷贝)

复杂度的震荡

当同时思考addLast和removeLast操作的时候:

假如调用addLast触发resize扩容后调用removeLast显然也会调用resize进行缩容,这个操作如果反复执行就会导致复杂度的震荡,所以代码中removeLast方法中,并没有像addLast中那样直接让data.length/2,而是当数组内的元素等于四分之一容量的时候,才会执行缩容的操作,就可以解决复杂度的震荡

if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

0 60

说到数组,我一向自认为熟知其概念,操作,特性,但是最近看到的一个问题却把我难住了,那就是,为什么数组下标从0开始而不是从1开始?

带着这个疑问,结合王争老师的《数据结构与算法》来重新剖析数组这种数据结构

 

如何实现随机访问?

一、为什么数组可以实现随机访问(1.线性表 2.连续空间春初相同类型的数据)

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据

这个定义里有几个关键词,理解了这几个关键词,我想你就能彻底掌握数组的概念了。

第一是线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。

其实除了数组,链表、队列、栈等也是线性表结构。而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

第二个是连续的内存空间和相同类型的数据。

正是因为这两个限制,它才有了一个堪称“杀手锏”的特性:“随机访问”。但有利就有弊,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

数组的两个限制分别为:

  1. 线性表
  2. 连续的内存空间和相同类型的数据

 

二、数组是如何实现根据下标随机访问数组元素的?(原理  内存偏移公式)

我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10]来举例。

在我画的这个图中,计算机给数组 a[10],分配了一块连续内存空间 1000~1039,其中,内存块的首地址为 base_address = 1000。我们知道,计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:a[i]_address = base_address + i * data_type_size其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里,数组中存储的是 int 类型数据,所以 data_type_size 就为 4 个字节。这个公式非常简单,我就不多做解释了。

三、数组的查找时间复杂度为O(1)吗?

我在面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为O(1)

 

数组的低效插入和删除(低效均是因为数据偏移)

插入操作

假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢?你可以自己先试着分析一下。如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为 O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是 O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。

插入操作的时间复杂度应该区分数组中的数据是否有序(二者可以采取的策略不同)

如果数组中的数据是有序的,我们在某个位置插入一个新的元素时,就必须按照刚才的方法搬移 k 之后的数据。

但是,如果数组中存储的数据并没有任何规律,数组只是被当作一个存储数据的集合。在这种情况下,如果要将某个数据插入到第 k 个位置,为了避免大规模的数据搬移,我们还有一个简单的办法就是,直接将第 k 位的数据搬移到数组元素的最后,把新的元素直接放入第 k 个位置。为了更好地理解,我们举一个例子。假设数组 a[10]中存储了如下 5 个元素:a,b,c,d,e。我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5],将 a[2]赋值为 x 即可。最后,数组中的元素如下: a,b,x,d,e,c。

在这种特定情况下,即数据无序,插入第K位的元素,时间复杂度可以降低到O(1),此思想在快速排序中也会用到!!!

 

删除操作

删除操作为什么要数据迁移?(避免出现空洞)

删除操作搬移数据是为了避免出现空洞!

跟插入数据类似,如果我们要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为 O(1);如果删除开头的数据,则最坏情况时间复杂度为 O(n);平均情况时间复杂度也为 O(n)。

如何提高删除效率?(先标记,再删除,减少数据迁移的次数,与JVM垃圾回收机制相似)

实际上,在某些特殊场景下,我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行,删除的效率是不是会提高很多呢?我们继续来看例子。数组 a[10]中存储了 8 个元素:a,b,c,d,e,f,g,h。现在,我们要依次删除 a,b,c 三个元素。

为了避免 d,e,f,g,h 这几个数据会被搬移三次,我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据,只是记录数据已经被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。

如果你了解 JVM,你会发现,这不就是 JVM 标记清除垃圾回收算法的核心思想吗?没错,数据结构和算法的魅力就在于此,很多时候我们并不是要去死记硬背某个数据结构或者算法,而是要学习它背后的思想和处理技巧,这些东西才是最有价值的。如果你细心留意,不管是在软件开发还是架构设计中,总能找到某些算法和数据结构的影子。

警惕数组的访问越界问题

在Java语言中,当数组出现越界时,会出现异常 在c语言中,数组出现越界时,一样可以访问;ArrayIndexOutOfBoundsException 属于 运行期错误,而不属于编译期错误.

 

容器能否完全替代数组?

针对数组类型,很多语言都提供了容器类,比如 Java 中的 ArrayList、C++ STL 中的 vector。

在项目开发中,什么时候适合用数组,什么时候适合用容器呢?

这里我拿 Java 语言来举例。如果你是 Java 工程师,几乎天天都在用 ArrayList,对它应该非常熟悉。那它与数组相比,到底有哪些优势呢?我个人觉得,ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外,它还有一个优势,就是支持动态扩容

数组本身在定义的时候需要预先指定大小,因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组,当第 11 个数据需要存储到数组中时,我们就需要重新分配一块更大的空间,将原来的数据复制过去,然后再将新的数据插入。

如果使用 ArrayList,我们就完全不需要关心底层的扩容逻辑,ArrayList 已经帮我们实现好了。每次存储空间不够的时候,它都会将空间自动扩容为 1.5 倍大小。(JDK1.8,初始大小为10个)

不过,这里需要注意一点,因为扩容操作涉及内存申请和数据搬移,是比较耗时的。

使用ArrayList如果能事先确定数据大小能省掉很多次的内存申请和数据迁移操作

所以,如果事先能确定需要存储的数据大小,最好在创建 ArrayList 的时候事先指定数据大小。比如我们要从数据库中取出 10000 条数据放入 ArrayList。我们看下面这几行代码,你会发现,相比之下,事先指定数据大小可以省掉很多次内存申请和数据搬移操作。

 

容器和数组对比总结(极致性能则使用数组,否则使用容器)

1.Java ArrayList 无法存储基本类型,比如 int、long,需要封装为 Integer、Long 类,而 Autoboxing、Unboxing 则有一定的性能消耗,所以如果特别关注性能,或者希望使用基本类型,就可以选用数组。自动拆箱,装箱需要读写内存,而基本数据类型只需要使用寄存器,寄存器比内存快一个级别)

2. 如果数据大小事先已知,并且对数据的操作非常简单,用不到 ArrayList 提供的大部分方法,也可以直接使用数组。3. 还有一个是我个人的喜好,当要表示多维数组时,用数组往往会更加直观。比如 Object[][] array;而用容器的话则需要这样定义:ArrayList<arraylist

我总结一下,对于业务开发,直接使用容器就足够了,省时省力。毕竟损耗一丢丢性能,完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发,比如开发网络框架,性能的优化需要做到极致,这个时候数组就会优于容器,成为首选。

 

解答开篇(1.根据内存偏移计算公式,从1开始要多做一次减法 2.历史原因)

现在我们来思考开篇的问题:为什么大多数编程语言中,数组要从 0 开始编号,而不是从 1 开始呢?

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。前面也讲到,如果用 a 来表示数组的首地址,a[0]就是偏移为 0 的位置,也就是首地址,a[k]就表示偏移 k 个 type_size 的位置,所以计算 a[k]的内存地址只需要用这个公式:a[k]_address = base_address + k * type_size但是,如果数组从 1 开始计数,那我们计算数组元素 a[k]的内存地址就会变为:a[k]_address = base_address + (k-1)*type_size对比两个公式,我们不难发现,从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。

数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是从 1 开始。不过我认为,上面解释得再多其实都算不上压倒性的证明,说数组起始编号非 0 开始不可。

所以我觉得最主要的原因可能是历史原因。C 语言设计者用 0 开始计数数组下标,之后的 Java、JavaScript 等高级语言都效仿了 C 语言,或者说,为了在一定程度上减少 C 语言程序员学习 Java 的学习成本,因此继续沿用了从 0 开始计数的习惯。实际上,很多语言中数组也并不是从 0 开始计数的,比如 Matlab。甚至还有一些语言支持负数下标,比如 Python。