如何计算一个string列表的好散列码？
背景：
- 我有一个简短的string列表。
- string的数量并不总是相同的，但几乎总是“less数”的顺序，
- 在我们的数据库中将这些string存储在第二个规范化的表中
- 这些string写入数据库后永远不会更改。
我们希望能够在查询中快速匹配这些string，而无需进行大量的连接。
所以我正在考虑将所有这些string的哈希码存储在主表中，并将其包含在我们的索引中，因此只有在哈希码匹配时才能通过数据库处理联接。
那么如何获得一个好的散列码呢？ 我可以：
- 将所有string的哈希码加在一起
- XOR与每个string后面的结果相乘（用31表示）
- 把所有的string集合在一起，然后得到哈希码
- 其他方式
那么人们会怎么想呢？
最后，我只是连接string并计算连接的哈希码，因为它很简单，而且工作得很好。
（如果你在意我们正在使用.NET和SqlServer）
Bug！，Bug！
Eric Lippert 引用GetHashCode的指导原则和规则
System.String.GetHashCode的文档特别指出，两个相同的string可以在CLR的不同版本中具有不同的哈希代码，实际上它们的确可以。 不要在数据库中存储string散列，并期望它们永远是一样的，因为它们不会。
所以String.GetHashcode（）不应该用于这个。
标准的java练习，就是简单的写
final int prime = 31; int result = 1; for( String s : strings ) { result = result * prime + s.hashCode(); } // result is the hashcode. 我没有理由不连接string并计算连接的哈希码。
比方说，我想计算一个内存块的MD5校验和，我不会把这个块分成更小的块，然后为它们计算单独的MD5校验和，然后用一些特殊的方法将它们组合起来。
(String1, String2)产生相同的(String2, String1)哈希码的唯一不便之处。 如果这不是一个问题（例如，因为你有一个固定的订单）没关系。
“把所有的string连在一起然后得到哈希码 ”似乎对我来说更加自然和安全。
更新 ：正如一个评论指出的那样，这有一个缺点，即列表（“x”，“yz”）和（“xy”，“z”）会给出相同的散列。 为了避免这种情况，可以使用不能出现在string内的string分隔符来joinstring。
如果string很大，您可能更喜欢散列每个字符，捕获这些散列码并重新散列结果。 更多的CPU，更less的内存。
另一种方式，在我的脑海里，链式xors旋转散列基于索引：
int shift = 0; int result = 1; for(String s : strings) { result ^= (s.hashCode() << shift) | (s.hashCode() >> (32-shift)) & (1 << shift - 1); shift = (shift+1)%32; }
编辑：阅读有效的java中给出的解释，我认为geoff的代码会更有效率。
基于SQL的解决scheme可以基于校验和和checksum_agg函数。 如果我正确地遵循，你有这样的事情：
MyTable MyTableId HashCode MyChildTable MyTableId (foreign key into MyTable) String
与MyChildTable中存储的给定项目（MyTableId）的各种string。 要计算和存储反映这些（永远不会改变）string的校验和，应该这样工作：
UPDATE MyTable set HashCode = checksum_agg(checksum(string)) from MyTable mt inner join MyChildTable ct on ct.MyTableId = mt.MyTableId where mt.MyTableId = @OnlyForThisOne
我相信这是顺序无关的，所以string“快速棕色”会产生与“棕色快速”相同的校验和。
我希望这是不必要的，但是由于你没有提到任何听起来像只用哈希码进行第一次检查然后再validationstring实际上是平等的东西，我觉得有必要警告你：
哈希码相等！=值相等
将有大量的string组合产生相同的散列码，但不总是相等的。
所以我明白，你实际上有一些你需要用哈希代码来标识的string，而且你需要识别的那组string永远不会改变？
如果是这样的话，只要您使用的scheme为不同的string/string组合提供了唯一的数字，那么这并不重要。 我会开始只是串联string和计算String.hashCode（），看看你是否最终以唯一的数字。 如果你不这样做，那么你可以试试：
- 而不是拼接string，连接组件string的哈希码，并尝试不同的乘法器（例如，如果要识别双string序列的组合，请尝试HC1 + 17 * HC2，如果不给出唯一的数字，请尝试HC1 + 31 * HC2，然后尝试19，然后尝试37等 – 基本上任何小奇怪的数字将会很好）。
- 如果你没有以这种方式得到唯一的数字 – 或者你需要处理扩展的可能性 – 那么考虑一个更强大的哈希码。 一个64位的散列码是一个很好的妥协之间的比较和散列的可能性是独特的。
一个64位散列码的可能scheme如下：
- 使用相当强大的scheme生成256个64位随机数组（尽pipeXORShiftscheme可以正常工作，但可以使用SecureRandom）
- select“m”，另一个“随机”的64位奇数，其大小设置的一半或多或less有一半
- 生成一个哈希码，遍历每个字节值，b，构成string，并从你的随机数组中获得第b个数字; 然后XOR或用当前散列值加上乘以“m”
所以基于Numerical Recipes中build议的值的实现将是：
private static final long[] byteTable; private static final long HSTART = 0xBB40E64DA205B064L; private static final long HMULT = 7664345821815920749L; static { byteTable = new long[256]; long h = 0x544B2FBACAAF1684L; for (int i = 0; i < 256; i++) { for (int j = 0; j < 31; j++) { h = (h >>> 7) ^ h; h = (h << 11) ^ h; h = (h >>> 10) ^ h; } byteTable[i] = h; } }
以上是初始化我们的随机数组。 我们使用一个XORShift生成器，但是我们真的可以使用任何相当高质量的随机数生成器（创build一个具有特定种子的SecureRandom（），然后调用nextLong（）就可以了）。 然后，生成一个哈希码：
public static long hashCode(String cs) { if (cs == null) return 1L; long h = HSTART; final long hmult = HMULT; final long[] ht = byteTable; for (int i = cs.length()-1; i >= 0; i--) { char ch = cs.charAt(i); h = (h * hmult) ^ ht[ch & 0xff]; h = (h * hmult) ^ ht[(ch >>> 8) & 0xff]; } return h; }
需要考虑的一个指导是，给定一个n位的散列码，平均来说，在碰撞之前，你将不得不生成2 ^（n / 2）个string的散列值。 换句话说，用64位散列，你会期望在大约40亿个string之后发生冲突（所以如果你要处理的是几百万个string，碰撞的几率是可以忽略的）。
另一个select是MD5，这是一个非常强大的散列（实际上是安全的），但它是一个128位散列，所以你有处理128位值的轻微缺点。 我会说MD5是为了这些目的的矫枉过正 – 正如我所说，用64位散列，你可以相当安全地处理几百万string的顺序。
（对不起，我应该澄清一下 – MD5被devise成一个安全的散列，就是因为它被认为是不安全的。一个“安全”的散列是给定一个特定的散列，不可能有意识地构buildinput，在某些情况下 – 但不是我所理解的 – 你可能需要这个属性，另一方面，如果你正在处理用户input数据的string，恶意用户可能会故意试图混淆你的系统，你也可能会在以下我写的过去中感到愤怒：
- 指导哈希码
- Java中的安全散列码 （包括一些性能测量）
使用GetHashCode()并不适合组合多个值。 问题是，对于string，哈希码只是一个校验和。 对于相似的数值，这会留下很小的熵。 例如，为（“abc”，“bbc”）添加哈希码将与（“abd”，“abc”）相同，导致冲突。
在需要绝对确定的情况下，可以使用真正的散列algorithm，如SHA1，MD5等。唯一的问题是它们是块函数，难以快速比较哈希值是否相等。 相反，尝试一个CRC或FNV1散列。 FNV1 32位超级简单：
public static class Fnv1 { public const uint OffsetBasis32 = 2166136261; public const uint FnvPrime32 = 16777619; public static int ComputeHash32(byte[] buffer) { uint hash = OffsetBasis32; foreach (byte b in buffer) { hash *= FnvPrime32; hash ^= b; } return (int)hash; } }
您可以使用以下方法来聚合哈希代码： http : //docs.oracle.com/javase/7/docs/api/java/util/Objects.html#hash（java.lang.Object …）
让我们解决你的根本问题。
不要使用哈希码。 只需为每个string添加一个整数主键
