String to unique integer hashing

This is not possible with the constraints you have given, unless you impose a maximum length.

Assume that k("a") and k("b") are the codes of these two strings.

With your constraints, you are looking for a unique integer number that falls inbetween these two values, but k("a") < k("a....a") < k("b"). As there is an infinite number of strings of style "a....a" (and "akjhdsfkjhs") that would need to fit inbetween the two codes, such an order preserving general, unique, fixed-length code cannot exist for strings of arbitrary length. Because you would need as many integers as strings, and since strings are not bounded by length this cannot work.

Drop either general (so don't allow inserting new strings), unique (allow collissions - e.g. use the first four letters as code!), the unbounded length (to e.g. 3 characters) or the order-preserving property.

For simplicity, I'll assume a to z are the only characters allowed in words.

Let's assign numbers up to length 2 strings:

String Value a 0 aa 1 ab 2 ... az 26 b 27 ba 28 bb 29 ... bz 53 c 54 ... 

Now, by just looking at that, you should be able to appreciate that, to determine the offset of any given shorter-length string, you'd need the maximum length allowed. Let's assume we know this number.

For algorithmic simplicity, we would prefer to start at 27: (feel free to try to figure it out for starting from 0, you'll need some special cases)

String Value a 27 aa 28 ab 29 ... 

So, essentially, the left-most character contributes a value 27*(1-26) (for a-z) and the next character to the right, if one exists, contributes 1-26 (for a-z) to the value for a string.

Now this can be generalized to say that the left-most number would contribute (1-26)*27^(len-1), the next (1-26)*27^(len-2), and so on, until (1-26)*27^0.

Which leads me to some Java code:

long result = 0; for (int i = 0; i < s.length(); i++) result += pow(27, MAX_LENGTH - i - 1)*(1 + s.charAt(i) - 'a'); 

Test output:

a = 150094635296999121 aa = 155653695863554644 aaa = 155859586995649293 aaaa = 155867212593134280 aaaaa = 155867495022670761 abacus = 161447654121636735 abbreviation = 161763445236432690 account = 167509959568845165 accuracy = 167554723653128367 announcement = 230924421746611173 z = 3902460517721977146 

Online demo.

Yes, those are some reasonably big numbers for just up to length 13 strings, but, without sequentially assigning numbers to words in an actual dictionary, you can't do any better (except that you can start at 0, which is, relatively speaking, a small difference), since there are that many possibilities of letter sequences.

For uniqueness, start with assigning primes to the letters: A -> 2, B -> 3, C -> 5, D -> 7 etc.

To calculate the "key" of a given letter in a word, raise the prime to the power of the position index in the word. To get the "key" of the whole word, multiply all the letter keys together.

For example the word CAB:

C -> 5 ^ 1 = 5 A -> 2 ^ 2 = 4 B -> 3 ^ 3 = 81 CAB -> 5 * 4 * 81 = 1620. 

No other word will ever give you 1620 as a key.

Note: you don't have to start with A -> 2 or assign primes to the characters of the alphabet in order as long as you keep track of the mapping. Also bear in mind that the results of this will get large very quickly.

However, bear in mind the other comments about security - this is not a particularly secure algorithm.

If you don't have any limit on the number of bytes that these integers can occupy, then the underlying (e.g. Ascii) byte codes for each character will give you an integer representation. Equivalently, assign 0=A, 1=B up to Z=25 and then the word itself is the integer in base 26.

Assign a unique prime value to each alphabet in increasing order(order not necessary).

Please Note : As multiplication of prime numbers is a unique result which can only be multiplied by these numbers, it will give you unique values for each word.

Algorithm :

int hash = 0; forEach (int i = 0 ; i < word.length ; i++) { hash *= (prime[c[i]] ** (length - i)); } 

prime - An array to store prime values corresponding to each

powered to (length - 1) to give value to the place at which this character occurs to maintain a dictionary order.

This algorithm will give sufficiently large values that will overrun your array.

Also : words will smaller lengths may give lower values than some words with larger length and it may affect your dictionary order but I'm not sure why do you want a dictionary order as the uniqueness will be maintained here.

Yes, but mostly no.

Yes as in Stochastically's answer. By setting up a base 26 (or base 128 for all ASCII), you could theoretically hash each string uniquely.

On the other hand, this is impractical, not only would numbers get too big for most languages, but also this would likely be an incredibly consuming process. Furthermore, if strings are allowed to be infinite, then a form of Cantor's diagonal argument can be applied also "breaking" this algorithm. It is impossible to create a one-to-one mapping of a set with cardinality aleph-one (strings) to a set of cardinality aleph-null (ints).

You can do this:

SEPARETOR = '000' string_to_hash = "some_string" hashed_result = int(SEPARETOR.join(list(str(ord(character)) for character in string_to_hash))) 

Enjoy!

The function in general form for a string s of length n is:

hashCode(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

Where ^ denotes exponentiation. As Java uses 32-bit integers to hold the hash value, all values should be kept as such.

if you want to hash string to small integer, you can use the following C# code:

int StringToIntegerHash(string str) { int hash = 0; str = GetTicketHash(str); for(int i=0; i<str.Length;i++) { hash +=(int) ((int)str[i]) * Math.Pow(2, str.Length - i); } return hash; } string GetTicketHash(string str) { const string chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; byte[] bytes = Encoding.UTF8.GetBytes(str); SHA256Managed hashstring = new SHA256Managed(); byte[] hash = hashstring.ComputeHash(bytes); char[] hash2 = new char[16]; // Note that here we are wasting bits of hash! // But it isn't really important, because hash.Length == 32 for (int i = 0; i < hash2.Length; i++) { hash2[i] = chars[hash[i] % chars.Length]; } return new string(hash2); } 

I would just convert the string into a byte-array and then convert that into a number. Here a PS-sample code:

$string = "test" # convert string into byte-array: $enc = [System.Text.Encoding]::UTF8 $arr = $enc.GetBytes($string) # convert byte-array into number: $hexbin = [System.Runtime.Remoting.Metadata.W3cXsd2001.SoapHexBinary]::new() $hexbin.Value = $arr $result = $hexbin.ToString() write-host $result 

Of course you could go with any other/shorter conversion like base-26 etc, but that makes the coding way more complex and slower.

FYI - in case you want to converts strings into numbers for faster comparison in a DB, then keep in mind that most DBs are already hashing strings internally. No need for any other finetuning.