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

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

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

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

一、當進行數(shù)據(jù)查詢時，數(shù)組可以直接通過下標迅速訪問數(shù)組中的元素。而鏈表則需要從第一個元素開始一直找到需要的元素位置，顯然，數(shù)組的查詢效率會比鏈表的高。

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

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

所謂的hash，簡單的說就是散列，即將輸入的數(shù)據(jù)通過hash函數(shù)得到一個key值，輸入的數(shù)據(jù)存儲到數(shù)組中下標為key值的數(shù)組單元中去。

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

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

不相同的數(shù)據(jù)通過hash函數(shù)得到相同的key值。這時候，就產(chǎn)生了hash沖突。解決hash沖突的方式有兩種。一種是掛鏈式，也叫拉鏈法。掛鏈式的思想在產(chǎn)生沖突的hash地址指向一個鏈表，將具有相同的key值的數(shù)據(jù)存放到鏈表中。另一種是建立一個公共溢出區(qū)。將所有產(chǎn)生沖突的數(shù)據(jù)都存放到公共溢出區(qū)，也可以使問題解決。