How do I calculate a good hash code for a list of strings?_问答_开发者

Background:

I have a short list of strings.
The number of strings is not always the same, but are nearly always of the order of a “handful”
In our database will store these strings in a 2nd normalised table
These strings are never changed once they are written to the database.

We wish to be able to match on these strings quickly in a query without the performance hit of doing lots of joins.

So I am thinking of storing a hash code of all these strings in the main table and including it in our index, so the joins are only processed by the database when the hash code matches.

So how do I get a good hashcode? I could:

Xor the hash codes of all the string together
Xor with multiply the result after each string (say by 31)
Cat all the string together then get the hashcode
Some other way

So what do people think?

In the end I just concatenate the strings and compute the hashcode for the concatenation, as it is simple and worked well enough.

(If you ca开发者_运维技巧re we are using .NET and SqlServer)

Bug!, Bug!

Quoting from Guidelines and rules for GetHashCode by Eric Lippert

The documentation for System.String.GetHashCode notes specifically that two identical strings can have different hash codes in different versions of the CLR, and in fact they do. Don't store string hashes in databases and expect them to be the same forever, because they won't be.

So String.GetHashcode() should not be used for this.

Standard java practise, is to simply write

final int prime = 31;
int result = 1;
for( String s : strings )
{
    result = result * prime + s.hashCode();
}
// result is the hashcode.

I see no reason not to concatenate the strings and compute the hashcode for the concatenation.

As an analogy, say that I wanted to compute a MD5 checksum for a memory block, I wouldn't split the block up into smaller pieces and compute individual MD5 checksums for them and then combine them with some ad hoc method.

Your first option has the only inconvenience of (String1, String2) producing the same hashcode of (String2, String1). If that's not a problem (eg. because you have a fix order) it's fine.

"Cat all the string together then get the hashcode" seems the more natural and secure to me.

Update: As a comment points out, this has the drawback that the list ("x", "yz") and ("xy","z") would give the same hash. To avoid this, you could join the strings with a string delimiter that cannot appear inside the strings.

If the strings are big, you might prefer to hash each one, cat the hashcodes and rehash the result. More CPU, less memory.

Another way that pops in my head, chain xors with rotated hashes based on index:

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;
}

edit: reading the explanation given in effective java, I think geoff's code would be much more efficient.

A SQL-based solution could be based on the checksum and checksum_agg functions. If I'm following it right, you have something like:

MyTable
  MyTableId
  HashCode

MyChildTable
  MyTableId  (foreign key into MyTable)
  String

with the various strings for a given item (MyTableId) stored in MyChildTable. To calculate and store a checksum reflecting these (never-to-be-changed) strings, something like this should work:

UPDATE MyTable
 set HashCode = checksum_agg(checksum(string))
 from MyTable mt
  inner join MyChildTable ct
   on ct.MyTableId = mt.MyTableId
 where mt.MyTableId = @OnlyForThisOne

I believe this is order-independant, so strings "The quick brown" would produce the same checksum as "brown The quick".

I hope this is unnecessary, but since you don't mention anything which sounds like you're only using the hashcodes for a first check and then later verifying that the strings are actually equal, I feel the need to warn you:

Hashcode equality != value equality

There will be lots of sets of strings which yield the identical hashcode, but won't always be equal.

So I understand, you effectively have some set of strings that you need to identify by hash code, and that set of strings that you need to identify among will never change?

If that's the case, it doesn't particularly matter, so long as the scheme you use gives you unique numbers for the different strings/combinations of strings. I would start by just concatenating the strings and calculating the String.hashCode() and seeing if you end up with unique numbers. If you don't, then you could try:

instead of concatenating strings, concatenate hash codes of the component strings, and try different multipliers (e.g. if you want to identify combiantions of two-string sequences, try HC1 + 17 * HC2, if that doesn't give unique numbers, try HC1 + 31 * HC2, then try 19, then try 37 etc -- essentially any small-ish odd number will do fine).
if you don't get unique numbers in this way-- or if you need to cope with the set of possibilities expanding-- then consider a stronger hash code. A 64-bit hash code is a good compromise between ease of comparison and likelihood of hashes being unique.

A possible scheme for a 64-bit hash code is as follows:

generate an array of 256 64-bit random numbers using a fairly strong scheme (you could use SecureRandom, though the XORShift scheme would work fine)
pick "m", another "random" 64-bit, odd number with more or less half of its bits set
to generate a hash code, go through each byte value, b, making up the string, and take the bth number from your array of random numbers; then XOR or add that with the current hash value, multiplied by "m"

So an implementation based on values suggested in Numerical Recipes would be:

  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;
    }
  }

The above is initialising our array of random numbers. We use an XORShift generator, but we could really use any fairly good-quality random number generator (creating a SecureRandom() with a particular seed then calling nextLong() would be fine). Then, to generate a hash code:

  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;
  }

A guide to consider is that given a hash code of n bits, on average you'd expect to have to generate hashes of in the order of 2^(n/2) strings before you get a collision. Or put another way, with a 64-bit hash, you'd expect a collision after around 4 billion strings (so if you're dealing with up to, say, a couple of million strings, the chances of a collision are pretty negligible).

Another option would be MD5, which is a very strong hash (practically secure), but it is a 128-bit hash, so you have the slight disadvantage of having to deal with 128-bit values. I would say MD5 is overkill for these purposes-- as I say, with a 64-bit hash, you can deal fairly safely with in the order of a few million strings.

(Sorry, I should clarify -- MD5 was designed as a secure hash, it's just that it's since found not to be secure. A "secure" hash is one where given a particular hash it's not feasible to deliberately construct input that would lead to that hash. In some circumstances-- but not as I understand in yours-- you would need this property. You might need it, on the other hand, if the strings you're dealing with a user-input data-- i.e. a malicious user could deliberately try to confuse your system. You might also be interetsed in the following I've written in the past:

guide to hash codes
secure hash codes in Java (includes some performance measurements)

Using the GetHashCode() is not ideal for combining multiple values. The problem is that for strings, the hashcode is just a checksum. This leaves little entropy for similar values. e.g. adding hashcodes for ("abc", "bbc") will be the same as ("abd", "abc"), causing a collision.

In cases where you need to be absolutely sure, you'd use a real hash algorithm, like SHA1, MD5, etc. The only problem is that they are block functions, which is difficult to quickly compare hashes for equality. Instead, try a CRC or FNV1 hash. FNV1 32-bit is super simple:

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;
    }
}

You can use the following method to aggregate hash codes: http://docs.oracle.com/javase/7/docs/api/java/util/Objects.html#hash(java.lang.Object...)

If you happen to use Java, you can create an array of strings (or convert a collection to an array), and then use Arrays.hashCode() as documented here.

Let's solve your root problem.

Don't use a hashcode. Just add a integer primary key for each String