Home 数据结构

0 13

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

一、带着问题去学习

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 17

队列是非常重要的数据结构,在许多模型或者架构中都能看到它的身影,今天就要仔细解剖一下它吧~

 

一、带着问题去学习

我们知道,CPU 资源是有限的,任务的处理速度与线程个数并不是线性正相关。

相反,过多的线程反而会导致 CPU 频繁切换,处理性能下降。

所以,线程池的大小一般都是综合考虑要处理任务的特点和硬件环境,来事先设置的。当我们向固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又是怎么实现的呢?

二、怎么理解“队列”?

想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。

 

特性:

先进者先出,这就是典型的“队列”。

我们知道,栈只支持两个基本操作:入栈 push()和出栈 pop()。队列跟栈非常相似,支持的操作也很有限,

 

最基本的操作也是两个:

  • 入队 enqueue(),放一个数据到队列尾部;
  • 出队 dequeue(),从队列头部取一个元素。

队列,也是一种操作受限的线性表数据结构(只允许在队尾插入,队头删除)

应用场景:

循环队列,阻塞队列,并发队列等等

 

三、队列的两种实现方式(顺序队列(数组实现),链式队列(链表实现))

队列是抽象的数据结构,跟栈一样,其实现也有两种方式:数组实现和链表实现

顺序队列随着入队出队会产生的问题(队列未满却无法添加)

当不停的入队,出队操作,head和tail都会持续往后移动。当tail移动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据

类似问题:数组中的删除操作会导致数组中的数据不连续,解决办法是数据搬移(即移动数组中的元素)

在队列中每次出队操作都相当于删除数组下标为0的数据,要搬移整个队列的数组,出队的时间复杂度就会从O(1)上升到O(n),怎么进行优化呢?

思路:减少数据搬移的次数(进一步思考,出队时不用搬移空间;如果没有空闲空间了,在入队时,集中触发一次数据的搬移操作即可)


搬移过程:

 

四、循环队列

在使用数组实现队列的时候,当tail == n时,会友数据搬移操作,这样入队操作性能就会受到影响,那么有无办法去避免数据搬移?

循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相连,扳成了一个环。

图中这个队列的大小为 8,当前 head=4,tail=7。当有一个新的元素 a 入队时,我们放入下标为 7 的位置。但这个时候,我们并不把 tail 更新为 8,而是将其在环中后移一位,到下标为 0 的位置。当再有一个元素 b 入队时,我们将 b 放入下标为 0 的位置,然后 tail 加 1 更新为 1。所以,在 a,b 依次入队之后,循环队列中的元素就变成了下面的样子:

通过这样的方法,我们成功避免了数据搬移操作。看起来不难理解,但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有 bug 的循环队列的实现代码,我个人觉得,最关键的是,确定好队空和队满的判定条件。

 

循环队列的判空条件:队列为空的判断条件仍然是 head == tail。

循环队列的判满条件:队列为满的判断条件是  (tail + 1 )%n == head   –> ( 3 + 1)%8 = 4;

循环队列的指针移动:tail = (tail + 1)% n;

 

当队列满时,图中的 tail 指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。(tail指向下一个插入的位置) 如果不浪费的话,无法区别是队列满了还是队列为空,即变为 head == tail

 

五、阻塞队列、并发队列

阻塞队列:在队列基础上增加了阻塞操作

并发队列:线程安全的队列

 

六、解答开篇

队列的知识就讲完了,我们现在回过来看下开篇的问题。线程池没有空闲线程时,新的任务请求线程资源时,线程池该如何处理?各种处理策略又是如何实现的呢?我们一般有两种处理策略。

第一种是非阻塞的处理方式,直接拒绝任务请求;

另一种是阻塞的处理方式,将请求排队,等到有空闲线程时,取出排队的请求继续处理。

那如何存储排队的请求呢?我们希望公平地处理每个排队的请求,先进者先服务,所以队列这种数据结构很适合来存储排队请求。我们前面说过,队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢?基于链表的实现方式,可以实现一个支持无限排队的无界队列(unbounded queue),但是可能会导致过多的请求排队等待,请求处理的响应时间过长。所以,针对响应时间比较敏感的系统,基于链表实现的无限排队的线程池是不合适的。而基于数组实现的有界队列(bounded queue),队列的大小有限,所以线程池中排队的请求超过队列大小时,接下来的请求就会被拒绝,这种方式对响应时间敏感的系统来说,就相对更加合理。不过,设置一个合理的队列大小,也是非常有讲究的。队列太大导致等待的请求太多,队列太小会导致无法充分利用系统资源、发挥最大性能。除了前面讲到队列应用在线程池请求排队的场景之外,队列可以应用在任何有限资源池中,用于排队请求,比如数据库连接池等。实际上,对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排队。

0 20

如何理解栈?

后进者先出,先进者后出,这就是典型的“栈”结构。

操作特性:栈是一种操作受限的数据结构,只允许在一端插入和删除数据。从功能上来说,数组或链表确实可以替代栈,但你要知道,特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,这时我们就应该首选“栈”这种数据结构。

 

如何实现一个栈?

两种数据操作:(入栈,出栈)

栈主要包含两个操作:入栈,出栈

 

两种实现方式:(顺序栈,链式栈)

栈既可以用数组来实现,也可以用链表来实现。

用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈。

 

时间复杂度和空间复杂度(O(1),O(1),注:均摊复杂度一般等于最好复杂度)

不管是顺序栈还是链式栈,我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)。注意,这里存储数据需要一个大小为 n 的数组,并不是说空间复杂度就是 O(n)。因为,这 n 个空间是必须的,无法省掉。所以我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。空间复杂度分析是不是很简单?时间复杂度也不难。不管是顺序栈还是链式栈,入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度都是 O(1)。

 

支持动态扩容的顺序栈(底层用支持动态扩容的数组即可)

我们在数组那一节,是如何来实现一个支持动态扩容的数组的吗?当数组空间不够时,我们就重新申请一块更大的内存,将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组。所以,如果要实现一个支持动态扩容的栈,我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后,我们就申请一个更大的数组,将原来的数据搬移到新数组中。我画了一张图,你可以对照着理解一下。

 

栈在函数调用中的应用

我们知道,操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。为了让你更好地理解,我们一块来看下这段代码的执行过程。

int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf(“%d”, res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
从代码中我们可以看出,main() 函数调用了 add() 函数,获取计算结果,并且与临时变量 a 相加,最后打印 res 的值。为了让你清晰地看到这个过程对应的函数栈里出栈、入栈的操作,我画了一张图。图中显示的是,在执行到 add() 函数时,函数调用栈的情况

栈在表达式求值中的应用

我们再来看栈的另一个常见的应用场景,编译器如何利用栈来实现表达式求值。

为了方便解释,我将算术表达式简化为只包含加减乘除四则运算,比如:34+13*9+44-12/3。对于这个四则运算,我们人脑可以很快求解出答案,但是对于计算机来说,理解这个表达式本身就是个挺难的事儿。如果换作你,让你来实现这样一个表达式求值的功能,你会怎么做呢?

实际上,编译器就是通过两个栈来实现的。

其中一个保存操作数的栈,另一个是保存运算符的栈。

我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。我将 3+5*8-6 这个表达式的计算过程画成了一张图,你可以结合图来理解我刚讲的计算过程。

 

栈在括号匹配中的应用

除了用栈来实现表达式求值,我们还可以借助栈来检查表达式中的括号是否匹配。我们同样简化一下背景。我们假设表达式中只包含三种括号,圆括号 ()、方括号[]和花括号{},并且它们可以任意嵌套。比如,{[] ()[{}]}或[{()}([])]等都为合法格式,而{[}()]或[({)]为不合法的格式。那我现在给你一个包含三种括号的表达式字符串,如何检查它是否合法呢?

这里也可以用栈来解决。我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配,则继续扫描剩下的字符串。

如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式。

 

内容小结

栈是一种操作受限的数据结构,只支持入栈和出栈操作。

后进先出是它最大的特点。

栈既可以通过数组实现,也可以通过链表来实现。

不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。

除此之外,我们还讲了一种支持动态扩容的顺序栈,你需要重点掌握它的均摊时间复杂度分析方法。

课后思考我们在讲栈的应用时,讲到用函数调用栈来保存临时变量,为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?我们都知道,JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用,堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢?如果不是,那它为什么又叫作“栈”呢?

其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,是最顺理成章的选择。

从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。

0 15

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

先上代码

    /**
     * 实现一个动态数组
     *
     * @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 15

链表,做过不少题,包括反转,相交链表等,这次就来试试实现一个LRU缓存淘汰算法吧(最近最少使用算法)

内容整理来自与极客时间

链表的经典使用场景:LRU缓存淘汰算法

先来了解一下缓存

一、 缓存是什么?(空间换时间的思想)

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

二、 为什么需要缓存淘汰策略?

缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。

三、常见的缓存策略有哪些?

常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)


接下来是链表部分

一、 链表与数组对比

我们先从底层的存储结构上来看一看。为了直观地对比,我画了一张图。

从图中我们看到,数组需要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个 100MB 大小的数组当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于 100MB,仍然会申请失败

而链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,所以如果我们申请的是 100MB 大小的链表,根本不会有问题。

二、 常见的三种链表结构(单链表,双向链表,循环链表)

和单链表相比,循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时,就特别适合采用循环链表。比如著名的约瑟夫问题。尽管用单链表也可以实现,但是用循环链表实现的话,代码就会简洁很多。从我画的图中可以看出来,双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。那相比单链表,双向链表适合解决哪种问题呢?从结构上来看,双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

链表的插入和删除操作的时间复杂度真的是O(1)吗?有哪些先决条件呢?

我们先来看删除操作。

一、 删除操作(删除某个值,则一样需要遍历;删除某个给定指针指向的结点,双向链表不需要遍历更高效)

在实际的软件开发中,从链表中删除一个数据无外乎这两种情况:

  1. 删除结点中“值等于某个给定值”的结点;(这种情况单链表和双向链表一样O(n))
  2. 删除给定指针指向的结点。(要删除某个结点,需要知道其前结点,双向链表拥有前指针,更高效;即单链表仍需要遍历找到前驱结点O(n),而双向链表只需要O(1))

对于第一种情况,不管是单链表还是双向链表,为了查找到值等于给定值的结点,都需要从头结点开始一个一个依次遍历对比,直到找到值等于给定值的结点,然后再通过我前面讲的指针操作将其删除。尽管单纯的删除操作时间复杂度是 O(1),但遍历查找的时间是主要的耗时点,对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则,删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

对于第二种情况,我们已经找到了要删除的结点,但是删除某个结点 q 需要知道其前驱结点,而单链表并不支持直接获取前驱结点,所以,为了找到前驱结点,我们还是要从头结点开始遍历链表,直到 p->next=q,说明 p 是 q 的前驱结点。

但是对于双向链表来说,这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历。所以,针对第二种情况,单链表删除操作需要 O(n) 的时间复杂度,而双向链表只需要在 O(1) 的时间复杂度内就搞定了!

同理,如果我们希望在链表的某个指定结点前面插入一个结点,双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定,而单向链表需要 O(n) 的时间复杂度。你可以参照我刚刚讲过的删除操作自己分析一下。

二、 链表如果有序,双向链表的查询也比单链表更高效,思想与二分查找类似

除了插入、删除操作有优势之外,对于一个有序链表,双向链表的按值查询的效率也要比单链表高一些。因为,我们可以记录上次查找的位置 p,每次查询时,根据要查找的值与 p 的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。

现在,你有没有觉得双向链表要比单链表更加高效呢?这就是为什么在实际的软件开发中,双向链表尽管比较费内存,但还是比单链表的应用更加广泛的原因。如果你熟悉 Java 语言,你肯定用过 LinkedHashMap 这个容器。如果你深入研究 LinkedHashMap 的实现原理,就会发现其中就用到了双向链表这种数据结构。

实际上,这里有一个更加重要的知识点需要你掌握,那就是用空间换时间的设计思想。当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反,如果内存比较紧缺,比如代码跑在手机或者单片机上,这个时候,就要反过来用时间换空间的设计思路。

还是开篇缓存的例子。缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上,会比较节省内存,但每次查找数据都要询问一次硬盘,会比较慢。但如果我们通过缓存技术,事先将数据加载在内存中,虽然会比较耗费内存空间,但是每次数据查询的速度就大大提高了。所以我总结一下,对于执行较慢的程序,可以通过消耗更多的内存(空间换时间)来进行优化;而消耗过多内存的程序,可以通过消耗更多的时间(时间换空间)来降低内存的消耗。

 

链表和数组性能对比(内存紧张则使用数组)

大纲:查找效率更高的是数组,插删效率更高的是链表,但是链表天然支持动态扩容,而容器尽管也可以扩容,但需要做数据拷贝(费时),链表占用空间更大,内存紧张使用数组

从JVM角度来说:

数组声明需要申请一块连续的内存空间,如果系统的内存空间不足则会申请失败,但是在垃圾回收阶段,数组可以采用标记后集中回收,减少垃圾回收次数,减少耗时; 链表在内存中不是连续存储,可以动态的增加内存空间,但链表的内存消耗相对于数组是翻倍的(多了一份指向下一个节点的指针),而且对链表频繁的插入,删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,导致频繁的垃圾回收。

数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。

而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。

数组的缺点是大小固定,一经声明就要占用整块连续内存空间。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致“内存不足(out of memory)”。如果声明的数组过小,则可能出现不够用的情况。这时只能再申请一个更大的内存空间,把原数组拷贝进去,非常费时。

链表本身没有大小的限制,天然地支持动态扩容,我觉得这也是它与数组最大的区别。你可能会说,我们 Java 中的 ArrayList 容器,也可以支持动态扩容啊?我们上一节课讲过,当我们往支持动态扩容的数组中插入一个数据时,如果数组中没有空闲空间了,就会申请一个更大的空间,将数据拷贝过去,而数据拷贝的操作是非常耗时的。我举一个稍微极端的例子。如果我们用 ArrayList 存储了了 1GB 大小的数据,这个时候已经没有空闲空间了,当我们再插入数据的时候,ArrayList 会申请一个 1.5GB 大小的存储空间,并且把原来那 1GB 的数据拷贝到新申请的空间上。听起来是不是就很耗时?

解答开篇

好了,关于链表的知识我们就讲完了。

我们现在回过头来看下开篇留给你的思考题。如何基于链表实现 LRU 缓存淘汰算法?

我的思路是这样的:(创建一个有序单链表,当有一个新的数据被访问时,从链表头开始遍历链表,如果已存在,则删除再插入到头,如果不存在,判断链表是否满了,没满直接插入头部,满了则先删除链表尾结点,再将新结点插入到头)

我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。

当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2.  如果此数据没有在缓存链表中,又可以分为两种情况:
  • 如果此时缓存未满,则将此结点直接插入到链表的头部;
  • 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

这样我们就用链表实现了一个 LRU 缓存,是不是很简单?现在我们来看下缓存访问的时间复杂度是多少。因为不管缓存有没有满,我们都需要遍历一遍链表,所以这种基于链表的实现思路,缓存访问的时间复杂度为 O(n)。实际上,我们可以继续优化这个实现思路,比如引入散列表(Hash table)来记录每个数据的位置,将缓存访问的时间复杂度降到 O(1)。因为要涉及我们还没有讲到的数据结构,所以这个优化方案,我现在就不详细说了,等讲到散列表的时候,我会再拿出来讲。除了基于链表的实现思路,实际上还可以用数组来实现 LRU 缓存淘汰策略。如何利用数组实现 LRU 缓存淘汰策略呢?我把这个问题留给你思考。

 

补充:“数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。”

CPU在从内存读取数据的时候,会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址,而是读取一个数据块(这个大小我不太确定。。)并保存到CPU缓存中,然后下次访问内存数据的时候就会先从CPU缓存开始查找,如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制,也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。

对于数组来说,存储空间是连续的,所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。

0 15

说到数组,我一向自认为熟知其概念,操作,特性,但是最近看到的一个问题却把我难住了,那就是,为什么数组下标从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。

0 28

队列,也是一种线性表,它的特性是先进先出,插入在一端,删除在另一端。就像排队一样,队(push)要排在队尾(rear),每次出队(pop)的都是队首(front)的人

队列与栈一样,是一种线性存储结果,它具有如下特点:

  1. 队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构。
  2. 在队尾(移动rear指针)添加元素,在队头(移动front指针)删除元素

1.2 队列相关概念

  1. 队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头。
  2. 入队:队列的插入操作。(push)
  3. 出队:队列的删除操作。(pop)

依次入队:{1,2,3}

入队时,元素只能从队尾一端进入队列,即2只能跟在1的后面,3只能跟在2的后面

依次出队:先进先出

元素只能从队首出队列,出队列的顺序为:1、2、3,与入队时的顺序一致,这就是所谓的“先进先出”。

1.3 队列的种类

单向队列

单向队列只能在队尾添加数据,在队首移除数据,是最简单的队列。

双端队列(deque)

双端队列是一种具有队列和栈性质的抽象数据类型,它可以在队尾、队首添加和移除数据,

优先队列(Priority queue)

优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。

循环队列 (克服假溢出现象)

为充分利用向量空间,克服”假溢出“现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在实际编程应用中来实现。

消除假溢出就是当队尾指针rear和队头指针front到达存储空间最大值QueueSize时,让队尾指针自动转化为存储空间的最小值0.

但是循环队列带来了新问题—front==rear 的二义性

在循环队列中,空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性

front==rear 二义性解决办法(三种):

1. 加设标志位,让删除动作使其为1,插入动作使其为0, 则可识别当前front == rear;
2. 使用一个计数器记录队列中元素个数(即队列长度)
3. 人为浪费一个单元,令队满特征为 front = (rear +1)%N—空闲单元法

空闲单元法:

1.4 队列的实现(Javascript)

class Queue {
  constructor(...items) {
    this.queue = [];
    this.enqueue(...items);
  }

  enqueue(...items) {
    items.forEach(item => this.queue.push(item));
    return this.queue;
  }

  dequeue(count = 1) {
    this.queue.splice(0, count);
    return this.queue;
  }

  peek() {
    return this.queue[0];
  }

  size() {
    return this.queue.length;
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

1.5 队列的应用

广泛应用在各种 广度优先搜索(Breadth-First-Search)中。

1.6 队列的操作

队列通常提供的操作:

  1. 入队: 通常命名为push()
  2. 出队: 通常命名为pop()
  3. 求队列中元素个数size()
  4. 判断队列是否为空isEmpty()
  5. 获取队首元素但不删除peek()

1.4 队列的存储结构

队列与栈一样是一种线性结构,因此以常见的线性表如数组、链表作为底层的数据结构。
本文中,我们以数组、链表为底层数据结构构建队列。

2.基于数组的循环队列实现

以数组作为底层数据结构时,一般讲队列实现为循环队列(为了解决队列假溢出)。这是因为队列在顺序存储上的不足:每次从数组头部删除元素(出队)后,需要将头部以后的所有元素往前移动一个位置,这是一个时间复杂度为O(n)的操作:3 队列假溢出

原因:

出队时,把队首标志往后移动不就不用移动元素了,的确,但那样会造成数组空间的“流失”。

解决办法:

我们希望队列的插入与删除操作都是O(1)的时间复杂度,同时不会造成数组空间的浪费,我们应该使用循环队列。
所谓的循环队列,可以把数组看出一个首尾相连的圆环,删除元素时将队首标志往后移动,添加元素时若数组尾部已经没有空间,则考虑数组头部的空间是否空闲,如果是,则在数组头部进行插入。

前言

今天介绍一下Java的两个集合类,ArrayList和LinkedList,这两个集合的知识点几乎可以说面试必问的。

对于这两个集合类,相信大家都不陌生,ArrayList可以说是日常开发中用的最多的工具类了,也是面试中几乎必问的,LinkedList可能用的少点,但大多数的面试也会有所涉及,尤其是关于这两者的比较可以说是家常便饭,所以,无论从使用上还是在面试的准备上,对于这两个类的知识点我们都要有足够的了解。

ArrayList

ArrayList是List接口的一个实现类,底层是基于数组实现的存储结构,可以用于装载数据,数据都是存放到一个数组变量中,

transient Object[] elementData;

transient是一个关键字,它的作用可以总结为一句话:将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会被序列化。 你可能会觉得奇怪,ArrayList可以被序列化的啊,源码可是实现了java.io.Serializable接口啊,为什么数组变量还要用transient定义呢?

别急,关于这个问题,我们后面会讨论到,不卖个关子,你们怎么会看到最后,然后给我点在看呢?

当我们新建一个实例时,ArrayList会默认帮我们初始化数组的大小为10(补充:1.8之后,新建实例并没有初始化为10。只有通过无参构造,添加第一个元素的时候才会扩容到10。)

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

但请注意,这个只是数组的容量大小,并不是List真正的大小,List的大小应该由存储数据的数量决定,在源码中,获取真实的容量其实是用一个变量size来表示,

private int size;

在源码中,数据默认是从数组的第一个索引开始存储的,当我们添加数据时,ArrayList会把数据填充到上一个索引的后面去,所以,ArrayList的数据都是有序排列的。而且,由于ArrayList本身是基于数组存储,所以查询的时候只需要根据索引下标就可以找到对于的元素,查询性能非常的高,这也是我们非常青睐ArrayList的最重要的原因。

但是,数组的容量是确定的啊,如果要存储的数据大小超过了数组大小,那不就有数组越界的问题?

关于这点,我们不用担心,ArrayList帮我们做了动态扩容的处理,如果发现新增数据后,List的大小已经超过数组的容量的话,就会新增一个为原来1.5倍容量的新数组,然后把原数组的数据原封不动的复制到新数组中,再把新数组赋值给原来的数组对象就完成了。

扩容之后,数组的容量足够了,就可以正常新增数据了。

除此之外,ArrayList提供支持指定index新增的方法,就是可以把数据插入到设定的索引下标,比如说我想把元素4插入到3后面的位置,也就是现在5所在的地方,

插入数据的时候,ArrayList的操作是先把3后面的数组全部复制一遍,然后将这部分数据往后移动一位,其实就是逐个赋值给后移一位的索引位置,然后3后面就可以空出一个位置,把4放入就完成了插入数据的操作了

删除的时候也是一样,指定index,然后把后面的数据拷贝一份,并且向前移动,这样原来index位置的数据就删除了。

到这里我们也不难发现,这种基于数组的查询虽然高效,但增删数据的时候却很耗性能,因为每增删一个元素就要移动对应index后面的所有元素,数据量少点还无所谓,但如果存储上千上万的数据就很吃力了,所以,如果是频繁增删的情况,不建议用ArrayList。

既然ArrayList不建议用的话,这种情况下有没有其他的集合可用呢?

当然有啊,像我这样的暖男肯定是第一时间告诉你们的,这就引出了我们下面要说的LinkedList

LinkedList

LinkedList 是基于双向链表实现的,不需要指定初始容量,链表中任何一个存储单元都可以通过向前或者向后的指针获取到前面或者后面的存储单元。在 LinkedList 的源码中,其存储单元用一个Node类表示:

private static class Node<E> {
    E item;
    Node<E> next;       
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Node中包含了三个成员,分别是存储数据的item,指向前一个存储单元的点 prev 和指向后一个存储单元的节点 next ,通过这两个节点就可以关联前后的节点,组装成为链表的结构,

因为有保存前后节点的地址,LinkedList增删数据的时候不需要像ArrayList那样移动整片的数据,只需要通过引用指定index位置前后的两个节点即可,比如我们要在李白和韩信之间插入孙悟空的节点,只需要像这样处理下节点之间的指向地址:

删除数据也是同样原理,只需要改变index位置前后两个节点的指向地址即可。

这样的链表结构使得LinkedList能非常高效的增删数据,在频繁增删的情景下能很好的使用,但不足之处也是有的。

虽然增删数据很快,但查询就不怎么样了,LinkedList是基于双向链表存储的,当查询对应index位置的数据时,会先计算链表总长度一半的值,判读index是在这个值的左边还是右边,然后决定从头结点还是从尾结点开始遍历,

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

虽然根据index位置做了查询优化,但依然会有遍历一半链表长度的情况,如果是数据量非常多的话,这样的查询无疑是非常慢的。

这也是LinkedList最无奈的地方,鱼和熊掌不可兼得,我们既想查的快,又想增删快,这样的好事怎么可能都让我们遇到呢?所以,一般建议LinkedList使用于增删多,查询少的情景。

除此之外,LinkedList对内存的占用也是比较大的,毕竟每个Node都维护着前后指向地址的节点,数据量大的话会占用不少内存空间。

两者哪个更占空间?

讲到这,你是不是对标题的那个问题成竹在胸了?

下次有面试官问你,ArrayList和LinkedList哪个更占空间时,你就可以信誓旦旦的说,LinkedList更占空间,我看了薛大佬的文章,肯定不会错。说完你就可以安心坐着,等待面试官露出满意的笑容,告诉你通过面试的消息,成功拿下offer指日可待。

如果你真的这么答的话,我也相信面试官一定会被你的回答所征服,他听完一定会点点头,嘴角开始上扬,然后笑容满面的告诉你,

感谢你今天过来面试,你可以回去等通知了。。。。

哈哈,开个玩笑,不凑多点字可不是我的风格。

言归正传,表面上看,LinkedList的Node存储结构似乎更占空间,但别忘了前面介绍ArrayList扩容的时候,它会默认把数组的容量扩大到原来的1.5倍的,如果你只添加一个元素的话,那么会有将近原来一半大小的数组空间被浪费了,如果原先数组很大的话,那么这部分空间的浪费也是不少的,

所以,如果数据量很大又在实时添加数据的情况下,ArrayList占用的空间不一定会比LinkedList空间小,这样的回答就显得谨慎些了,听上去也更加让人容易认同,但你以为这样回答就完美了吗?非也

还记得我前面说的那个transient变量吗?它的作用已经说了,不想序列化的对象就可以用它来修饰,用transient修饰elementData意味着我不希望elementData数组被序列化。为什么要这么做呢?

这是因为序列化ArrayList的时候,ArrayList里面的elementData,也就是数组未必是满的,比方说elementData有10的大小,但是我只用了其中的3个,那么是否有必要序列化整个elementData呢? 显然没有这个必要,因此ArrayList中重写了writeObject方法:

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

每次序列化的时候调用这个方法,先调用defaultWriteObject()方法序列化ArrayList中的非transient元素elementData这个数组对象不去序列化它,而是遍历elementData,只序列化数组里面有数据的元素这样一来,就可以加快序列化的速度,还能够减少空间的开销。

加上这个知识点后,我们对上面那个问题就可以有更加全面的回答了,如果你下次也遇到这个问题的话,你可以参考一下我的说法:

一般情况下,LinkedList的占用空间更大,因为每个节点要维护指向前后地址的两个节点,但也不是绝对,如果刚好数据量超过ArrayList默认的临时值时,ArrayList占用的空间也是不小的,因为扩容的原因会浪费将近原来数组一半的容量,不过,因为ArrayList的数组变量是用transient关键字修饰的,如果集合本身需要做序列化操作的话,ArrayList这部分多余的空间不会被序列化。

怎么样,这样的回答是不是更加的说服力,不仅更加全面,还可能会给面试官留下好印象,让他觉得你是个有自己思考的求职者,说不定当场就让你面试通过了呢。就冲这点,你们是不是应该给我点个赞啊,哈哈。

0 25

面试官:你好,能看得清下面这张图吗?

我:可以的。

面试官:恩,好的。呃,你能不能说一说为什么String要用final修饰?

我:final意味着不能被继承或者被重写,String类用final修饰是Java的设计人员不希望客户端程序员继承String类,并有可能改写String类中的方法。使用String对象的最佳实践,应该是关联或者依赖,而不是继承。

面试官:恩,你还没有说到点儿上,能再展开谈谈吗?

我:恩,好的。具体来说,String类被定义为final的主要是从两个方面来考虑:安全性能,也就是说,String被设计成final的,即考虑到了安全性,也兼顾了性能问题。

我们可以看到上面这张图中,出现了两个final一个final是修饰了String类,而另一个final修饰了char数组。我们知道,String的本质实际上就是这个char数组,先来说一说 final char[] 的这个 final。

用final修饰char数组的原因,还需要从我们日常的实际开发中说起。

在日常的实际开发中,开发者会用到大量的字符串对象,可以说我们无时无刻不在和字符串打交道。大量的字符串被轻易的创建出来,这就涉及到一个非常严重的问题,即性能的开销,我们知道分配给Java虚拟机的内存是有限的,如果不加节制的创建字符串对象,那么弊端显而易见:内存迅速被占满,程序执行缓慢!!!于是Java的设计者采用了一种非常有效的解决办法,即:共享字符串。共享字符串对象的方法是将字符串对象存放到虚拟机中的方法区里面的常量池里不同的类不同的方法,甚至是不同的线程,可以使用同一个字符串对象,而不需要再在内存中开辟新的内存空间,从而极大的降低了内存的消耗,也提升了程序运行效率。

因此,字符串共享是解决内存消耗以及庞大的性能开销的必然选择。但是到这里为止,还不能解释为什么这个char数组要用final修饰。用final修饰的原因来自于另一个必须要考虑的问题:安全性。什么是安全性?这里的安全性,指的是线程安全性,这个很好理解,首先,我们已经确定了一个大的前提:字符串要共享,否则内存将瞬间挤爆、性能将严重下降。

但是共享的问题在于:不同的线程有可能会修改这个共享对象

比如,thread_1正在循环一个List,每个元素和 “abc” 进行比较,同时thread_2也在使用这个 “abc” 对象,如果thread_2改变了这个共享字符串,结果会怎样?很明显,thread_1 的结果将不可预测!!因此,解决共享变量安全性的最好的手段,就是禁止修改共享对象,于是字符串对象的这个char数组就必然要被 final 修饰了,因为 final 意味着禁止改变。

面试官:恩恩,没想到你的想法这么透彻!那么,这是char数组final的作用,那为什么还要给String类本身加一个final呢?

我:恩,这也是另一个Java设计者需要考虑的问题。既然共享字符数组已经确定是final的、不能改变的了,那为什么要给String也加一个final呢?原因依然是性能和安全性两个方面。

但是,此时需要考虑的性能和安全性却和 final char[] 的final 不太一样了。

首先,如果假设String可以被继承,那么方法也可以被重写,这里面涉及到一个C++中的概念,叫做:虚函数表

面试官:哦?你还懂C++?

我: 是的。同样是面向对象的语言,Java和C++有着共通的地方。首先,虚函数是指:可以定义一个父类的指针, 其指向一个子类对象, 当通过父类的指针去调用函数时, 可以在运行时决定应该调用父类的函数还是子类的函数。虚函数是实现多态的基础。前面说了,如果String可以被继承,那么势必就会有人通过创建String引用并指向String子类对象的方式,来使用子类的方法,比如像这样写:

String aa = new SubString(“abcd”);
aa.length();
这看似没有什么问题,但是问题在于性能,前面提到了,在程序开发过程中,字符串对象是非常常用的,上述代码在调用对象aa.length() 时,虚拟机就会去虚函数表中查找并判定究竟是应该调用哪个子类的length()方法。在大量使用字符串对象的场景下,势必会降低程序运行效率。

其次又是安全性,这个安全性的解释为语义的安全性,面向对象的语言本身就要求要有清晰的语义和明确的表达。String的各个方法都围绕着一个char数组进行,所有方法的语义都是最直接、最有效的。重写String的方法意味着:不一样的语义或者错误的语义。这将直接导致String行为的不确定性,使用String对象的代码将会是不安全的代码。因此,Java设计者才会禁止任何人继承String类,主要是为了String对象的操作语义不被改变,确保使用String对象的代码是绝对安全的。

面试官:原来如此,没想到你的理解这么到位!年薪50万,明天就来上班吧!

总结
当面试官问道为什么 String 是final的时候,要答出两方面:第一就是final char value[] 的final ;第二就是 final class 的final

这两个final都要紧扣安全性能两个方面阐述。

1、final char value[] 的final 要抓住几个关键点是:value[]数组的final用于限制字符数组的修改。字符串将会被大量使用,从性能上考虑迫使Java语言的设计者将 char[] 设计为共享的,又因为字符串是共享的再次迫使设计者考虑到线程安全性,这才需要用final来修饰,避免并发场景下的行为不可预测。

2、final class 的final 要抓住几个关键点是:类上的final用于限制产生子类(或限制多态/或限制行为的变化)。字符串的使用是频繁的,如果通过多态的方式使用String子类对象及其方法将会一定程度上导致性能下降(多态的实现原理:底层的虚函数表),同时String中的方法也可能面临被Override重写的危险导致程序语义不安全、甚至是逻辑错误,与Java自始至终强调的安全性理念相违背。

综上,我觉得只要对照总结部分和上面的对话内容回答出这个问题,不论是简答还是展开讨论基本都应该是满分的节奏了。
————————————————
版权声明:本文为CSDN博主「圣斗士Morty」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/u014745069/article/details/86612841

补充:

https://blog.csdn.net/u013905744/article/details/52414111?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-4.control&dist_request_id=1619532933740_81157&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-4.control