• 數(shù)組是將元素在內(nèi)存中連續(xù)存放。
• 鏈表中的元素在內(nèi)存中不是順序存儲(chǔ)的，而是通過(guò)存在元素中的指針聯(lián)系到一起。

• 數(shù)組必須事先定義固定的長(zhǎng)度，不能適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況。當(dāng)數(shù)據(jù)增加時(shí)，可能超出原先定義的元素個(gè)數(shù)；當(dāng)數(shù)據(jù)減少時(shí)，造成內(nèi)存浪費(fèi)。
• 鏈表動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配，可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況。

• (靜態(tài))數(shù)組從棧中分配空間, 對(duì)于程序員方便快速,但是自由度小
• 鏈表從堆中分配空間, 自由度大但是申請(qǐng)管理比較麻煩。

數(shù)組和鏈表在存儲(chǔ)數(shù)據(jù)方面到底孰優(yōu)孰劣呢？根據(jù)數(shù)組和鏈表的特性，分兩類情況討論。

一、當(dāng)進(jìn)行數(shù)據(jù)查詢時(shí)，數(shù)組可以直接通過(guò)下標(biāo)迅速訪問(wèn)數(shù)組中的元素。而鏈表則需要從第一個(gè)元素開(kāi)始一直找到需要的元素位置，顯然，數(shù)組的查詢效率會(huì)比鏈表的高。

二、當(dāng)進(jìn)行增加或刪除元素時(shí)，在數(shù)組中增加一個(gè)元素，需要移動(dòng)大量元素，在內(nèi)存中空出一個(gè)元素的空間，然后將要增加的元素放在其中。同樣，如果想刪除一個(gè)元素，需要移動(dòng)大量元素去填掉被移動(dòng)的元素。而鏈表只需改動(dòng)元素中的指針即可實(shí)現(xiàn)增加或刪除元素。

那么，我們開(kāi)始思考：有什么方式既能夠具備數(shù)組的快速查詢的優(yōu)點(diǎn)又能融合鏈表方便快捷的增加刪除元素的優(yōu)勢(shì)？HASH呼之欲出。

所謂的hash，簡(jiǎn)單的說(shuō)就是散列，即將輸入的數(shù)據(jù)通過(guò)hash函數(shù)得到一個(gè)key值，輸入的數(shù)據(jù)存儲(chǔ)到數(shù)組中下標(biāo)為key值的數(shù)組單元中去。

我們發(fā)現(xiàn)，不相同的數(shù)據(jù)通過(guò)hash函數(shù)得到相同的key值。這時(shí)候，就產(chǎn)生了hash沖突。解決hash沖突的方式有兩種。一種是掛鏈?zhǔn)?，也叫拉鏈法。掛鏈?zhǔn)降乃枷朐诋a(chǎn)生沖突的hash地址指向一個(gè)鏈表，將具有相同的key值的數(shù)據(jù)存放到鏈表中。另一種是建立一個(gè)公共溢出區(qū)。將所有產(chǎn)生沖突的數(shù)據(jù)都存放到公共溢出區(qū)，也可以使問(wèn)題解決。

hash表其實(shí)是結(jié)合了數(shù)組和鏈表的優(yōu)點(diǎn)，進(jìn)行的折中方案。平衡了數(shù)組和鏈表的優(yōu)缺點(diǎn)。hash的具體實(shí)現(xiàn)有很多種，但是需要解決沖突的問(wèn)題。?

不相同的數(shù)據(jù)通過(guò)hash函數(shù)得到相同的key值。這時(shí)候，就產(chǎn)生了hash沖突。解決hash沖突的方式有兩種。一種是掛鏈?zhǔn)剑步欣湻?。掛鏈?zhǔn)降乃枷朐诋a(chǎn)生沖突的hash地址指向一個(gè)鏈表，將具有相同的key值的數(shù)據(jù)存放到鏈表中。另一種是建立一個(gè)公共溢出區(qū)。將所有產(chǎn)生沖突的數(shù)據(jù)都存放到公共溢出區(qū)，也可以使問(wèn)題解決。