我有一個散列表，我想存儲到磁盤。該列表看起來像這樣：我應該使用哪種數據結構來存儲散列值？

<16-byte key     > <1-byte result> 
a7b4903def8764941bac7485d97e4f76 04 
b859de04f2f2ff76496879bda875aecf 03 
etc...

有一百零五萬條目。目前我只是將它們存儲在一個文件中，每個條目17個字節乘以條目數量。該文件是幾十兆字節。我的目標是以一種先優化磁盤空間和查找時間的方式存儲它們。插入時間並不重要。

這樣做的最好方法是什麼？我希望文件儘可能小。多個文件也可以。帕特里夏特里？基數特里？

無論我得到什麼好建議，我都會實施和測試。我會在這裏發佈結果供所有人查看。

來源

2009-12-24 Eyal

請澄清對RAM使用的要求... – ThinkJet 2009-12-25 07:37:00

我建議密鑰是隨機的（例如GUID）。這是正確的？ – ThinkJet 2009-12-25 07:56:37

您可以按鍵排序條目並進行二分查找。

固定大小的鍵和數據條目意味着您可以非常快速地從一行跳到另一行，只存儲鍵和數據意味着您不會浪費元數據上的任何空間。

我不認爲你會在磁盤空間上做得更好，並且查找時間是O（log（n））。插入時間很長，但你說這沒有關係。

如果您真的願意容忍長訪問時間，請對錶格進行排序，然後將其塊化爲一定大小的塊並壓縮它們。在開始處將每個塊的偏移量*和開始/結束鍵存儲在文件的一部分中。使用這種方案，您可以在線性時間內找到包含所需密鑰的塊，然後在解壓縮塊內執行二進制搜索。根據您願意一次加載到內存中的文件大小來選擇塊大小。

使用現成的壓縮方案（如GZIP），您可以根據需要調整壓縮比率;更大的文件可能會有更快的查找時間。

我懷疑節省的空間會非常大，因爲你的結構似乎主要是哈希值。如果它們實際上是散列，它們是隨機的，並且不會非常好地壓縮。分揀有助於提高壓縮比，但不是一噸。

_{*使用標題查找要解壓縮和使用的塊的偏移量。}

來源

2009-12-24 08:39:47

這個怎麼樣：首先我存儲256個數字，每個4個字節。每個人都說有多少個密鑰以特定前綴開頭。因此，如果我有10個以0x00開頭的鍵和20個以0x01開頭的鍵，則該文件的前8個字節爲0x0000000a00000014。然後我存儲排序的鍵，但沒有第一個字節。總存儲量：256 * 4Bytes + N * 16Bytes。與N * 17Bytes比較，我已經保存了幾個megs。 – Eyal 2009-12-24 09:38:46

如果你的哈希值實際上是哈希值（因此基本上是隨機的），你不會看到太多的節省。不要忽視具有多個文件的實際磁盤成本。但是，如果你的密鑰不是散列，你可以利用它來壓縮密鑰並節省空間。 – 2009-12-24 10:59:11

與N * 17相比，只有一個大小爲256 * 4 + N * 16的文件。 N> 100萬，已經是一筆不錯的儲蓄了！也許更好的辦法可以做... – Eyal 2009-12-24 11:15:34

簡單的方法是否可以工作並將它們存儲在sqlite database？我不認爲它會變小，但你應該得到非常好的查找性能，並且它很容易實現。

來源

2009-12-24 08:40:36 Nifle

首先 - 多個文件都不行，如果你想優化的磁盤空間，因爲簇大小的 - 當你創建一個大小約100個字節的文件，磁盤空間的每簇的大小減小 - 例如2kB的。

其次 - 在你的情況下，我會將所有表存儲在單個二進制文件中，只需按字節值按鍵排序即可。它會給你的長度正好等於entriesNumber * 17，這是最小的文件，如果你不想使用存檔，其次，可以使用非常快速搜索用時〜LOG2（entriesNumber），當你搜索鍵分割文件分爲兩部分，並將邊界上的按鍵與所需的按鍵進行比較。如果「邊框鍵」較大，則取第一部分文件，如果較大 - 則第二部分。再次分成兩部分，等等。所以你需要關於log2（entriesNumber）的讀操作來搜索單個密鑰。

來源

2009-12-24 08:46:41 user224564

500萬條記錄大約81MB - 可以在內存中使用數組。

正如你所描述的問題 - 它比哈希值更獨特的鍵。嘗試使用散列表訪問值（請參閱this link）。

如果有我的誤解，這是真正的散列 - 嘗試構建第二個散列水平高於此。

散列表也可以在磁盤上成功組織（例如作爲單獨的文件）。

加成具有良好的搜索性能和小的開銷

解決辦法是：

定義散列函數，從鍵生成整數值。根據值文件
排序的記錄，由該函數
存儲文件偏移量產生，其中每個散列值開始
要查找值：
4.1。使用函數
計算它的哈希值。查找文件中的偏移量
4.3。從該位置開始讀取文件中的記錄，直到未找到下一個鍵的鍵找到或偏移或文件結束。

有一些必須指出附加的東西：

哈希函數必須快速有效
Hash函數必須產生線性分佈的值或接近
表散列值偏移量可以放在分開的文件中
散列值偏移量表可以在應用程序開始時順序讀取整個排序文件並動態生成並存儲在內存中
在步驟4.3。記錄必須以塊爲單位，而不是一個一個地生效。理想情況下，一次將計算出的散列值全部讀取到內存中。

你可以找到一些哈希函數here的例子。

來源

2009-12-24 09:04:55 ThinkJet

你是對的，他們是唯一的鑰匙，不是任何東西的哈希。 – Eyal 2009-12-24 09:39:38

+1：在桌面/服務器系統上，「可以與內存中的數組一起使用」。如果嵌入式應用程序不是那麼多。 – 2010-07-19 08:22:22

與文件設計一樣，您越瞭解（並告訴我們）關於數據分佈越好。假設您的密鑰值均勻分佈在所有16字節密鑰的集合中 - 如果您要存儲散列表，則應該爲真 - 我建議將其他人已經建議的組合：

這樣的二進制數據屬於二進制文件;不要讓你的散列和值的簡單表示就像十六進制數字的字符串一樣欺騙你，認爲這是字符串數據;
文件大小是這樣的，整個shebang可以保存在任何現代PC或服務器和許多其他設備的內存中;
您的密鑰的前4個字節將可能密鑰的集合劃分爲16^4（= 65536）個子集;如果你的密鑰是均勻分佈的，並且你有5x10 6個條目，那麼每個子集約有76個條目;所以要爲每個子集創建一個包含空間的文件，例如100個條目;那麼：
在偏移量0處開始寫入前4個字節的所有條目0x0000;填充到100個條目（我認爲是1700個字節）與0;
在偏移1700開始寫的所有條目與領先的4個字節爲0x0001，墊，
重複你寫的所有數據，直到。

現在，您的查找變爲計算文件偏移量，然後掃描最多100個條目以找到所需的文件。如果速度不夠快，則使用16^5個子集，每個子集允許大約6個條目（6x16^5 = 6291456）。我想這會比二元搜索更快 - 但這只是一個猜測。

插入是一個問題，它取決於你對你的數據的知識，以決定是否新條目（a）需要重新排序的子集或（b）可以簡單地添加在該索引處的條目列表（這意味着在每次查找時掃描整個子集）。

如果空間非常重要，當然可以從條目中刪除前4個字節，因爲它們是通過計算文件中的偏移量來計算的。

我所描述的，不是非常好，是一個哈希表。

來源

2009-12-24 11:16:07

您的密鑰是128位，但如果您有最多10^7個條目，則只需要24位來索引它。

你可以做一個哈希表，或
使用賓利風格的展開二進制搜索（最多24個比較），如

這裏展開的循環（與32整數）。

int key[4]; 
int a[1<<24][4]; 

#define COMPARE(key, i) (key[0]>=a[i][0] && key[1]>=a[i][1] && key[2]>=a[i][2] && key[3]>=a[i][3]) 

i = 0; 
if (COMPARE(key, (i+(1<<23))) >= 0) i += (1<<23); 
if (COMPARE(key, (i+(1<<22))) >= 0) i += (1<<22); 
if (COMPARE(key, (i+(1<<21))) >= 0) i += (1<<21); 
... 
if (COMPARE(key, (i+(1<<3))) >= 0) i += (1<<3); 
if (COMPARE(key, (i+(1<<2))) >= 0) i += (1<<2); 
if (COMPARE(key, (i+(1<<1))) >= 0) i += (1<<3);

來源

2009-12-24 16:32:43

我應該使用哪種數據結構來存儲散列值？

回答

加成具有良好的搜索性能和小的開銷

相關問題