Почему HashTable хранит хеш-значение ключа в таблице в java

Я просматривал Java-реализацию метода put для хеш-таблицы и наткнулся на это:

// Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

Хотя я понимаю, что для проверки коллизий требуется ключ, почему Java хранит хеш-значение ключа, а также проверяет его?


java hashtable hash-collision
person akanksha1105    schedule 18.10.2012    source источник

Ответы (2)


arrow_upward
8
arrow_downward

Поскольку одна и та же корзина (tab) может содержать элементы, имеющие разные хеши из-за операции % tab.length. Проверка хеша в первую очередь, вероятно, является некоторой оптимизацией производительности, чтобы избежать вызова equals(), если хеши разные.

Чтобы проиллюстрировать это на примере: скажем, у вас есть два сложных объекта с дорогостоящим equals() методом. Один объект имеет хэш, равный 1, а другой объект - 32. Если вы поместите оба объекта в хеш-таблицу, содержащую 31 сегмент, они окажутся в одном сегменте (tab). При добавлении второго (другого объекта) убедитесь, что его еще нет в таблице. Вы можете использовать equals() сразу, но это может быть медленнее. Вместо этого вы сначала сравниваете хеши, избегая дорогостоящих equals(), если в этом нет необходимости. В этом примере хеши разные (несмотря на то, что они находятся в одном ведре), поэтому equals() не требуется.

person Tomasz Nurkiewicz    schedule 18.10.2012

arrow_upward
1
arrow_downward

Это ускоряет доступ, поскольку не нужно пересчитывать хеш-значение для каждого доступа. Это важно не только для явного поиска (когда хеш проверяется перед выполнением equals), но и для повторного хеширования.

person Hot Licks    schedule 18.10.2012