?

?

?　　不多說，直接上干貨！

　　首先來說一個非常形象的例子，來說明下數(shù)組和鏈表。

　　上體育課的時候，老師說：你們站一隊(duì)，每個人記住自己是第幾個，我喊到幾，那個人就舉手，這就是數(shù)組。
　　老師說，你們每個人記住自己前面的人和后面的人，然后老師只知道第一人是誰。 然后你們各自由活動，老師要找某一個人，是不是每次都是從第一個開始往自己身后的人開始傳達(dá)？這就是鏈表。
　　老師說： 大家1，2，3，4報數(shù)，凡是報1，為1隊(duì)，凡是報2的為2隊(duì)....... ?這就是散列（哈希）。而這個4就相當(dāng)于預(yù)定義好的桶的個數(shù)。

?

程序中，存放指定的數(shù)據(jù)最常用的數(shù)據(jù)結(jié)構(gòu)有兩種：數(shù)組和鏈表。

?

數(shù)組和鏈表的區(qū)別：
　　1、 ?數(shù)組是將元素在內(nèi)存中連續(xù)存放。
　　 ? ? ? 鏈表中的元素在內(nèi)存中不是順序存儲的，而是通過存在元素中的指針聯(lián)系到一起。
　　2、 ?數(shù)組必須事先定義固定的長度，不能適應(yīng)數(shù)據(jù)動態(tài)的增減的情況。當(dāng)數(shù)據(jù)增加時，可能超出原先定義的元素個數(shù)；當(dāng)數(shù)據(jù)減少時，造成內(nèi)存浪費(fèi)；
　　　　鏈表動態(tài)地進(jìn)行存儲分配，可以適應(yīng)數(shù)據(jù)動態(tài)地增減的情況。
　　3、（靜態(tài)）數(shù)組從棧中分配空間，對于程序員方便快速，但是自由度小；
　　　　鏈表從堆中分配空間，自由度大但是申請管理比較麻煩。

?

數(shù)組和鏈表在存儲數(shù)據(jù)方面到底誰好？根據(jù)數(shù)組和鏈表的特性，分兩種情況討論：
　　1、當(dāng)進(jìn)行數(shù)據(jù)查詢時，數(shù)組可以直接通過下標(biāo)迅速訪問數(shù)組中的元素。
　　 ? ? ?而鏈表則需要從第一個元素開始一直找到需要的元素位置，
　　 ? ? ?顯然，數(shù)組的查詢效率會比鏈表的高。

　　2、當(dāng)進(jìn)行增加或刪除元素時，在數(shù)組中增加一個元素，需要移動大量元素，在內(nèi)存中空出一個元素的空間，然后將要增加的元素放在其中。

? ? ? ? ? ? ?同樣，如果想刪除一個元素，需要移動大量去填掉被移動的元素，而鏈表只需改動元素中的指針即可實(shí)現(xiàn)增加或刪除元素。

?

?

　　那么哈希表，是既能具備數(shù)組的快速查詢的優(yōu)點(diǎn)，又能融合鏈表方便快捷的增加刪除元素的優(yōu)勢。
　　所謂的hash，簡單的說就是散列，即將輸入的數(shù)據(jù)通過hash函數(shù)得到一個key值，輸入的數(shù)據(jù)存儲到數(shù)組中下標(biāo)的key值的數(shù)組單元中去。　

?

?

?

?

　　Java中數(shù)據(jù)存儲方式最底層的兩種結(jié)構(gòu)，一種是數(shù)組，另一種就是鏈表。

　　數(shù)組的特點(diǎn)：連續(xù)空間，尋址迅速，但是在刪除或者添加元素的時候需要有較大幅度的移動，所以查詢速度快，增刪較慢。

　　而鏈表正好相反，由于空間不連續(xù)，尋址困難，增刪元素只需修改指針，所以查詢慢、增刪快。

　　有沒有一種數(shù)據(jù)結(jié)構(gòu)來綜合一下數(shù)組和鏈表，以便發(fā)揮他們各自的優(yōu)勢？答案是肯定的！就是：哈希表。

　　哈希表具有較快（常量級）的查詢速度，及相對較快的增刪速度，所以很適合在海量數(shù)據(jù)的環(huán)境中使用。一般實(shí)現(xiàn)哈希表的方法采用“拉鏈法”，我們可以理解為“鏈表的數(shù)組”，如下圖：

　　哈希表。如拿HashMap來說。

?

　　從上圖中，我們可以發(fā)現(xiàn)哈希表是由數(shù)組 ?+ ? 鏈表組成的，一個長度為16的數(shù)組中，每個元素存儲的是一個鏈表的頭結(jié)點(diǎn)。那么這些元素是按照什么樣的規(guī)則存儲到數(shù)組中呢。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數(shù)組長度取模得到。比如上述哈希表中，12%16=12，28%16=12，108%16=12，140%16=12。所以12、28、108以及140都存儲在數(shù)組下標(biāo)為12的位置。它的內(nèi)部其實(shí)是用一個Entity數(shù)組來實(shí)現(xiàn)的，屬性有key、value、next。

總結(jié)

以上是生活随笔為你收集整理的牛客网Java刷题知识点之数组、链表、哈希表、 红黑二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。