牛客網Java刷題知識點之數組、連結清單、哈希表、 紅黑二叉樹

　首先來說一個非常形象的例子，來說明下數組和連結清單。

上體育課的時候，老師說：你們站一隊，每個人記住自己是第幾個，我喊到幾，那個人就舉手，這就是數組。

老師說，你們每個人記住自己前面的人和後面的人，然後老師隻知道第一人是誰。 然後你們各自由活動，老師要找某一個人，是不是每次都是從第一個開始往自己身後的人開始傳達？這就是連結清單。

老師說： 大家1，2，3，4報數，凡是報1，為1隊，凡是報2的為2隊.......  這就是散列（哈希）。而這個4就相當于預定義好的桶的個數。

程式中，存放指定的資料最常用的資料結構有兩種：數組和連結清單。

數組和連結清單的差別：

1、  數組是将元素在記憶體中連續存放。

      連結清單中的元素在記憶體中不是順序存儲的，而是通過存在元素中的指針聯系到一起。

2、  數組必須事先定義固定的長度，不能适應資料動态的增減的情況。當資料增加時，可能超出原先定義的元素個數；當資料減少時，造成記憶體浪費； 

連結清單動态地進行存儲配置設定，可以适應資料動态地增減的情況。

3、（靜态）數組從棧中配置設定空間，對于程式員友善快速，但是自由度小；

連結清單從堆中配置設定空間，自由度大但是申請管理比較麻煩。

數組和連結清單在存儲資料方面到底誰好？根據數組和連結清單的特性，分兩種情況讨論：

1、當進行資料查詢時，數組可以直接通過下标迅速通路數組中的元素。

     而連結清單則需要從第一個元素開始一直找到需要的元素位置，

　　      顯然，數組的查詢效率會比連結清單的高。

　　2、當進行增加或删除元素時，在數組中增加一個元素，需要移動大量元素，在記憶體中空出一個元素的空間，然後将要增加的元素放在其中。

             同樣，如果想删除一個元素，需要移動大量去填掉被移動的元素，而連結清單隻需改動元素中的指針即可實作增加或删除元素。

　　那麼哈希表，是既能具備數組的快速查詢的優點，又能融合連結清單友善快捷的增加删除元素的優勢。

所謂的hash，簡單的說就是散列，即将輸入的資料通過hash函數得到一個key值，輸入的資料存儲到數組中下标的key值的數組單元中去。　

　　Java中資料存儲方式最底層的兩種結構，一種是數組，另一種就是連結清單。

　　數組的特點：連續空間，尋址迅速，但是在删除或者添加元素的時候需要有較大幅度的移動，是以查詢速度快，增删較慢。

　　而連結清單正好相反，由于空間不連續，尋址困難，增删元素隻需修改指針，是以查詢慢、增删快。

　　有沒有一種資料結構來綜合一下數組和連結清單，以便發揮他們各自的優勢？答案是肯定的！就是：哈希表。

　　哈希表具有較快（常量級）的查詢速度，及相對較快的增删速度，是以很适合在海量資料的環境中使用。一般實作哈希表的方法采用“拉鍊法”，我們可以了解為“連結清單的數組”，如下圖：

　　哈希表。如拿HashMap來說。

　　從上圖中，我們可以發現哈希表是由數組  +   連結清單組成的，一個長度為16的數組中，每個元素存儲的是一個連結清單的頭結點。那麼這些元素是按照什麼樣的規則存儲到數組中呢。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數組長度取模得到。比如上述哈希表中，12%16=12，28%16=12，108%16=12，140%16=12。是以12、28、108以及140都存儲在數組下标為12的位置。它的内部其實是用一個Entity數組來實作的，屬性有key、value、next。

本文轉自大資料躺過的坑部落格園部落格，原文連結：http://www.cnblogs.com/zlslch/p/7635822.html，如需轉載請自行聯系原作者