Java: Need help on hashing function overflow

Question

I am working on an assignment were I have to hash 10,000 numbers into a hash table of load size .1, .2 .3 .... up to .9. My problem is that my hashing function is giving me some overflow or something of the sort. If am doing a hash for a table with load factor of .5 like 36077(mod)20,000 it gives me 16070 as the key. This only happens on numbers that are above the load factor. This is the code for my hashing function.

    public int linearHash(int in){
    int hashKey = in%hashTableArray.length;
    while(this.hashTableArray[hashKey] != 0){
        hashKey += 1;
    }
    return hashKey;
}

Thank you.

As @Reimeus said below, and also for Open Addressing hashKey should wrap around to zero if it reaches the end of the array. Watch you don't go into an infinite loop if the array is full. — James
– James, Commented Nov 2, 2012 at 21:25

Reimeus · Accepted Answer · 2012-11-02 21:23:42Z

0

You are not checking that you are exceeding the index bounds of the hashTableArray in your while loop. You could do:

while (hashKey < hashTableArray.length && this.hashTableArray[hashKey] != 0){

answered Nov 2, 2012 at 21:23

Reimeus

160k16 gold badges225 silver badges282 bronze badges

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

Comments

Kent · Accepted Answer · 2012-11-02 22:05:33Z

Reimeus pointed out the OutOfBound problem and gave a solution. I just want to add something about your way to handle collision.

Your function looks like open addressing approach. instead of hashKey += 1; perhaps you could consider to increment the in

 public int linearHash(int in){   
    int hashKey = in%hashTableArray.length;
    while(this.hashTableArray[hashKey] != 0){
        in ++;
        hashKey = in%hashTableArray.length;
    }
    return hashKey;
}

the example codes above didn't check for hashtable overflow. the auto-increment should not happen more than hashTableArray.length times. otherwise your program falls into dead loop

and please note that decide if a slot is free by checking hashTableArray[hashKey] != 0 is not safe. for example, what about there are number 0 and 20000 in your elements.

Collectives™ on Stack Overflow

Java: Need help on hashing function overflow

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related