CODEWITHSUNDEEP
c#
jgauffin
jgauffin

Reputation: 101140

Calculate a checksum for a string

I got a string of an arbitrary length (lets say 5 to 2000 characters) which I would like to calculate a checksum for.

Requirements

Which algorithm should I use?

Update:

Update2

Let's say that I got the following string "Welcome to this website. Navigate using the flashy but useless menu above".

The string is used in a view in a similar way to gettext in linux. i.e. the user just writes (in a razor view)

@T("Welcome to this website. Navigate using the flashy but useless menu above")

Now I need a way to identity that string so that I can fetch it from a data source (there are several implementations of the data source). Having to use the entire string as a key seems a bit inefficient and I'm therefore looking for a way to generate a key out of it.

Upvotes: 30

Views: 68791

Answers (5)

David Heffernan
David Heffernan

Reputation: 612844

Note: This is an answer to the original question.

Assuming you want the checksum to be stored in a variable of fixed size (i.e. an integer), you cannot satisfy your second constraint.

The checksum must be unique (no collisions)

You cannot avoid collisions because there will be more distinct strings than there are possible checksum values.

Upvotes: 4

Mitchell E.
Mitchell E.

Reputation: 11

To guarantee uniqueness, for a almost infinite size strings, treat the variable length string as a set of concatenated substrings each having "x characters in length". Your hash function needs only to determine uniqueness for a maximum substring length and then generate a series of checksum numbers generating values. Think of it as the equivalent network IP address with a set of checksum numbers.

Your issue with collisions is the assumption that a collision forces a slower search method to resolve each collision. If their are a insignificant number of possible collisions compared to the number of hash objects, then as a whole the extra overhead becomes NIL. A collision is due to the sizing of a table smaller than the maximum number of objects. This doesn't have to be the case because the table may have "holes" and each object within the table may have a reference count of objects at that collision. Only if this count is greater than 1, then a collision occurs or multiple instances of the same substring.

Upvotes: 1

cocogorilla
cocogorilla

Reputation: 1865

I realize this post is practically ancient, but I stumbled upon it and have run into an almost identical issue in the past. We had an nvarchar(8000) field that we needed to lookup against.

Our solution was to create a persisted computed column using CHECKSUM of the nasty lookup field. We had an auto-incrementing ID field and keyed on (checksum, id)

When reading from the table, we wrote a proc that took the lookup text, computed the checksum and then took where the checksums were equal and the text was equal.

You could easily perform the checksum portions at the application level based on the answer above and store them manually instead of using our DB-centric solution. But the point is to get a reasonably sized key for indexing so that your text comparison runs against a bucket of collisions instead of the entire dataset.

Good luck!

Upvotes: 2

L.B
L.B

Reputation: 116108

You can use cryptographic Hash functions for this. Most of them are available in .Net

For example:

var sha1 = System.Security.Cryptography.SHA1.Create();
byte[] buf = System.Text.Encoding.UTF8.GetBytes("test");
byte[] hash= sha1.ComputeHash(buf, 0, buf.Length);
//var hashstr  = Convert.ToBase64String(hash);
var hashstr = System.BitConverter.ToString(hash).Replace("-", "");

Upvotes: 9

Guffa
Guffa

Reputation: 700212

That's not possible.

If you can't store previous values, it's not possible to create a unique checksum that is smaller than the information in the string.

Update:

The term "reasonably unique" doesn't make sense, either it's unique or it's not.

To get a reasonably low risk of hash collisions, you can use a resonably large hash code.

The MD5 algorithm for example produces a 16 byte hash code. Convert the string to a byte array using some encoding that preserves all characters, for example UTF-8, calculate the hash code using the MD5 class, then convert the hash code byte array into a string using the BitConverter class:

string theString = "asdf";

string hash;
using (System.Security.Cryptography.MD5 md5 = System.Security.Cryptography.MD5.Create()) {
  hash = BitConverter.ToString(
    md5.ComputeHash(Encoding.UTF8.GetBytes(theString))
  ).Replace("-", String.Empty);
}

Console.WriteLine(hash);

Output:

912EC803B2CE49E4A541068D495AB570

Upvotes: 36

Related Questions