引子：在網(wǎng)上找到了一門(mén)基于python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法的課程（課程鏈接：https://www.bilibili.com/video/av21540971/?p=33），老師講課的思路非常清晰，適合入門(mén)學(xué)習(xí)者參考。接下來(lái)的幾篇文章是對(duì)課堂筆記的整理，希望能夠幫助更多的讀者。

1. 概念引入

先來(lái)看一道題：如果 a + b + c = 1000,且 a^2+b^2=c^2（a,b,c為自然數(shù)），如何求出所有a、b、c可能的組合？

1.1 第一次嘗試

第一次嘗試的程序

以上代碼運(yùn)行的結(jié)果：

第一次嘗試的程序運(yùn)行結(jié)果

1.2 算法的提出

1.2.1 算法的概念

算法是計(jì)算機(jī)處理信息的本質(zhì)，因?yàn)橛?jì)算機(jī)程序本質(zhì)是一個(gè)算法來(lái)告訴計(jì)算機(jī)確切的步驟來(lái)執(zhí)行一個(gè)指定的任務(wù)。一般地，當(dāng)算法在處理信息時(shí)，會(huì)從輸入設(shè)備或數(shù)據(jù)的存儲(chǔ)地址讀取數(shù)據(jù)，把結(jié)果寫(xiě)入輸出設(shè)備或某個(gè)存儲(chǔ)地址供以后再調(diào)用。

算法是獨(dú)立存在的一種解決問(wèn)題的方法和思想。

對(duì)于算法而言，實(shí)現(xiàn)的語(yǔ)言并不重要，重要的是思想。

算法可以有不同的語(yǔ)言描述實(shí)現(xiàn)版本（如C描述、C++描述、Python描述等），我們現(xiàn)在是在用Python語(yǔ)言進(jìn)行描述實(shí)現(xiàn)。

1.2.2 算法的五大特征

1.輸入：算法具有0個(gè)或多個(gè)輸入

2.輸出：算法至少有1個(gè)或多個(gè)輸出

3.有窮性：算法在有限的步驟之后會(huì)在自動(dòng)結(jié)束而不會(huì)無(wú)限循環(huán)，并且每一個(gè)步驟可以在可接受的時(shí)間內(nèi)完成

4.確定性：算法中的每一步都有確定的含義，不會(huì)出現(xiàn)二義性

5.可行性：算法的每一步都是可行的，也就是說(shuō)每一步都能夠執(zhí)行有限的次數(shù)完成

1.3 第二次嘗試

在第一次嘗試的時(shí)候，我們將c作為一個(gè)獨(dú)立的變量并進(jìn)行循環(huán)，這樣就一共有三層循環(huán)，所以造成了計(jì)算時(shí)間比較長(zhǎng)。實(shí)際上，隨著a和b的確定，c值就已經(jīng)確定了，因此我們可以用 1000 - a - b 來(lái)替換 c ，這樣就省去了一層循環(huán)，代碼如下：

第二次嘗試程序

上面代碼運(yùn)行的結(jié)果：

第二次嘗試程序的運(yùn)行結(jié)果

可以發(fā)現(xiàn)，相較于第一次嘗試的運(yùn)行結(jié)果，這次的運(yùn)行時(shí)間明顯縮短了很多。

1.4 算法效率衡量

1.4.1 執(zhí)行時(shí)間反應(yīng)算法效率

對(duì)于同一問(wèn)題，我們給出了兩種解決算法，在兩種算法的實(shí)現(xiàn)中，我們對(duì)程序執(zhí)行的時(shí)間進(jìn)行了測(cè)算，發(fā)現(xiàn)兩段程序執(zhí)行的時(shí)間相差懸殊，由此我們可以得出結(jié)論：實(shí)現(xiàn)算法程序的執(zhí)行時(shí)間可以反應(yīng)出算法的效率，即算法的優(yōu)劣。

1.4.2 單靠時(shí)間值絕對(duì)可信嗎？

假設(shè)我們將第二次嘗試的算法程序運(yùn)行在一臺(tái)配置古老性能低下的計(jì)算機(jī)中，情況會(huì)如何？很可能運(yùn)行的時(shí)間并不會(huì)比在我們的電腦中運(yùn)行的算法一快多少。因此，單純依靠運(yùn)行的時(shí)間來(lái)比較算法的優(yōu)劣并不一定是客觀準(zhǔn)確的！程序的運(yùn)行離不開(kāi)計(jì)算機(jī)環(huán)境（包括硬件和操作系統(tǒng)），這些客觀原因會(huì)影響程序運(yùn)行的速度并反應(yīng)在程序的執(zhí)行時(shí)間上。那么如何才能客觀的評(píng)判一個(gè)算法的優(yōu)劣呢？

1.4.3 時(shí)間復(fù)雜度與“大O記法”

我們假定計(jì)算機(jī)執(zhí)行算法每一個(gè)基本操作的時(shí)間是固定的一個(gè)時(shí)間單位，那么有多少個(gè)基本操作就代表會(huì)花費(fèi)多少時(shí)間單位。算法對(duì)于不同的機(jī)器環(huán)境而言，確切的單位時(shí)間是不同的，但是對(duì)于算法進(jìn)行多少個(gè) 基本操作（即花費(fèi)多少時(shí)間單位）在規(guī)模數(shù)量級(jí)上卻是相同的，由此可以忽略機(jī)器環(huán)境的影響而客觀的反應(yīng)算法的時(shí)間效率。對(duì)于算法的時(shí)間效率，我們可以用“大O記法”來(lái)表示。

“大O記法”：對(duì)于單調(diào)的整數(shù)函數(shù)f，如果存在一個(gè)整數(shù)函數(shù)g和實(shí)數(shù)常數(shù)c>0，使得對(duì)于充分大的n總有f(n)<=c*g(n)，就說(shuō)函數(shù)g是f的一個(gè)漸進(jìn)函數(shù)（忽略常數(shù)），記為f(n)=O(g(n))。也就是說(shuō)，在趨向無(wú)窮的極限意義下，函數(shù)f的增長(zhǎng)速度受到函數(shù)g的約束，亦即函數(shù)f與函數(shù)g的特征相似。

時(shí)間復(fù)雜度：假設(shè)存在函數(shù)g，使得算法A處理規(guī)模為n的問(wèn)題示例所用時(shí)間為 T(n)=O(g(n))，則稱(chēng)O(g(n))為算法A的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度，記為T(mén)(n)

1.4.4 如何理解“大O記法”

對(duì)于算法進(jìn)行特別具體的細(xì)致分析雖然好，但在實(shí)踐中的實(shí)際價(jià)值有限。對(duì)于算法的時(shí)間性質(zhì)和空間性質(zhì)，最重要的是其數(shù)量級(jí)和趨勢(shì)，這些是分析算法效率的主要部分。而計(jì)量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計(jì)。例如，可以認(rèn)為和同屬一個(gè)量級(jí)，如果兩個(gè)算法處理同樣規(guī)模實(shí)例的代價(jià)分別為這兩個(gè)函數(shù)，就認(rèn)為他們的效率“差不多”，都為級(jí)。

1.4.5 最壞時(shí)間復(fù)雜度

分析算法時(shí)，存在幾種可能的考慮：

算法完成工作最少需要多少基本操作，即最優(yōu)時(shí)間復(fù)雜度

算法完成工作最多需要多少基本操作，即最壞時(shí)間復(fù)雜度

算法完成工作平均需要多少基本操作，即平均時(shí)間復(fù)雜度

對(duì)于最優(yōu)時(shí)間復(fù)雜度，其價(jià)值不大，因?yàn)樗鼪](méi)有提供什么有用信息，其反映的只是最樂(lè)觀最理想的情況，沒(méi)有參考價(jià)值。對(duì)于最壞時(shí)間復(fù)雜度，提供了一種保證，表明算法在此種程度是基本操作中一定能完成工作。對(duì)于平均時(shí)間復(fù)雜度，是對(duì)算法的一個(gè)全面的評(píng)價(jià)，因此它完整全面的反映了這個(gè)算法的性質(zhì)。但另一方面，這種衡量并沒(méi)有保證，不是每個(gè)計(jì)算都能在這個(gè)基本操作內(nèi)完成。而且，對(duì)于平均情況的計(jì)算，也會(huì)因?yàn)閼?yīng)用算法的實(shí)例分布可能并不均勻而難以計(jì)算。因此，我們主要關(guān)注算法的最壞情況，亦即最壞時(shí)間復(fù)雜度。

1.4.6 時(shí)間復(fù)雜度的幾條基本計(jì)算規(guī)則

1. 基本操作，即只有常數(shù)項(xiàng)，認(rèn)為其時(shí)間復(fù)雜度為O(1)

2. 順序結(jié)構(gòu)，時(shí)間復(fù)雜度按加法進(jìn)行計(jì)算

3. 循環(huán)結(jié)構(gòu)，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算

4. 分支結(jié)構(gòu)，時(shí)間復(fù)雜度取最大值

5. 判斷一個(gè)算法的效率時(shí)。往往只需要關(guān)注操作數(shù)量的最高次項(xiàng)，其它次要項(xiàng)和常數(shù)項(xiàng)可以忽略

6. 在沒(méi)有特殊說(shuō)明時(shí)，我們所分析的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度

1.5 算法分析

第一次嘗試的算法核心部分

第一次嘗試的算法核心部分代碼

時(shí)間復(fù)雜度： T(n) = O(n*n*n) = O()

第二次嘗試的算法核心部分

第二次嘗試的算法核心部分代碼

時(shí)間復(fù)雜度： T(n) = O(n*n*(1+1)) = O(n*n) = O()

由此可見(jiàn)，我們嘗試的第二種算法要比第一種算法的時(shí)間復(fù)雜度好多了。

1.6 常見(jiàn)時(shí)間復(fù)雜度

1.6.1 常見(jiàn)時(shí)間復(fù)雜度對(duì)比

常見(jiàn)的時(shí)間復(fù)雜度（注：經(jīng)常將簡(jiǎn)寫(xiě)為 logn）

1.6.2 常見(jiàn)時(shí)間復(fù)雜度之間的關(guān)系

常見(jiàn)時(shí)間復(fù)雜度對(duì)比圖

所消耗時(shí)間從小到大? ?O(1) < O(logn) < O(n) < O(nlogn) < O() < O() < O() < O(n!) < O()

1.7 數(shù)據(jù)結(jié)構(gòu)

我們?nèi)绾斡肞ython中的類(lèi)型來(lái)保存一個(gè)班的學(xué)生信息？如果想要快速的通過(guò)學(xué)生姓名獲取其信息呢？

實(shí)際上當(dāng)我們?cè)谒伎歼@個(gè)問(wèn)題的時(shí)候，我們已經(jīng)用到了數(shù)據(jù)結(jié)構(gòu)。列表和字典都可以存儲(chǔ)一個(gè)班的學(xué)生信息，但是想要在列表中獲取一名同學(xué)的信息時(shí)，就要遍歷這個(gè)列表，其時(shí)間復(fù)雜度為O(n)，而使用字典存儲(chǔ)時(shí)，可將學(xué)生姓名作為字典的鍵，學(xué)生信息作為值，進(jìn)而查詢(xún)時(shí)不需要遍歷便可以快速獲取到學(xué)生的信息，其時(shí)間復(fù)雜度為O(1)。

我們?yōu)榱私鉀Q問(wèn)題，需要將數(shù)據(jù)保存下來(lái)，然后根據(jù)數(shù)據(jù)的存儲(chǔ)方式來(lái)設(shè)計(jì)算法實(shí)現(xiàn)進(jìn)行處理，那么數(shù)據(jù)的存儲(chǔ)方式不同就會(huì)導(dǎo)致需要不同的算法進(jìn)行處理。我們希望算法解決問(wèn)題的效率越快越好，于是我們就需要考慮數(shù)據(jù)究竟如何保存的問(wèn)題，這就是數(shù)據(jù)結(jié)構(gòu)。

在上面的問(wèn)題中我們可以選擇Python中的列表或字典來(lái)存儲(chǔ)學(xué)生信息。列表和字典就是Python內(nèi)建幫我們封裝好的兩種數(shù)據(jù)結(jié)構(gòu)。

1.7.1 概念

數(shù)據(jù)是一個(gè)抽象的概念，將其進(jìn)行分類(lèi)后得到程序設(shè)計(jì)語(yǔ)言中的基本類(lèi)型。如：int，float，char等。數(shù)據(jù)元素之間不是獨(dú)立的，存在特定的關(guān)系，這些關(guān)系便是結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的關(guān)系。Python給我們提供了很多現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)類(lèi)型，這些系統(tǒng)自己定義好的，不需要我們自己去定義的數(shù)據(jù)結(jié)構(gòu)叫Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，比如列表、元組、字典。而有些數(shù)據(jù)組織方式，Python系統(tǒng)里面沒(méi)有直接定義，需要我們自己去定義實(shí)現(xiàn)這些數(shù)據(jù)的組織方式，這些數(shù)據(jù)組織方式稱(chēng)之為Python的擴(kuò)展數(shù)據(jù)結(jié)構(gòu)，比如棧、隊(duì)列等。

1.7.2 算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別

數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系。高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)和選擇算法。程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

總結(jié)：算法是為了解決實(shí)際問(wèn)題而設(shè)計(jì)的，數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問(wèn)題載體

1.7.3 抽象數(shù)據(jù)類(lèi)型（Abstract Data Type）

抽象數(shù)據(jù)類(lèi)型（ADT）的含義是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作，即把數(shù)據(jù)類(lèi)型和數(shù)據(jù)類(lèi)型上的運(yùn)算捆在一起，進(jìn)行封裝。引入抽象 數(shù)據(jù)類(lèi)型的目的是把數(shù)據(jù)類(lèi)型的表示和數(shù)據(jù)類(lèi)型上運(yùn)算的實(shí)現(xiàn)與這些數(shù)據(jù)類(lèi)型和運(yùn)算在程序中的引用隔開(kāi)，使它們相互獨(dú)立。

最常用的數(shù)據(jù)運(yùn)算有五種：插入、刪除、修改、查找、排序

2. 順序表

在程序中，經(jīng)常需要將一組（通常是同為某個(gè)類(lèi)型的）數(shù)據(jù)元素作為整體管理和使用，需要?jiǎng)?chuàng)建這種元素組，用變量記錄它們，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個(gè)數(shù)可能發(fā)生變化（可以增加或刪除元素）。對(duì)于這種需求，最簡(jiǎn)單的解決方案便是將這樣一組元素看成一個(gè)序列，用元素在序列里的位置和順序，表示實(shí)際應(yīng)用中的某種有意義的信息，或者表示數(shù)據(jù)之間的某種關(guān)系。這樣的一組序列元素的組織形式，我們可以將其抽象為線性表。一個(gè)線性表是某類(lèi)元素的一個(gè)集合，還記錄著元素之間的一種順序關(guān)系。線性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一，在實(shí)際程序中非常廣泛，他還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)。根據(jù)線性表的實(shí)際存儲(chǔ)方式，分為兩種實(shí)現(xiàn)模型：

順序表，將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示。

鏈表，將元素存放在通過(guò)鏈接構(gòu)造起來(lái)的一系列存儲(chǔ)塊中。

2.1 順序表的基本形式

順序表的兩種基本形式

圖a表示的是順序表的基本形式，數(shù)據(jù)元素本身連續(xù)存儲(chǔ)，每個(gè)元素所占的存儲(chǔ)單元大小固定相同，元素的下標(biāo)是其邏輯地址，而元素存儲(chǔ)的物理地址（實(shí)際內(nèi)存地址）可以通過(guò)存儲(chǔ)區(qū)的起始地址Loc() 加上邏輯地址（第i個(gè)元素）與存儲(chǔ)單元大小（c）的乘積計(jì)算而得，即：

Loc() = Loc() + c*i

故，訪問(wèn)指定元素時(shí)無(wú)需從頭遍歷，通過(guò)計(jì)算便可獲得對(duì)應(yīng)地址，其時(shí)間復(fù)雜度為O(1)。如果元素的大小不統(tǒng)一，則須采用圖b的元素外置的形式，將實(shí)際數(shù)據(jù)元素另行存儲(chǔ)，而順序表中的各單元位置保存對(duì)應(yīng)元素的地址信息（即鏈接）。由于每個(gè)鏈接所需的存儲(chǔ)量相同，通過(guò)上述公式，可以計(jì)算出元素鏈接的存儲(chǔ)位置，以后順著鏈接找到實(shí)際存儲(chǔ)的數(shù)據(jù)元素。注意，圖b中的c不再是數(shù)據(jù)元素的大小，而是存儲(chǔ)一個(gè)鏈接地址所需的存儲(chǔ)量，這個(gè)量通常很小。圖b這樣的順序表也被稱(chēng)為對(duì)實(shí)際數(shù)據(jù)的索引，這是最簡(jiǎn)單的索引結(jié)構(gòu)。

2.2 順序表的結(jié)構(gòu)與實(shí)現(xiàn)

2.2.1 順序表的結(jié)構(gòu)

順序表的結(jié)構(gòu)

一個(gè)順序表的完整信息包括兩部分，一部分是表中的元素集合，另一部分是為實(shí)現(xiàn)正確操作而需記錄的信息，即有關(guān)表的整體情況的信息，這部分信息主要包括元素存儲(chǔ)區(qū)的容量和當(dāng)前表中已有的元素個(gè)數(shù)兩項(xiàng)。

2.2.2 順序表的兩種基本實(shí)現(xiàn)方式

順序表的兩種基本實(shí)現(xiàn)方式

圖a為一體式結(jié)構(gòu)，存儲(chǔ)表信息的單元與元素存儲(chǔ)區(qū)以連續(xù)的方式安排在一塊存儲(chǔ)區(qū)里，兩部分?jǐn)?shù)據(jù)的整體形成一個(gè)完整的順序表對(duì)象。一體式結(jié)構(gòu)整體性強(qiáng)，易于管理。但是由于數(shù)據(jù)元素存儲(chǔ)區(qū)域是表對(duì)象的一部分，順序表創(chuàng)建后，元素存儲(chǔ)區(qū)就固定了。圖b為分離式結(jié)構(gòu)，表對(duì)象里只保存與整個(gè)表有關(guān)的信息（即容量和元素個(gè)數(shù)），實(shí)際數(shù)據(jù)元素存放在另一個(gè)獨(dú)立的元素存儲(chǔ)區(qū)里，通過(guò)鏈接與基本表對(duì)象關(guān)聯(lián)。

2.2.3 元素存儲(chǔ)區(qū)替換

一體式結(jié)構(gòu)由于順序表信息區(qū)與數(shù)據(jù)區(qū)連續(xù)存儲(chǔ)在一起，所以若想更換數(shù)據(jù)區(qū)，則只能整體搬遷，即整個(gè) 順序表對(duì)象（指存儲(chǔ)順序表的結(jié)構(gòu)信息的區(qū)域）改變了。分離式結(jié)構(gòu)若想更換數(shù)據(jù)區(qū)，只需將表信息區(qū)中的數(shù)據(jù)區(qū)鏈接地址更新即可，而該順序表對(duì)象不變。

2.2.4 元素存儲(chǔ)區(qū)擴(kuò)充

采用分離式結(jié)構(gòu)的順序表，若將數(shù)據(jù)區(qū)更換為存儲(chǔ)空間更大的區(qū)域，則可以在不改變表對(duì)象的前提下對(duì)其數(shù)據(jù)存儲(chǔ)區(qū)進(jìn)行了擴(kuò)充，所有使用這個(gè)表的地方都不必修改。只要程序的運(yùn)行環(huán)境（計(jì)算機(jī)系統(tǒng)）還有空閑存儲(chǔ)，這種表結(jié)構(gòu)就不會(huì)因?yàn)闈M了而導(dǎo)致操作無(wú)法進(jìn)行。人們把采用這種技術(shù)實(shí)現(xiàn)的順序表稱(chēng)為動(dòng)態(tài)順序表，因?yàn)槠淙萘靠梢栽谑褂弥袆?dòng)態(tài)變化。

擴(kuò)充的兩種策略

1. 每次擴(kuò)充增加固定數(shù)目的存儲(chǔ)位置，如每次擴(kuò)充增加10個(gè)元素位置，這種策略可稱(chēng)為線性增長(zhǎng)。特點(diǎn)：節(jié)省空間，但是擴(kuò)充操作頻繁，操作次數(shù)多。

2. 每次擴(kuò)充容量加倍，如每次擴(kuò)充增加一倍存儲(chǔ)空間。特點(diǎn)：減少了擴(kuò)充操作的執(zhí)行次數(shù)，但可能會(huì)浪費(fèi)空間資源。以空間換時(shí)間，推薦的方式。

2.3 順序表的操作

2.3.1 增加元素

如圖所示，為順序表增加新元素111的三種方式

順序表增加新元素的三種方式

a. 尾端加入元素，時(shí)間復(fù)雜度為O(1)

b. 非保序的加入元素（不常見(jiàn)），時(shí)間復(fù)雜度為O(1)

c. 保序的元素加入，時(shí)間復(fù)雜度為O(n)

2.3.2 刪除元素

順序表刪除元素的三種形式

a. 刪除表尾元素，時(shí)間復(fù)雜度為O(1)

b. 非保序的元素刪除（不常見(jiàn)），時(shí)間復(fù)雜度為O(1)

c. 保序的元素刪除，時(shí)間復(fù)雜度為O(n)

2.4 Python中的順序表

Python中的list和tuple兩種類(lèi)型采用了順序表的實(shí)現(xiàn)技術(shù)，具有前面討論的順序表的所有性質(zhì)。tuple是不可變類(lèi)型，即不變的順序表，因此不支持改變其內(nèi)部狀態(tài)的任何操作，而其他方面，則與list的性質(zhì)類(lèi)似。

2.4.1 list的基本實(shí)現(xiàn)技術(shù)

Python標(biāo)準(zhǔn)類(lèi)型list就是一種元素個(gè)數(shù)可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：

1. 基于下標(biāo)（位置）的高效元素訪問(wèn)和更新，時(shí)間復(fù)雜度應(yīng)該是O(1)；為滿足該特征，應(yīng)該采用順序表技術(shù)，表中元素保存在一塊連續(xù)的存儲(chǔ)區(qū)中。

2. 允許任意加入元素，而且在不斷加入元素的過(guò)程中，表對(duì)象的標(biāo)識(shí)（函數(shù)ID得到的值）不變。為滿足該特征，就必須能更換元素存儲(chǔ)區(qū)，并且為保證更換存儲(chǔ)區(qū)時(shí)的list對(duì)象的標(biāo)識(shí)ID不變，只能采用分離式實(shí)現(xiàn)技術(shù)。

在Python的官方實(shí)現(xiàn)中，list就是一種采用分離式技術(shù)實(shí)現(xiàn)的動(dòng)態(tài)順序表，這就是為什么用list.append(x) （或 list.insert(len(list),x)），即尾部插入）比在指定位置插入元素效率高的原因。

在Python的官方實(shí)現(xiàn)中，list實(shí)現(xiàn)采用了如下的策略：在建立空表（或者很小的表）時(shí)，系統(tǒng)分配一塊能容納8個(gè)元素的存儲(chǔ)區(qū)；在執(zhí)行插入操作（insert或append）時(shí)，如果元素存儲(chǔ)區(qū)滿就換一塊4倍大的存儲(chǔ)區(qū)。但如果此時(shí)的表已經(jīng)很大（目前的閾值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現(xiàn)過(guò)多空閑的存儲(chǔ)位置。