散列字符串向量的最佳方式不是很长（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）？

回答

相关问题