有點意思5792
哈希來自英文hash的翻譯。其實恰如其分應該叫散列。散列的目的就是找到一個函數能夠將一堆數字均勻分佈在一維數組裡。理想狀態大家存儲的位置是不同的，否則哈希函數比較糟糕。但是當兩個數字經過一次哈希發現存在同一個數組裡，還會二次哈希把他存在另外一個不同地方，這就是所謂雙哈希。但是影響哈希存儲的最關鍵因素是數組大小，當足夠大大家發生碰撞機會比較少，這就是為什麼內存數據庫，key值達到內存70%就要擴容。剛才看到樓上說的太簡單而且概念有些錯誤忍不住發表兩句。我們很少會用到數組加鏈表方式，因為查詢不穩定。基本通過空間換時間才能達到大o常數效率
我頭新條聞
哈希表是根據關鍵值(key)來直接訪問目標值(value)的一種數據結構。其特點就在於能夠快捷的實現信息的查詢和檢索。
比如我們在手機中存放的通訊錄就是用哈希表來實現的，即我們輸入一個聯繫人的姓名，就能返回相應的電話號碼。用哈希表實現的過程就是，將聯繫人姓名的字符通過一個哈希函數，映射成一個整數（哈希碼），然後根據哈希碼來索引出電話號碼。比如哈希碼為5，就表示是在存儲位置為5，因此我們就能直接取出該位置的值，並返回結果。
那麼實現哈希表的關鍵就在於哈希函數的構建，也就是如何建立一個合適的索引來滿足如下條件：
1）同一個鍵每次輸入到哈希函數中，其對應的哈希碼也必須相同；
2）不同鍵對應的哈希碼不能相同。
第一個條件意味著哈希函數必須是確定性的；第二個條件則要求不能出現哈希衝突。當兩個或更多個鍵產生相同的哈希碼時就會發生衝突（hash collisions）。
比如我們現在考慮建立一個簡單的哈希表來查詢年齡,{Jim：5, Davis：7, Taylor:12, Bob:3}，如果我們選擇哈希函數為輸入鍵值的字符個數。那麼在建立哈希表時，就講Jim存放在位置3處，Jack存放在位置4處。而這樣的話Jim和Bob的存儲位置就會發生衝突，不符合哈希函數的要求。但是如果我們將哈希函數替換為首字母順序存放，在這個數據中就沒有哈希衝突了。
然而萬一無法避免哈希衝突的話，我們可以用鏈接和線性探測的方法來避免哈希值發生碰撞。
鏈接就是將發生衝突的鍵值直接鏈接在鏈表的尾部；線性探測則是，如果在位置i處發生衝突，那麼就檢查i+1處是否為空，為空的話就將衝突鍵值放入其中，否則繼續檢查下一個。
ICMLL實驗室
一個簡單的例子
我們生活中如何使用哈希的一些例子包括：
在大學中，每個學生都會被分配一個唯一的卷號，可用於檢索有關它們的信息。
在圖書館中，每本書都被分配了一個唯一的編號，可用於確定有關圖書的信息，例如圖書館中的確切位置或已發給圖書的用戶等。
在這兩個例子中，學生和書籍都被分成了一個唯一的數字。
假設您有一個對象，並且您想為其分配一個鍵以便於搜索。 要存儲鍵/值對，您可以使用一個簡單的數組，如數據結構，其中鍵（整數）可以直接用作存儲值的索引。 但是，如果密鑰很大並且無法直接用作索引，則應使用哈希（Hashing）。
在哈希中，通過使用哈希函數將大鍵轉換為小鍵。 然後將這些值存儲在稱為哈希表的數據結構中。 哈希的想法是在數組中統一分配條目（鍵/值對）。 為每個元素分配一個鍵（轉換鍵）。 通過使用該鍵，您可以在O（1）時間內訪問該元素。 使用密鑰，算法會計算一個索引，該索引可以找到或插入條目的位置。
哈希一般分兩步執行：
通過使用哈希函數將元素轉換為整數。 此元素可用作存儲原始元素的索引，該元素屬於哈希表。
元素存儲在哈希表中，可以使用哈希鍵快速檢索它。
hash = hashfunc（key）
index = hash％array_size
在此方法中，哈希與數組大小無關，然後通過使用模運算符（％）將其縮減為索引（介於0和array_size - 1之間的數字）。
應用場景
關聯數組：哈希表通常用於實現許多類型的內存表。 它們用於實現關聯數組（索引是任意字符串或其他複雜對象的數組）。
數據庫索引：哈希表也可以用作基於磁盤的數據結構和數據庫索引（例如在dbm中）。
高速緩存：哈希表可用於實現高速緩存，即用於加速對數據的訪問的輔助數據表，其主要存儲在較慢的介質中。
對象表示：一些動態語言（如Perl，Python，JavaScript和Ruby）使用哈希表來實現對象。
提升速度：哈希函數用於各種算法，以使其計算更快。
我會在這裡發佈所有與科技、科學有關的有趣文章，歡迎訂閱我的頭條號。偶爾也回答有趣的問題，有問題可隨時在評論區回覆和討論。
