How to convert a string to a key for hash table

2k views Asked by At

I need to convert a string (max. length = 20, consisting of random lower alphabetical characters and/or numbers) to a key for a hash table that holds slots for a max of 100.000 keys. What I tried is to convert each of the chars within the string to a number between 0 and 36 (since 36 posibilities for each char) and calculate the number for the string, counting as a positional numeral system with base 36:

long val = 0;
long v;
long pow = name.Length-1;
foreach (char c in name) {
    if (char.IsNumber(c))
        v = (long)c;
    else
        v = char.ToUpper(c) - 54; 
    val += v * (long)Math.Pow((double)36, (double)pow);
    Console.WriteLine(v+","+pow+","+val);
    pow--;
}

Then I tried using tolong(somestring) % 100000 to map the strings to keys between 0 and 9999. However the results of the tolong function amount to huge numbers which long can't even handle.

Could anyone help me out on how I could do this conversion right?

2

There are 2 answers

0
Stefan Steinegger On

I've implemented something like this (because the HashCode is not usable outside of the machine).

I started with turning the string into a byte array:

        byte[] bytes = new byte[value.Length * sizeof(char)];
        Buffer.BlockCopy(value.ToCharArray(), 0, bytes, 0, bytes.Length);

Then looping it and put it into an integer:

        foreach (var b in bytes)
        {
            hash ^= RotateLeft(b, position);
            position += 7;
        }

RotateLeft does bit shifting. These are details which may be different.

0
Seth On

To stick with your algorithm you don't need to calculate the whole number and do a mod at the end. You can change val to a BigInteger and mod as you go.

BigInteger val = 0;
long v;
long pow = name.Length-1;
foreach (char c in name) {
    if (char.IsNumber(c))
        v = (long)c;
    else
    {
        v = char.ToUpper(c) - 54; 
        val += v * (long)Math.Pow((double)36, (double)pow);
    }
    Console.WriteLine(v+","+pow+","+val);
    pow--;

    val = val % 100000;
}