Geek asks and answers

How get (key) works even after the hash table has grown in size!

If the Hashtable has a size of 8 initially, and we gain a load factor, and it doubles. How to get still the opportunity to get the original values ​​... so let's say that we have a hash function (8), it will be converted to 12345 as a hash value, which we change to 8, and get the index 7 ... now, when the hash table the size increases to 16 ... for the key (8) we get 12345 .. if we change it to 16, we get a different answer! So how I still retrieve the source key (8)

+3
source share
4 answers

This is not specific to Java - when the hash table grows (in most implementations that I know of), it should re-evaluate the keys of all hashed objects and put them in its new, correct bucket based on the number of buckets now available.

That is why resizing a hash table is usually considered an “expensive” operation (compared to many others) - because it must visit all stored items inside it.

+4
source

The hash value used to find the value comes from the key object itself, and not from the container.

What objects use as keys on the map must be unchanged. If it hashCode()changes, you cannot find your key or value again.

+3
source

, rehash , .

+1

HashMap transfer(), resize().

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

HashTable , ( ). , . - ( , hash Entry, ), indexFor() :

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

- .

, get() indexFor(), , .

+1
source

More articles:


All Articles