跳转至

03 数组与链表：存储设计的基石有哪些？

你好，我是丁威。

从这节课开始，我们就要进行基础篇的学习了。想要熟练使用中间件解决各种各样的问题，首先需要掌握中间件的基础知识。

我认为，中间件主要包括如下三方面的基础：数据结构、JUC和Netty，接下来的两节课，我们先讲数据结构。

数据结构主要解决的是数据的存储方式问题，是程序设计的基座。

按照重要性和复杂程度，我选取了数组和链表、键值对(HashMap)、红黑树、LinkedHashMap和PriorityQueue几种数据结构重点解析。其中，数组与链表是最底层的两种结构，是后续所有数据结构的基础。

我会带你分析每种结构的存储结构、新增元素和搜索元素的方式、扩容机制等，让你迅速抓住数据结构底层的特性。当然，我还会结合一些工业级实践，带你深入理解这些容器背后蕴含的设计理念。

说明一下，数据结构其实并不区分语言，但为了方便阐述，这节课我主要基于Java语言进行讲解。

数组

我们先来看下数组。

数组是用于储存多个相同类型数据的集合，它具有顺序性，并且也要求内存空间必须连续。高级编程语言基本都会提供数组的实现。

为了更直观地了解数组的内存布局，我们假设从操作系统申请了128字节的内存空间，它的数据结构可以参考下面这张图：

图片

结合这张图我们可以看到，在Java中，数组通常包含下面几个部分。

  • 引用：每一个变量都会在栈中存储数组的引用，我们可以通过引用对数组进行操作，对应上图的 array1、array2。
  • 容量：数组在创建时需要指定容量，一旦创建，无法修改，也就是说，数组并不能自动扩容。
  • 下标：数组可以通过下标对数组中的元素进行随机访问，例如array1[0]表示访问数组中的第一个元素，下标从0开始，其最大值为容量减一。

在后面的讲解中，你能看到很多数据结构都是基于数组而构建的。

那么数组有哪些特性呢？这里我想介绍两个我认为最重要的点：内存连续性和随机访问效率高。

我们先来看下内存连续性。

内存连续性的意思是，数组在向操作系统申请内存时，申请的必须是连续的内存空间。我们还是继续用上面这个例子做说明。我们已经创建了array1、array2两个数组，如果想要再申请一个拥有五个int元素的数组，能把这五个元素拆开，分别放在数组1的前面和后面吗？你可以看看下面这张示意图。

图片

答案当然是不可以。

虽然当前内存中剩余可用空间为32个字节，乍一看上去有充足的内存。但是，因为不存在连续的20字节的空间，所以不能直接创建array3。

当我们想要创建20字节长度的array3时，在Java中会触发一次内存回收，如果垃圾回收器支持整理特性，那么垃圾回收器对内存进行回收后，我们就可以得到一个新的布局：

图片

经过内存整理后就能创建数组3了。也就是说，如果内存管理不当，确实容易产生内存碎片，从而影响性能。

那我们为什么要把内存设计为连续的呢？换句话说，连续内存有什么好处呢？

这就不得不提到数组一个无可比拟的优势了：数组的随机访问性能极好。连续内存确保了地址空间的连续性，寻址非常简单高效。

举个例子，我们创建一个存放int数据类型的数组，代码如下：

int[] array1 = new int[10];

然后我们看下JVM中的布局：

图片

可以看到，首先内存管理器在栈空间会分配一段空间，用它存储数组在物理内存的起始地址，这个起始地址我们用baseOffset表示。如果是64位操作系统，默认一个变量使用8字节，如果采用了指针压缩技术，可以减少到4字节。

数组能够高效地随机访问数组中的元素，主要原因是它能够根据下标快速计算出真实的物理地址，寻找算法为“baseOffset + index * size”。

其中,size为数组中单个元素的长度，是一个常量。在上面这个数组中，存储的元素是int类型的数据，所以size为4。因此，我们根据数组下标就可以迅速找到对应位置存储的数据。

数组这种高效的访问机制在中间件领域有着非常广泛的应用，大名鼎鼎的消息中间件RocketMQ在它的文件设计中就灵活运用了这个特性。

RocketMQ为了追求消息写入时极致的顺序写，会把所有主题的消息全部顺序写入到commitlog文件中。也就是说，commitlog文件中混杂着各个主题的消息，但消息消费时，需要根据主题、队列、消费位置向消息服务器拉取消息。如果想从commitlog文件中读取消息，则需要遍历commitlog文件中的所有消息，检索性能非常低下。

一开始，为了提高检索效率，RocketMQ引入了ConsumeQueue文件，可以理解为commitlog文件按照主题创建索引。

为了在消费端支持消息按tag进行消息过滤，索引数据中需要包含消息的tag信息，它的数据类型是String，索引文件遵循{topic}/{queueId}，也就是按照主题、队列两级目录存储。单个索引文件的存储结构设计如下图所示：

图片

索引文件中，每一条消息都包含偏移量、消息长度和tag内容 3个字段。

  • commitlog偏移量
    可以根据该值快速从commitlog文件中找到消息，这也是索引文件的意义。
  • 消息长度
    消息的长度，知道它可以方便我们快速提取一条完整的消息。
  • tag内容
    由于消息的tag是由用户定义的，例如tagA、createorder等，它的长度可变。在文件存储领域，一般存储可变长的数据，通常会采用“长度字段+具体内容”的存储方式。其中用来存储内容的长度使用固定长度，它是用来记录后边内容的长度。

回到消息消费这个需求，我们根据主题、消费组，消息位置(队列中存储的第N条消息)，能否快速找到消息呢？例如输入 topic:order_topic、queueId:0,offset:2，能不能马上找到第N条消息？

答案是可以找到，但不那么高效。原因是，我们根据topic、queueid，能非常高效地找到对应的索引文件。我们只需要找到对应的topic文件夹，然后在它的子目录中找到对应的队列id文件夹就可以了。但要想从索引文件中找到具体条目，我们还是必须遍历索引文件中的每一个条目，直到到达offset的条目，才能取出对应的commitlog偏移量。

那是否有更高效的索引方式呢？

当然有，我们可以将每一个条目设计成固定长度，然后按照数组下标的方式进行检索。

为了实现每一个条目定长，我们在这里不存储tag的原始字符串，而是存储原始字符串的hashCode，这样就可以确保定长了。你可以看看下面这张设计图：

图片

基于这种设计，如果给定一个offset，我们再想快速提取一条索引就变得非常简单了。

首先，根据 offset * 20(每一个条目的长度)，定位到需要查找条目的起始位置，用startOffset表示。

然后，从startOffset位置开始读取20个字节的长度，就可以得到物理偏移量、消息长度和tag的hashCode了。

接着，我们可以通过hashCode进行第一次过滤，如果遇到hash冲突，就让客户端再根据消息的tag字符串精确过滤一遍。

这种方式，显然借鉴了数组高效访问数据的设计理念，是数组实现理念在文件存储过程中的经典运用。

总之，正是由于数组具有内存连续性，具有随机访问的特性，它在存储设计领域的应用才非常广泛，我们后面介绍的HashMap也引入了数组。

ArrayList

不过，数组从严格意义上来说是面向过程编程中的产物，而Java是一门面向对象编程的语言，所以，直接使用数组容易破坏面向对象的编程范式，故面向对象编程语言都会对数组进行更高级别的抽象，在Java中对应的就是ArrayList。

我会从数据存储结构、扩容机制、数据访问特性三个方面和你一起来探究一下ArrayList。

首先我们来看一下ArrayList的底层存储结构，你可以先看下这个示意图：

图片

从图中可以看出，ArrayList的底层数据直接使用了数组，是对数组的抽象。

ArrayList相比数组，增加了一个特性，它支持自动扩容。其扩容机制如下图所示：

扩容的实现有三个要点。

  • 扩容后的容量= 原容量 +（原容量）/ 2，以 1.5 倍进行扩容。
  • 内部要创建一个新的数组，数组长度为扩容后的新长度。
  • 需要将原数组中的内容拷贝到新的数组，即扩容过程中存在内存复制等较重的操作。

注意，只在当前无剩余空间时才会触发扩容。在实际的使用过程中，我们要尽量做好容量评估，减少扩容的发生。因为扩容的成本还是比较高的，存储的数据越多，扩容的成本越高。

接下来，我们来看一下ArrayList的数据访问特性。

  • 顺序添加元素的效率高

ArrayList顺序添加元素，如果不需要扩容，直接将新的数据添加到elementData[size]位置，然后size加一即可（其中，size表示当前数组中存储的元素个数）。

ArrayList添加元素的时间复杂度为O(1)，也就是说它不会随着存储数据的大小而改变，是非常高效的存储方式。

  • 中间位置插入/删除元素的效率低
    图片

在插入元素时，我们将需要插入数据的下标用 index 表示，将 index 之后的依次向后移动(复制到 index + 1)，然后将新数据存储在下标 index的位置。

删除操作与插入类似，只是一个数据是往后移，而删除动作是往前移。

ArrayList在中间位置进行删除的时间复杂度为O(n)，这是一个比较低效的操作。

  • 随机访问性能高

由于ArrayList的底层就是数组，因此它拥有高效的随机访问数据特性。

LinkedList

除了ArrayList，在数据结构中，还有一种也很经典的数据结构：链表。LinkedList就是链表的具体实现。

我们先来看一下LinkedList的底层存储结构，最后再对比一下它和ArrayList的差异。

图片

从上面这张图你可以看到，一个LinkedList对象在内存中通常由两部分组成：LinkedList对象和由Node节点组成的链条。

一个LinkedList对象在内存中主要包含3个字段。

  • int size：链表中当前存在的Node节点数，主要用来判断是否为空、判断随机访问位点是否存在；
  • Node first：指向链表的头节点；
  • Node last：指向链表的尾节点。

再来说说由Node节点组成的链条。Node节点用于存储真实的数据，并维护两个指针。分别解释一下。

  • E item：拥有存储用户数据；
  • Node prev：前驱节点，指向当前节点的前一个指针；
  • Node last：后继节点，指向当前节点的下一个节点。
    由这两部分构成的链表具有一个非常典型的特征：内存的申请无须连续性。这就减少了内存申请的限制。

接下来我们来看看如何操作链表。对于链表的操作主要有两类，一类是在链表前后添加或删除节点，一类是在链表中间添加或删除数据。

当你想要在链表前后添加或删除节点时，因为我们在LinkedList对象中持有链表的头尾指针，可以非常快地定位到头部或尾部节点。也就是说，这时如果我们想要增删数据，都只需要更新相关的前驱或后继节点就可以了，具体操作如下图所示：

图片

举个例子，如果我们向尾部节点添加节点，它的代码是这样的：

Node oldLastNode = list.last; //添加数据之前原先的尾部节点
Node newNode = new Node();
newNode.item = 4;//设置用户的值
oldLastNode.next = newNode; // 将原先尾部节点的next指针更新为新添加的节点
newNode.prev = oldLastNode; // 新添加的节点的prev指向源尾部节点，通过这两步，使新加入的节点添加到链表中
list.last = newNode; // 更新LinkedList的尾部节点为新添加节点

在链表的尾部、头部添加和删除数据，时间复杂度都是O(1)，比ArrayList在尾部添加节点效率要高。因为当ArrayList需要扩容时，会触发数据的大量复制，而LinkedList是一个无界队列，不存在扩容问题。

如果要在链表的中间添加或删除数据，我们首先需要遍历链表，找到操作节点。因为链表是非连续内存，无法像数组那样直接根据下标快速定位到内存地址。

例如，在下标index为1的后面插入新的数据，它的操作示例图如下：

图片

我们从上往下看。插入新节点的第一步是需要从头节点开始遍历，找到下标为i=1的节点，然后在该节点的后面插入节点，最后执行插入节点的逻辑。

插入节点的具体实现主要是为了维护链表中相关操作节点的前驱与后继节点。

遍历链表、查询操作节点的时间复杂度为O(n)，然后基于操作节点进行插入与删除动作的时间复杂度为O(1)。

关于链表的知识点就讲到这里。由于链表与数组是数据结构中两种最基本的存储结构，为了让你更直观地了解二者的差异，我也给你画了一个表格，对两种数据结构做了对比：

图片

HashMap

无论是链表还是数组都是一维的，在现实世界中有一种关系也非常普遍：关联关系。关联关系在计算机领域主要是用键值对来实现，HashMap就是基于哈希表Map接口的具体实现。

JDK1.8版本之前，HashMap的底层存储结构如下图所示：

图片

HashMap的存储结构主体是哈希槽与链表的组合，类似一个抽屉。

我们向HashMap中添加一个键值对，用这个例子对HashMap的存储结构做进一步说明。

HashMap内部持有一个Map.Entry[]的数组，俗称哈希槽。当我们往HashMap中添加一个键值对时，HashMap会根据Key的hashCode与槽的总数进行取模，得出槽的位置(也就是数组的下标)，然后判断槽中是否已经存储了数据。如果未存储数据，则直接将待添加的键值对存入指定的槽；如果槽中存在数据，那就将新的数据加入槽对应的链表中，解决诸如哈希冲突的问题。

在HashMap中，单个键值对用一个Map.Entry结构表示，具体字段信息如下。

  • K key：存储的Key，后续可以用该Key进行查找
  • V value：存储的Value；
  • int hash：Key的哈希值；
  • Ma.Entry ：next 链表。

到这里，你可以停下来思考一下，当哈希槽中已经存在数据时，新加入的元素是存储在链表的头部还是尾部呢？

答案是放在头部。代码如下：

//假设新放入的槽位下标用 index 表示,哈希槽用 hashArray 表示
Map.Entry newEntry = new Map.Entry(key,value);
newEntry.next = hashArray[index];
hashArray[index] = newEntry;

我们将新增加的元素放到链表的头部，也就是直接放在哈希槽中，然后用next指向原先存在于哈希槽中的元素。

图片

这种方式的妙处在于，只涉及两个指针的修改。如果我们把新增加的元素放入链表的头部，链表的复杂度为O(1)。相反，如果我们把新元素放到链表的尾部，那就需要遍历整条链表，写入复杂度会有所提高，随着哈希表中存储的数据越来越多，那么新增数据的性能将随着链表长度的增加而逐步降低。

介绍完添加元素，我们来看一下元素的查找流程，也就是如何根据Key查找到指定的键值对。

首先，计算Key的hashCode，然后与哈希槽总数进行取模，得到对应哈希槽下标。

然后，访问哈希槽中对应位置的数据。如果数据为空，则返回“未找到元素”。如果哈希槽对应位置的数据不为空，那我们就要判断Key值是否匹配了。如果匹配，则返回当前数据；如果不匹配，则需要遍历哈希槽，如果遍历到链表尾部还没有匹配到任何元素，则返回“未找到元素”。

说到这里，我们不难得出这样一个结论：如果没有发生哈希槽冲突，也就是说如果根据Key可以直接命中哈希槽中的元素，数据读取访问性能非常高。但如果需要从链表中查找数据，则性能下降非常明显，时间复杂度将从O(1)提升到O(n)，这对查找来说就是一个“噩梦”。

一旦出现这种情况，HashMap的结构会变成下面这个样子：

图片

怎么解决这个问题呢？JDK的设计者们给出了两种优化策略。

第一种，对Hash槽进行扩容，让数据尽可能分布到哈希槽上，但不能解决因为哈希冲突导致的链表变长的问题。

第二种，当链表达到指定长度后，将链表结构转换为红黑树，提升检索性能(JDK8开始引入)。

我们先来通过源码深入探究一下HashMap的扩容机制。HashMap的扩容机制由resize方法实现，该方法主要分成两个部分，上半部分处理初始化或扩容容量计算，下半部分处理扩容后的数据复制(重新布局)。

上半部分的具体源码如下：

    /**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
      //此处省略数据复制相关代码
    }

为了方便你对代码进行理解，我画了一个与之对应的流程图：

图片

总结一下扩容的要点。

  • HashMap的容量并无限制，但超过2的30次幂后不再扩容哈希槽。
  • 哈希槽是按倍数扩容的。
  • HashMap在不指定容量时，默认初始容量为16。

HashMap并不是在无容量可用的时候才扩容。它会先设置一个扩容临界值，当HashMap中的存储的数据量达到设置的阔值时就触发扩容，这个阔值用threshold表示。

我们还引入了一个变量loadFactor来计算阔值，阔值=容量*loadFactor。其中，loadFactor表示加载因子，默认为0.75。

加载因子的引入与HashMap哈希槽的存储结构与存储算法有关。

HashMap在出现哈希冲突时，会引入一个链表，形成“数组+链表”的存储结构。这带来的效果就是，如果HashMap有32个哈希槽，当前存储的数据也刚好有32个，这些数据却不一定全会落在哈希槽中，因为可能存在hash值一样但是不同Key的数据，这时，数据就会进入到链表中。

前面我们也提到过，数据放入链表就容易引起查找性能的下降，所以，HashMap的设计者为了将数据尽可能地存储到哈希槽中，会提前进行扩容，用更多的空间换来检索性能的提高。

我们再来看一下扩容的下半部分代码。

我们先来看下这段代码：

@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            if (e.next == null)
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            else { // preserve order
                Node<K,V> loHead = null, loTail = null;
                Node<K,V> hiHead = null, hiTail = null;
                Node<K,V> next;
                do {
                    next = e.next;
                    if ((e.hash & oldCap) == 0) {
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                    }
                    else {
                        if (hiTail == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                    }
                } while ((e = next) != null);
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
}

这段代码不难理解，就是按照扩容后的容量创建一个新的哈希槽数组，遍历原先的哈希槽(数组)，然后将数据重新放入到新的哈希槽中，为了保证链表中数据的顺序性，在扩容时采用尾插法。

除了扩容，JDK8之后的版本还有另外一种提升检索能力的措施，那就是在链表长度超过8时，将链表演变为红黑树。这时的时间复杂度为O(2lgN)，可以有效提升效率。

关于红黑树，我会在下节课详细介绍。

总结

这节课，我们介绍了数组、ArrayList、LinkedList、HashMap这几种数据结构。

数组，由于其内存的连续性，可以通过下标的方式高效随机地访问数组中的元素。

数组与链表可以说是数据结构中两种最基本的数据结构，这节课，我们详细对比了两种数据结构的存储特性。

图片

哈希表是我们使用得最多的数据结构，它的底层的设计也很具技巧性。哈希表充分考虑到数组与链表的优劣，扬长避短，HashMap就是这两者的组合体。为了解决链表检索性能低下的问题，HashMap内部又引入了扩容与链表树化两种方式进行性能提升，提高了使用的便利性，降低了使用门槛。

课后题

最后，我也给你留两道思考题吧！

1、业界在解决哈希冲突时除了使用链表外，还有其他什么方案？请你对这两者的差异进行简单的对比。

2、HashMap中哈希槽的容量为什么必须为2的倍数？如果不是很理解，推荐你先学习一下位运算，然后在留言区告诉我你的答案。

我们下节课再见！

精选留言（8）
  • 苜蓿° 👍（14） 💬（1）

    问题1 网上找寻资料学习了一下: (1) 开放定址法 ①线性探测法 实现过程：当我们的所需要存放值的位置被占了，我们就往后面一直加1并对m取模直到存在一个空余的地址供我们存放值，取模是为了保证找到的位置在0~m-1的有效空间之中。 公式：h(x)=(Hash(x)+i)mod (Hashtable.length);（i会逐渐递增加1） 存在问题：出现非同义词冲突（两个不相同的哈希值，抢占同一个后续的哈希地址）被称为堆积（聚集）现象 ②平方探测法（二次探测） 实现过程： 当我们的所需要存放值的位置被占了，会前后寻找而不是单独方向的寻找 公式：h(x)=(Hash(x) +i)mod (Hashtable.length);（i依次为+(i^2)和-(i^2)） 存在问题：相比线性探测减少找寻时间，但不会减少堆积（聚集）现象 （2）再哈希法 实现过程：同时构造多个不同的哈希函数，等发生哈希冲突时就使用第二个、第三个……等其他的哈希函数计算地址，直到不发生冲突为止 存在问题：不易发生聚集，但是增加了计算时间 （3）建立公共溢出区 实现过程：将哈希表分为基本表和溢出表，将发生冲突的都存放在溢出表中 存在问题：需要实时动态维护两张哈希表

    2022-06-29

  • 末日，成欢 👍（10） 💬（1）

    HashMap 中哈希槽的容量为什么必须为 2 的倍数？ 当我们计算key的索引下标时， 通过会对key的哈希码对数组取模运算来计算出下标值。 而JAVA中的大神对取模运算又进行了一次优化。 将取模运算优化为与运算。 为什么能被优化为与运算呢？ 举个简单的例子： hashcode为11,数组容量为4。 我们知道对于2的n次方一定能整除2的n-1次方。 11对8取模，获取它的余数,也就是它的下标值。 转化为二进制1011 % 0100, 也就是1011/0100, 因为2的n次方一定能整除2的n-1次方的缘故，高位直接舍弃。 其余的无法被整数的也就是它的余数，它的低位就是它的余数， 获取它的低位就可以通过x011&(0100-1)=>也就是hash & (n-1),能推导出这个公式是建立在数组的容量是2的倍数的前提上。 为什么要优化为与运算呢？ 我的猜想，计算机对于与运算的指令比取模运算的指令要少的多， 故与运算要高效的多。 最后，我还想再说一个key获取哈希值的优化。 我们知道，生成哈希值的原则就是要尽量让所有的元素都参与到计算。 key获取哈希值， 并不是简单的直接获取哈希码， 而是该key的哈希值高低16位再一次又进行了异或运算，这样就可以让哈希值再次变化。 其实也可以不变化的，但是对于起始容量比较小，大量的元素如果低位都相同，就可能会造成大量的哈希冲突。 而再一次进行异或运算， 即使相同的低位也可以再次变化， 减小hash冲突。

    2022-06-21

  • 蔫巴的小白菜 👍（4） 💬（2）

    hashmap，容量设计成2的整数幂，我理解有两点： 1.就是设计成2整数幂可以利用位运算的高效，快速找到下标。 2.为了扩容搬运元素方便，小于之前size的元素，可以直接搬运到新size的原始位置，而超过原始size的元素，只需要下标加上原始size即可，实战了高效的扩容元素迁移。

    2022-07-01

  • 独自等待 👍（0） 💬（3）

    RocketMQ这块的分析还可以

    2022-06-17

  • Zero 👍（0） 💬（0）

    ArrayList与LinkedList的对比图中，ArrayList中的数组是以1.5倍进行扩容的吧，图中标错了

    2024-11-02

  • 夜空中最亮的星 👍（0） 💬（0）

    分析到位 图标很棒

    2022-07-11

  • William Ning 👍（0） 💬（0）

    https://time.geekbang.org/column/article/64586 数据结构与算法之美 对照着学习～～

    2022-07-06

  • Geek_xbye50 👍（0） 💬（3）

    hashmap1.8之前采用头插法的解释很牵强啊！通过复杂度比较的话头尾不都是O(1)

    2022-06-26