在編碼時我們經(jīng)常使用各種容器來做基本的數(shù)據(jù)結(jié)構(gòu)，比如 C++ STL 中的 vector, C# 的 List 和 Dictionary 等，這篇文章我們簡單聊一下這些容器在發(fā)生擴(kuò)容時的擴(kuò)容系數(shù)選擇的話題
1. 什么是容器的擴(kuò)容
雖然容器的使用方法和特點(diǎn)各異，但整體來說底層的存儲結(jié)構(gòu)基本上都是基于數(shù)組，例如 C++ 中的 vector、C# 中的 List 底層都是使用數(shù)組來存放數(shù)據(jù)，那么容器中的數(shù)組長度如何確定呢？
- 容器會進(jìn)行預(yù)分配空間（capacity）
- 通常容器會提供接口，讓我們在初始化時指定容器中元素的個數(shù)（size 或 length），容器底層會根據(jù)元素個數(shù)分配對應(yīng)的數(shù)組長度
- 如果初始化時沒有提供元素個數(shù)，則會初始化一個默認(rèn)長度（vector 和 List 默認(rèn)都是4）
- 那么當(dāng)容器元素超過預(yù)分配空間時，會重新分配更多的空間，以存放更多的元素，這個過程就是擴(kuò)容
容器擴(kuò)容的操作： - 分配新的內(nèi)存空間
- 搬移元素，將元素全部復(fù)制到新分配的內(nèi)存空間
- 釋放舊空間
2. 容器擴(kuò)容的時機(jī)
那么容器的擴(kuò)容發(fā)生在什么時候呢？
- 第一種情況：當(dāng)容器調(diào)用添加元素（push_back, Add等）的方法時，如果當(dāng)前 capacity 無法容納新元素，會觸發(fā)擴(kuò)容機(jī)制
- 第二種情況：基于哈希表的容器（如Dictionary）當(dāng)哈希沖突超過某個閾值時，觸發(fā)擴(kuò)容機(jī)制
3. 容器擴(kuò)容的系數(shù)選擇邏輯
擴(kuò)容時分配多大的新空間比較合適呢？（此處綜合考慮到普遍情況下的內(nèi)存分配、元素復(fù)制消耗、擴(kuò)容次數(shù)等），假設(shè)當(dāng)前容量是，那么新分配的容量為
，對于不同容器，不同的版本實(shí)現(xiàn)，此處的
不盡相同
3.1 C++ STL vector 的擴(kuò)容系數(shù)
- VC 版本的 vector 擴(kuò)容系數(shù)為 1.5，每次擴(kuò)容時分配 1.5 倍的新空間
- gcc 版本的 vector 擴(kuò)容系數(shù)為 2，每次擴(kuò)容時分配 2 倍的新空間
3.2 C# List 的擴(kuò)容系數(shù)
查看 List源碼可知，C# List 的擴(kuò)容系數(shù)是 2，擴(kuò)容是分配 2 倍新空間
對于 vector 和 List 來說，1.5 的擴(kuò)容系數(shù)是比 2 更好的選擇。使用擴(kuò)容系數(shù) 2 時產(chǎn)生的問題在于，每次新分配的空間必然剛好大于之前分配的空間之和，之前分配的空間無法復(fù)用，使用1.5 是一個更好的選擇，便于復(fù)用之前分配過的空間，詳情可以參考 MiloYip的回答
3.3 C# Dictionary 的擴(kuò)容系數(shù)
和列表不同，Dictionary 由于底層哈希桶數(shù)組的存在，添加元素時需要考慮元素哈希值沖突，擴(kuò)容應(yīng)該能夠盡量避免哈希沖突的產(chǎn)生，所以 Dictionary 的擴(kuò)容方法是，取小于 的最小質(zhì)數(shù)，為什么要取質(zhì)數(shù)呢？這是因為哈希桶的長度為質(zhì)數(shù)時，能夠使得哈希值分配更均勻，最大程度的減少哈希沖突的發(fā)生，理論依據(jù)簡單概括：
- 偶數(shù)除以偶數(shù)，得到的余數(shù)一定是個偶數(shù)。
- 偶數(shù)除以質(zhì)數(shù)，小于質(zhì)數(shù)得到的余數(shù)是偶數(shù)，大于質(zhì)數(shù)得到的是奇數(shù)。
- 奇數(shù)除以偶數(shù)，得到的余數(shù)一定是個奇數(shù)。
- 奇數(shù)除以質(zhì)數(shù)，小于質(zhì)數(shù)得到的余數(shù)是奇數(shù)，大于質(zhì)數(shù)得到的是偶數(shù)。
陷入以質(zhì)數(shù)做除數(shù)，得到的結(jié)果的可能性更多，也就說明了質(zhì)數(shù)能夠使數(shù)據(jù)分配的更均勻，達(dá)到了減少哈希沖突的目的。
