3

I need a 64-bit hash for strings, and the default .GetHashCode() returns only a 32-bit int. I could generate a MD5/SHA1 hash, and use only the first 64bits. But because those algorithms are cryptographically secure, they are much more demanding on the CPU.

Could it be so simple as to just calling .GetHashCode() a second time, on the reverse of the input string? And casting the two 32bit int into a 64-bit long? Would it have the same spread and collision resistance as a 'real' 64bit hash like CRC64?

Improve this question
7
  • See this answer stackoverflow.com/questions/7954602/… for a 64-bit hash code implementation. Commented Nov 9, 2011 at 0:11
  • Why would this be "not constructive?" There are good reasons for wanting a hash code that you can guarantee doesn't change. And good reasons for wanting a 64-bit hash code. Commented Nov 9, 2011 at 0:13
  • Why do you think you need a 64-bit hash? Commented Nov 9, 2011 at 0:22
  • @DourHighArch Because 32-bit will give me too many collisions, and 128-bit is overkill. Commented Nov 9, 2011 at 0:27
  • 1
    I would definitely not recommend using a hash code for a record key. As Chris Haas pointed out in his answer, a hash code doesn't create a unique value. 64 bits means that the likelihood of getting a collision will be small, but there will be collisions. As I said in my linked answer above, "let the database do what it's good at." Using a hash code to "optimize" your database access is almost certainly a bad decision. Commented Nov 9, 2011 at 0:43

3 Answers 3

Reset to default
3

You are about to make a very big mistake. A 64-bit hash isn't nearly good enough to guarantee uniqueness. That requires at least 128 bits. A guid is a common choice.

Generating unique 32-bit or 64-bit numbers isn't that hard, you simple use the next one. The rub is that you need to know the previous one. Dbase engines never have a problem with that, their point of being is remembering stuff.

Use an auto-increment column.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

The problem is that I need to look up strings quickly. If I create an indexed TEXT column in SQLite, all strings are stored twice (because of the b-tree index), and additional inserts become very slow after a million rows (because of b-tree page splitting, etc). I agree with you that it's best to keep the PRIMARY KEY a normal integer, but what's wrong with adding a second column containing the hash, and indexing that instead of the TEXT column?
I can't see why you think that improves anything. Dbase engines already have good ways to generate a hash from a string. You really need to distinguish the task of looking up records (easy and fast) with inserting rows in a table with a million records. Which tends to highlight the LITE in SqlLite.
Most database engines may have ways to generate a hash from a string, but SQLite has none (afaik)? So it's always creating an index on large (text) values, when it just can index a small (integer) value.
This is getting a bit random. Measure to convince yourself.
No, that only told you that it is slow. You already knew that. You have to compare. Measure if it is faster when you add an extra column and write more data.
|
2

Just to get this out of the way, you know that GetHashCode() doesn't generate anything unique, right? Two completely different strings can return the same hash code. The algorithm is only intended for creating even distribution of objects in hashtable.

From the horse's mouth:

The default implementation of the GetHashCode method does not guarantee unique return values for different objects.

Additionally, the rules for what happens when you call GetHashCode() can and will change over time. See the section titled "Rule: Consumers of GetHashCode cannot rely upon it being stable over time or across appdomains" here, specifically:

This has bitten people in the past. 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.

To see someone's collision detection work check this out.

Improve this answer

Comments

0

Is there a particular reason you chose 64 bit? MD5 is more for checking that the content hasn't changed on accident, and SHA is more for making sure the content wasn't changed on purpose. I'd definitely use at LEAST SHA1.

Improve this answer

4 Comments

Because it's going to serve as a row id in a sqlite database, and those are max 64bits. Also the strings I will be hashing are 50 bytes on average, making even a 8 byte hash almost overkill.
Are there security concerns around the 50 bytes? Are you going to check after the hash is created that the bytes haven't changed or send the hash over the wire securely for a remote location to verify the bytes?
No, none of that. It's just used so that sqlite can index shorter values.
I would use the link Jim Mischel recommended for your purpse.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.