哈希表如何工作？這是不是比快「SELECT *從..」

比方說，我有：哈希表如何工作？這是不是比快「SELECT *從..」

 
Key | Indexes | Key-values 
----+---------+------------ 
001 | 100001 | Alex 
002 | 100002 | Micheal 
003 | 100003 | Daniel

比方說，我們要搜索001，怎麼辦使用哈希表的快速搜索的過程？

是不是像我們在mysql中使用「SELECT * from ..」一樣？我讀了很多，他們說，「SELECT *」從頭到尾搜索，但哈希表不是？爲什麼和如何？

通過使用散列表，我們是減少我們正在搜索的記錄？怎麼樣？

任何人都可以演示如何在mysql查詢代碼中插入和檢索哈希表進程？例如，

SELECT * from table1 where hash_value="bla" ...

另一種情形：如果索引像S0001，S0002，T0001，T0002等在MySQL中我可以使用：

SELECT * from table WHERE value = S*

是不是一樣快？

來源

2009-02-12 roa3

一個簡單的散列表的工作原理是將項目保留在幾個列表中，而不僅僅是一個。它使用非常快且可重複的（即非隨機）方法來選擇保留每個項目的列表。因此，當再次找到該項目時，它會重複該方法以發現要查找的列表，然後在該列表中執行正常（慢速）線性搜索。

通過將項目分成17名列表，搜索變成17倍的速度，這是一個很好的改進。

雖然當然如果列表是大致相同的長度，所以要選擇分發列表之間的項目的一個很好的方法是很重要的，這是唯一的真實。

在您的示例表，第一欄是關鍵，我們需要找到該項目的東西。假設我們將保留17個列表。爲了插入某些東西，我們對被稱爲散列的鍵執行操作。這只是將密鑰變成數字。它不會返回一個隨機數，因爲它必須始終爲相同的密鑰返回相同的數字。但與此同時，這些數字必須「廣泛傳播」。

然後我們得到的號碼和使用模量萎縮下來到我們的列表的大小：

Hash(key) % 17

這一切都發生非常快。我們的名單是一個數組，因此：

_lists[Hash(key % 17)].Add(record);

再後來，使用該鍵查找項目：

Record found = _lists[Hash(key % 17)].Find(key);

注意，每個列表可以只是任何容器類型，或鏈表你手寫的課程。當我們在該列表中執行Find時，它會以較慢的方式工作（檢查每條記錄的關鍵字）。

來源

2009-02-12 08:59:49

注意，如果有任何部分令人困惑，請留下評論，我會盡力改進。 – 2009-02-12 09:22:04

散列表非常適合在O（1）成本中查找條目，其中密鑰（用於散列）已知。它們廣泛用於收集庫和數據庫引擎。你應該能夠在互聯網上找到關於它們的大量信息。你爲什麼不開始Wikipedia或只是做一個谷歌搜索？

我不知道mysql的細節。如果在那裏有一個稱爲「散列表」的結構，那可能是一種使用散列來定位鍵的表。我相信別人會告訴你這件事。 =）

編輯:(回覆評論）

好的。我會盡量做出一個非常簡單的解釋：散列表是基於鍵的函數定位條目的表。例如，假設你想存儲關於一組人的信息。如果將它存儲在一個普通的未排序數組中，則需要依次遍歷這些元素以查找要查找的條目。平均而言，這需要N/2次比較。

如果您將所有條目都放在索引的基礎上，這些條目基於人名的第一個字符。（A = 0，B = 1，C = 2等），只要知道名字，就可以立即找到正確的條目。這是基本的想法。您可能會意識到，爲了支持具有相同首字母的多個條目，需要進行一些特殊處理（重新哈希或允許條目列表）。如果你有一個尺寸合適的散列表，你應該能夠直接找到你正在搜索的項目。這意味着大約只有一個比較，就是我剛剛提到的特殊處理的免責聲明。

來源

2009-02-12 07:01:25 SteinNorheim

我已經閱讀http://en.wikipedia.org/wiki/Hash_table和一些在互聯網上的研究，但是我無法理解搜索過程如何被固定的想法？ – roa3 2009-02-12 07:32:17

我想你可以使用散列函數來獲取你想選擇的ID。像

SELECT * FROM表WHERE值= hash_fn（whatever_input_you_build_your_hash_value_from）

然後，你不需要知道你要選擇的行的id，可以做一個精確的查詢。既然你知道這個行總是會有相同的id，因爲你建立了散列值表單，並且你總是可以通過散列函數重新創建這個id。

但是根據在桌子上，hashvalues的最大數量的大小，這並不總是正確的（你經常有「X MOD哈希表大小的」在某處你的哈希值）。爲了照顧到這一點，每次獲得具有相同ID的兩個值時，您應該使用確定性策略。您應該檢查Wikipedia以獲取有關此策略的更多信息，其稱爲衝突處理，並應在散列表的相同文章中提及。

的MySQL可能使用哈希表的地方，因爲的O（上）上述（1）功能norheim.se。

來源

2009-02-12 07:37:23 jowi

使用該策略來「優化」數據庫正在引發災難。數據庫的工作是快速簡單地檢索數據。像這樣的「捷徑」通常只會削弱它，使其工作變得更加困難。 – kquinn 2009-02-12 07:44:42

不用擔心MySQL在內部正在做什麼來快速定位記錄。數據庫的工作就是爲你做這種事情。只需運行一個SELECT [columns] FROM table WHERE [condition];查詢，並讓數據庫爲您生成查詢計劃。請注意，您不希望使用SELECT *，因爲如果您向該表中添加一列，該列將打破依賴於某個特定順序的特定列數的所有舊查詢。你需要知道什麼是索引是什麼，以及如何使用它們，以及如何使用這些索引。他們工作。如果一個表在WHERE子句中涉及的列沒有索引，那麼就像你說的那樣，數據庫將不得不搜索表中的每一行來查找符合條件的行。但是，如果是的索引，數據庫將搜索索引以查找所需行的確切位置，並直接跳轉到它們。索引通常實現爲B+-trees，這是一種使用極少數比較來查找特定元素的搜索樹。搜索特定鍵的B樹非常快。 MySQL也能夠使用散列索引，但這些數據庫使用往往會比較慢。哈希索引通常只在長鍵（特別是字符串）上才能很好地執行，因爲它們將鍵的大小減小到固定的哈希大小。對於整數和實數等數據類型，其定義明確且長度固定，B樹的易搜索性通常會提供更好的性能。

你可能想看看在索引的MySQL manual和PostgreSQL manual的章節。

來源

2009-02-12 07:42:25 kquinn

http://en.wikipedia.org/wiki/Hash_table

哈希表可以被用作存儲器內數據結構。散列表也可以用於持久數據結構; database indices有時使用基於散列表的基於磁盤的數據結構，儘管balanced trees更受歡迎。

來源

2009-02-12 07:45:54

哈希表如何工作？這是不是比快「SELECT *從..」

回答

相關問題