0

I have this, i would like to make it more efficient and if you need the whole hashset data structure i have created i can add it but im overall looking for something like this that takes any number of strings and stores them in my custom implementation of a hashset:

    private int hash(String key)
{
    int prime = 31;
    int hash = 0;

    for(int i = 0; i < key.length(); i++)
    {
        hash *= prime;
        hash ^= key.charAt(i);
    }

    if (hash < 0)
        hash *= -1;

    return hash % array.length;
}
5
  • If you want to generate hash code for an array of string well we have built in function like Arrays.hashCode(Object[]): Arrays.hashCode(strArray). Simple and efficient
    – Sage
    Dec 10, 2013 at 17:54
  • Sorry i didnt say, no use of the java api, i have to add word by word Dec 10, 2013 at 17:55
  • Could please make it a little bit more clear. You are passing a String to hash function but the returning statement has array.length: where did this array come from ?
    – Sage
    Dec 10, 2013 at 17:56
  • its the hashset array, it has a set amount, think of that as a number Dec 10, 2013 at 17:58
  • Heres the Answer: public int FNV(String word){ int hash=0; for (int i=0; i<word.length(); i++) { hash *= 31; hash ^=+word.charAt(i); } if(hash<0){ hash *=-1; } int endResult = hash % HashTable.length; return endResult; } Dec 10, 2013 at 19:09

1 Answer 1

0

A few observations:

  • It's generally accepted these days that 33 is a better choice of prime than 31, because it leads to fewer collisions in most non-English languages (English has about the same small number of collisions either way).
  • Converting your string to a character array and accessing the elements that way rather than calling charAt() multiple times is likely to be faster
  • The following code is inefficient:

    if (hash < 0)
         hash *= -1;
    

    This code is better, because (1) it doesn't use a processor multiply instruction, which is resource intensive, and (2) it doesn't produce branch mispredictions periodically:

    hash &= ~0x80000000;
    
1
  • Bullet point #1 above (prime 31 vs 33) is fascinating! Do you have any sources that I can read to learn more?
    – kevinarpe
    Oct 20, 2022 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.