散列字符串向量的最佳方式不是很長（urls）？

我現在正在處理網址分類。我用「/？」分區url，生成一堆零件。在這個過程中，我需要將第一部分散列到第k個部分，例如k = 2，然後對於「http://stackoverflow.com/questions/ask」，關鍵字是一個字符串向量「stackoverflow.com問題」。目前，散列就像哈希。但是它消耗了大量的內存。我想知道MD5是否可以提供幫助，或者是否有其他選擇。實際上，只要區分不同的密鑰，我不需要精確地恢復密鑰。謝謝！散列字符串向量的最佳方式不是很長（urls）？

來源

2011-04-20 zcg

'目前，散列就像哈希。「 - 我不知道你是什麼意思。什麼是消耗大量的內存，存儲散列碼或計算它們？ – 2011-04-20 20:34:15

如果您試圖圍繞查找/散列進行優化，以下是一些需要考慮的事項。你的應用程序在哪裏花費大部分時間/內存 - 生成哈希或查找它們？當你的列表接近無窮大（或你的桶大小）時，你將會遇到某種形式的衝突。你的應用程序能處理這個嗎如果不行，那麼在某個時候你可能會遇到這個bug，並且可能很難調試。如果可以，並且經常發生，那麼您可能需要研究散列算法，以便爲您的數據提供良好的分佈。 – 2011-04-21 00:24:24

它消耗了大量的內存

如果你的代碼已經工作的，你可能要考慮留原樣。如果你沒有目標，你不會知道你什麼時候完成。你確定「很多」在你的案例中是「太多」的代名詞嗎？

如果你決定你真的需要改變你的工作代碼，你應該考慮各種各樣的您有可用的選項，而不是把別人的話特定的算法：

等

不知道關於內存的影響，它肯定會改變你的PERF的個人資料，但你也可以考慮使用嘗試次數：

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

來源

2011-04-20 20:42:10

+1「如果沒有損壞，請不要修復」 – corsiKa 2011-04-20 20:47:27

MD5是東西一個很好的哈希代碼，其中安全性是不是一個問題。它的速度很快並且相當長（對於大多數應用來說，128位就足夠了）。此外，分佈非常好。

Adler32將是一個可能的選擇。這很容易實現，只需幾行代碼。它比MD5更快。對於很多應用程序來說足夠長/足夠好（儘管對於很多應用程序來說不是這樣）。（我知道Adler32嚴格來說不是一個哈希碼，但它對很多應用程序來說仍然可以）

但是，如果存儲散列碼耗費大量內存，則可以總是截斷散列碼，或者使用XOR來「收縮」它。例如。

uint8_t md5[16]; 
GetMD5(md5, ...); 

// use XOR to shrink the MD5 to 32 bits 
for (size_t i = 4; i < 16; i++) 
    md5[i % 4] ^= md5[i]; 

// assemble the parts into one uint32_t 
uint32_t const hash = md5[0] + (md5[1] << 8) + (md5[2] << 16) + (md5[3] << 24);

就我個人而言，我認爲MD5將會過度殺傷。看看Adler32，我認爲它會做的。

編輯

我必須糾正自己：Adler23是短字符串（小於幾千字節）一個相當糟糕的選擇。我完全忘記了這一點。但總是有顯而易見的：CRC32。並不像Adler23那麼快（與MD5的速度大致相同），但仍然可以很容易地實現，而且現在還有大量現有的各種許可證實施方案。

來源

2011-04-20 20:42:31

+1。 Adler32看起來像一個體面的選擇。它似乎符合我所假設的他的需要（在執行散列函數時輸出低內存，並輸出一個32位整數）。有很多其他選項適合相同的配置文件，但實現和調試看起來非常簡單，並且可能運行得很好。 – 2011-04-21 00:15:49

如果您只是試圖找出兩個URL是否相同，您是否考慮過存儲服務器IP地址的二進制版本？如果兩個服務器名稱解析爲相同的地址對於您的應用程序來說不正確或有優勢？

來源

2011-04-20 20:42:56 Jay

我不能假裝知道他的需求，但是當他試圖分開存儲由同一服務器提供服務的兩個URL時，這肯定不起作用。 – 2011-04-21 00:18:06

雖然有一個問題：URL：IP ist不是N：1映射，它是N：N。 – 2011-04-21 01:17:01

散列字符串向量的最佳方式不是很長（urls）？

回答

相關問題