How can hashmap guarantee same `index` for key used again?

Question

The way a hashmap computes the index is the following code -

static int indexFor(int h, int length) {
    return h & (length-1);
}

Now assuming a key is used for a second time (lets say another put) and at that time the length has changed. In such a case how does indexFor return same index when length was 16 vs when length was 64 ?

Thanks, but many a times such duplicate cannot be googled up. — JavaDeveloper, Oct 13 '13 at 19:53
@Jay to me it looks like a different question about the same code - although YMMV. — Alan Stokes, Oct 13 '13 at 20:21

score 2 · Accepted Answer · answered Oct 13 '13 at 19:52

When the length of the hash table changes the whole table has to be rebuilt to make sure every entry is at the place where it should now be. (This is called rehashing.)

This is quite an expensive operation, so the code attempts to minimise how often it happens. That's why it's useful to tell the HashMap how many elements to expect when first constructing it - it allows it to avoid doing any rehashing while filling the table.

score 0 · Answer 2 · answered Oct 13 '13 at 19:55

The length is not necessarily the number of items in the hash, but the maximum capacity of the hash.

Usually it's a prime number which is increased whenever there's no space to add additional item. In that case the capacity is increased to the next step and rehashing is performed.

How can hashmap guarantee same `index` for key used again?

2 Answers2