在我們編程的世界裡數據的基本組織可以說有三種形式。
其他任何的數據組織形式都可以看作是這三種數據組織形式的組合變體。
結構體(或對象)可以是基本數據類型或者其他結構體(或對象)的組合。結構體或對象一般用來描述一個複雜數據實體。
數組一般是一組同類型的變量的集合，在內存中表現為一片連續的空間，因為空間是連續的，且每一個數據單元佔的內存空間的大小是相等的，所以可以根據地址的偏移對數據元素實現快速訪問，但是當需要插入或者刪除一個元素的時候，則需要對目標元素的之後的所有元素進行移動了。 鍊表的單個節點一般為結構體或者對象，因為鍊表的單個節點除了需要保存數據之外還需要維護它的相鄰節點的關係，如果想獲得鍊表中的某個節點的值，需要從鍊表的頭結點開始遍歷，直到找到需要的東西，而插入或者刪除某個節點的話，需要找到相應的節點，修改其以及其相鄰節點的相關指針的引用即可。
像其他的數據結構，比如 隊列，棧，樹，都可以通過數組或者鍊表來組織，並實現相應的操作功能。
二.Hash Table這個世界上沒有十全十美的東西，所以我們要學會取捨。任何技術的實現都沒有最好的只要最合適的，也就說實現的最佳方案是和應用場景息息相關的。
很多時候，我們想對數據進行快速的存取（比如緩存的實現），並用一個key來標記自己存取的數據。我們可以把它叫做key-value的結構。
說到「快速」我們很快想到數組，因為數組可以在O(1)的時間複雜內完成指定位置元素的讀寫操作。
所以在理想狀態，如果一個數組足夠長，且存在一個函數可以將每一個key映射到唯一的一個數組下標，那麼我們就可以很完美的解決問題。但往往資源都是有限的，我們沒有那麼大的空間，也不能設計一個無比負責的映射算法保證每一個key對應到一個唯一的數組下標。所以我們會選擇一些折中的方案。
hash table便是為解決這類問題而存在的。
1.哈希函數Hash或者你可以翻譯成散列或者雜湊，hash操作其本質上就是將一個數據映射成另一個數據，通常情況下原數據的長度比hash後的數據容量大。 這種映射的關係我們叫做哈希函數。
一般情況下 哈希函數的輸入可能的總數要遠遠多於哈希值所能表示的總數，所以就有可能兩個不同的輸入對應同一個哈希值，通常把具有不同關鍵碼而具有相同哈希值的記錄稱作「同義詞」。 在信息安全領域中也經常使用到哈希函數，不過需要使用的是單向哈希函數，就是無法通過哈希的結果反推出輸入，所以經常應用於密碼的加密，傳輸內容的完整性檢查，在安全領域常用的哈希算法有 MD5，SHA1等。 在哈希表的應用中，哈希函數常用餘數法進行，也就是通過求模的方式算出哈希值。
2.哈希表哈希表是一種數據結構，實現key-value的快速存取。之前說過數組可以實現快速存取，所以哈希表肯定會使用到數組。在這裡，我們把每一個數組的單元叫做一個bucket（桶）。
構造哈希函數 這裡哈希函數的作用就是將key映射到一個存儲地址。所以構造一個哈希表我們得先構造哈希函數。 如果一個key哈希後對應地址中已經存放了值了，這種情況我們叫做哈希衝突（Hash collisions）。 如果存在一個哈希函數，使得每一個輸入都能對應到唯一的一個存儲單元中（沒有衝突），那麼這樣的哈希函數我們可以叫它完美哈希函數（Perfect Hash Function，簡稱PHF)。 但為了哈希函數簡單，運行速度快，往往不會使用完美哈希函數。所以衝突肯定會存在的，為了減少衝突，我們希望哈希函數的結果均勻的分布在地址單元的空間中。這樣可以有效的減少衝突。
裝填因子Load factor a=哈希表的實際元素數目(n)/ 哈希表的容量(m) a越大，哈希表衝突的概率越大，但是a越接近0，那麼哈希表的空間就越浪費。 一般情況下建議Load factor的值為0-0.7，Java實現的HashMap默認的Load factor的值為0.75，當裝載因子大於這個值的時候，HashMap會對數組進行擴張至原來兩倍大。
衝突解決 既然衝突不可避免，那麼我們就必須對衝突進行解決(總不能把之前的內容覆蓋掉把), 解決衝突的方式主要分兩類 開放定址法(Open addressing)這種方法就是在計算一個key的哈希的時候，發現目標地址已經有值了，即發生衝突了，這個時候通過相應的函數在此地址後面的地址去找，直到沒有衝突為止。這個方法常用的有線性探測，二次探測，再哈希。 這種解決方法有個不好的地方就是，當發生衝突之後，會在之後的地址空間中找一個放進去，這樣就有可能後來出現一個key哈希出來的結果也正好是它放進去的這個地址空間，這樣就會出現非同義詞的兩個key發生衝突。
連結法(Separate chaining)連結法是通過數組和鍊表組合而成的。當發生衝突的時候只要將其加到對應的鍊表中即可。
與開放定址法相比，連結法有如下幾個優點：
①連結法處理衝突簡單，且無堆積現象，即非同義詞決不會發生衝突，因此平均查找長度較短；
②由於連結法中各鍊表上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；
③開放定址法為減少衝突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而連結法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；
④在用連結法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪去鍊表上相應的結點即可。而對開放地址法構造的散列表，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之後填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理衝突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。
當然連結法也有其缺點，拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的衝突，從而提高平均查找速度。