动态数组挺常用的，它和普通数组的最大区别也就是它的容量大小可变，而其中的重点也就是它的扩容机制。
本篇博客就主要记录记录我对几种常用的动态数组的理解，主要包括C++ stl里的vector，java中的ArrayList，redis中的SDS（动态字符串，本质上就是动态字符数组）
并且主要讨论它们的扩容机制。

C++ stl —— vector

vector就是一个动态（大小可变的）数组，使用vector的程序员不需要关注它的容量大小变化，如果有扩容需求时，程序会自动处理。

vector的扩容机制

vector 容器扩容的过程需要经历以下 3 步：

1. 完全弃用现有的内存空间，重新申请更大的内存空间；
2. 将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
3. 最后将旧的内存空间释放。

所以，vector 容器在进行扩容后，与其相关的指针、引用以及迭代器可能会失效。

vector 常见的扩容有两种，gcc是2倍扩容，而vs是1.5倍扩容。

为什么vs的vector是1.5倍扩容？相比于2倍扩容有什么优势？

如果是两倍扩容，那么之前使用过的内存空间都没办法再次被这个vector使用，因为之前的所有内存加起来都比新申请的内存小。

举个例子，在两倍扩容的情况下，之前分配的内存分别是1,2，4,8（它们现在都被释放了）。
而现在要申请的内存大小是16，而之前所有使用过的内存加起来也只有15，满足不了本次的要求（而且其实8这块内存还没有被释放，被释放内存大小的其实只有7，更加满足不了要求了），也就是说，之前释放过的内存在之后的扩容中不可能被使用。

而在1.5倍扩容的情况下，分配的内存情况可能就是这样的：
4，6，9，14，21，31.5，…
当要申请大小为31.5的内存时，之前使用过的4,6，9,14都已经被释放了，它们加起来的大小是4+6+9+14 = 33 >31.5,，如果它们刚好是连续的，那么就有可能重复利用之前释放过的内存。

java —— ArrayList

ArrayList 底层是基于数组来实现容量大小动态变化的。

/**
* The size of the ArrayList (the number of elements it contains).
*/
private int size;  // 实际元素个数
transient Object[] elementData; 

注意：上面的 size 是指 elementData 中实际有多少个元素，而 elementData.length 为集合容量，表示最多可以容纳多少个元素。
前者相当于vector中的size(),后者相当于capacity()

扩容机制

ArrayList默认容量为10，但当大小从10增加到11时，容量变成了15，扩大了1.5倍，以此类推，总是会扩容1.5倍,不为整则向下取整。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length; // 旧容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的1.5倍
    if (newCapacity - minCapacity < 0) // 新容量小于参数指定容量，修改新容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 新容量大于最大容量
        newCapacity = hugeCapacity(minCapacity); // 指定新容量
    // 拷贝扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

线程安全性

ArrayList是线程不安全的。
如果非要在多线程的环境下使用ArrayList，就需要保证它的线程安全性，通常有两种解决办法：第一，使用synchronized关键字；第二，可以用Collections类中的静态方法synchronizedList();对ArrayList进行调用即可。

Redis —— SDS

redis是一种用c语言实现的数据库，其中某些字符串对象是以动态字符串的形式存储的，其本质是记录了字符串的长度len与未使用字节的数量free的字符数组。

struct sdshdr {

    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];

};

SDS的内存重分配机制（即扩容与释放）

对于普通的c字符串，每次增长或者缩短它的长度时， 程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作。

而对于经常对字符串进行修改操作的数据库来说，这种过于频繁的内存重分配太低效，于是redis对它进行了优化。

优化从两方面进行，在扩容时，redis使用了空间预分配，在释放时，redis使用了空间惰性释放。

接下来分别对这两种策略进行介绍：

一、空间预分配

其实本质思想与之前c++ stl的vector和java的ArrayList一样，都是在需要扩容时分配可能超过需求的内存，以减少扩容的次数。

不过前两者都是以原有内存的倍数进行分配，而redis中SDS的处理有点不一样。
扩容时SDS分配的内存大小由以下公式决定：

• 如果对 SDS 进行修改之后， SDS 的长度（也即是 len 属性的值）将小于 1 MB ， 那么程序分配和len 属性同样大小的未使用空间， 这时 SDS len 属性的值将和 free 属性的值相同。
  举个例子， 如果进行修改之后， SDS 的 len 将变成 13 字节， 那么程序也会分配 13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。

• 如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ， 那么程序会分配 1 MB的未使用空间。
  举个例子， 如果进行修改之后， SDS 的 len 将变成 30 MB ， 那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。

惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作： 当 SDS 的 API 需要缩短 SDS 保存的字符串时， 程序并不立即使用内存重分配来回收缩短后多出来的字节， 而是使用 free 属性将这些字节的数量记录起来， 并等待将来使用。

• 通过惰性空间释放策略， SDS 避免了缩短字符串时所需的内存重分配操作， 并为将来可能有的增长操作提供了优化。

• 与此同时， SDS 也提供了相应的 API ， 让我们可以在有需要时， 真正地释放 SDS 里面的未使用空间， 所以不用担心惰性空间释放策略会造成内存浪费。

关于redis动态字符串的更多信息可以看这篇博客

最后

以上就是明理手套为你收集整理的动态数组C++ stl —— vectorjava —— ArrayListRedis —— SDS的全部内容，希望文章能够帮你解决动态数组C++ stl —— vectorjava —— ArrayListRedis —— SDS所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。