有關散列及其用於數據壓縮的說明

Question

我正面臨使用散列的應用程序，但我仍無法弄清楚它是如何工作的。這是我的問題，散列用於生成一些索引，並使用這些索引訪問不同的表格，並在添加了使用索引獲得的每個表格的值之後，獲得我的最終值。這樣做是爲了減少內存需求。哈希函數的輸入是在應用程序的一個隨機常數和一些參數之間進行異或運算。

這是一個典型的哈希應用程序？我不明白的是如何使用散列可以減少內存需求？任何人都可以澄清這一點？

謝謝

Answer 1

單獨的散列與內存沒有任何關係。

它常用的是散列表。哈希表的工作方式是計算您正在關閉的內容的哈希值，然後將其用作數據結構的索引。

散列允許您將鍵（字符串等）縮減爲更緊湊的值，如整數或位集。

這可能是您所指的內存節省 - 將大鍵減少爲簡單整數。

但是請注意，散列並不是唯一的！一個好的哈希算法可以最大限度地減少衝突，但它們並不是要減少到一個唯一值 - 這樣做是不可能的（例如，如果你的哈希輸出一個32位整數，你的哈希將只有2^32個唯一值）。

Answer 2

難道你是在談論一個bloom filter？這使用散列函數來獲得空間有效的方式來測試集合的成員資格。如果是這樣，請參閱鏈接以獲取解釋。

Answer 3

大多數好的散列實現都是內存效率低下的，否則會涉及更多的計算 - 而這恰恰會丟失散列點。

散列實現用於處理效率，因爲它們將爲插入，刪除和檢索等操作提供持續運行時間。

您可以考慮哈希的質量，使得您的所有數據（無論類型或大小）始終以單個固定長度格式表示。

Answer 4

如果所做的哈希不是構建真正的哈希表，而是僅在字符串/內存塊表中創建索引，則可以解釋這一點。如果數據中有20次相同的字符串（或內存序列），然後用該哈希/表索引替換了該字符串的所有20個實例，則可以用這種方式實現數據壓縮。但是，如果每個散列值在該表中包含一個實際的碰撞鏈，那麼我剛描述的並不是發生了什麼;在這種情況下，哈希的原因很可能是加速執行（通過提供對存儲值的快速訪問），而不是壓縮。