數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)在內(nèi)存中存儲(chǔ)的一種方式，如果數(shù)據(jù)在內(nèi)存中的存儲(chǔ)是地址連續(xù)的漠趁，比如內(nèi)存中從0到9的位置就用來存儲(chǔ)1,2,3, ... 8,9,10這10個(gè)數(shù)字扁凛，那么這種存儲(chǔ)方式就是數(shù)組。如果數(shù)據(jù)在內(nèi)存中存儲(chǔ)地址是不連續(xù)的闯传，而是有空位就放的谨朝，但是每個(gè)位置都保存下一個(gè)存儲(chǔ)位置的地址，那么這種存儲(chǔ)方式就是鏈表甥绿。
| 數(shù)組 | 鏈表 | |
|---|---|---|
| 讀取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 刪除 | O(n) | O(1) |
如上表所示字币，在查找某個(gè)數(shù)據(jù)時(shí)，數(shù)組可以根據(jù)下標(biāo)直接找出來共缕，即O(1), 而鏈表需要遍歷洗出，挨個(gè)查過去，算法運(yùn)行時(shí)間為O(n)图谷。插入數(shù)據(jù)的時(shí)候翩活，如果插入的不是首尾的位置，數(shù)組就需要相應(yīng)的把插入位置后面的數(shù)據(jù)向后移蜓萄，為O(n)隅茎，而列表插入的時(shí)候只需要把上一個(gè)數(shù)據(jù)的指向位置改成插入的位置澄峰，再把插入位置指向下一個(gè)數(shù)據(jù)的位置即可嫉沽。刪除的時(shí)候，數(shù)組如果刪除的不是最后一個(gè)俏竞，也是需要把相應(yīng)的數(shù)據(jù)前移绸硕，而列表只需要把刪除位置上一個(gè)位置指向刪除位置的下一個(gè)位置的地址即可，為O(1)魂毁。
在存儲(chǔ)數(shù)據(jù)時(shí)玻佩，還有一種映射的結(jié)構(gòu)，叫做散列表席楚。散列表就是一個(gè)鍵對(duì)應(yīng)一個(gè)值咬崔，比如一斤蘋果5塊錢，把水果的名稱蘋果作為鍵，而水果的價(jià)格作為值垮斯，這兩個(gè)形成一個(gè)映射關(guān)系郎仆，只要給出蘋果這個(gè)鍵，就立馬能夠知道這個(gè)水果的價(jià)格是5塊錢一斤兜蠕。如果把所有水果都使用這種映射結(jié)構(gòu)存儲(chǔ)扰肌，每次只需要把水果名稱輸入進(jìn)去，就可以立刻得到水果的價(jià)格熊杨，即算法運(yùn)行時(shí)間是O(1)曙旭。
當(dāng)然，散列表在使用的時(shí)候也會(huì)有其他問題晶府，比如用來記錄不同的人的投票情況桂躏，如果一個(gè)人已經(jīng)投過票了，再次進(jìn)行投票的話郊霎，就會(huì)和之前重復(fù)沼头，這時(shí)應(yīng)該不允許這個(gè)人再次投票。
還有如果兩個(gè)鍵在散列表做映射的時(shí)候书劝，映射的是同一個(gè)位置进倍，就會(huì)產(chǎn)生沖突。比較簡(jiǎn)單的解決方法就是在這個(gè)位置购对，做一個(gè)鏈表猾昆，如果兩個(gè)鍵映射到同一個(gè)位置的話，就把個(gè)兩個(gè)鍵用鏈表保存起來骡苞。但這樣又出現(xiàn)一個(gè)新問題垂蜗，如果某個(gè)位置有特別多的映射，就是這個(gè)用來保存相同鍵位置的鏈表很長(zhǎng)解幽，而其他位置幾乎沒有保存鍵或者很少贴见，這樣這個(gè)散列表的性能反而不如鏈表和數(shù)組單獨(dú)使用了。這里有一個(gè)解決方法就是盡量使散列函數(shù)可以把鍵均勻的分布在不同的位置上躲株，還有就是計(jì)算當(dāng)前散列表的散列因子（散列表包含的元素?cái)?shù)/位置總數(shù)）片部，如果散列因子超過 0.7，就開始調(diào)整散列表的長(zhǎng)度霜定。
