В java Hashtable использует внутреннюю технику разрешения?

Question

После прочтения постов я запутался в java Hashtable внутренне использует отдельную цепочку или связанный список или открытую близкую адресацию для обработки коллизий хеш-таблицы.

Может кто-нибудь сказать мне, какие хеш-таблицы используются внутренне?

Answer 1

Если вы посмотрите на источник (есть некоторые онлайн-источники, или в каталоге lib JDK есть src.jar или src.zip - я думаю, что с JDK 11+ это только в OpenJDK, а не в Oracle), вы можете видеть, что Hashtable реализован в виде массива блоков, и каждый сегмент представляет собой односвязный список.

Данные хранятся здесь:

/**
 * The hash table data.
 */
private transient Entry<?,?>[] table;

Тогда еслимы смотрим на get:

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

Мы можем видеть, что hashCode ключа используется для выбора сегмента, а затем это линейный поиск внутри этого сегмента длязапись.

---

Обратите внимание, что Hashtable является в значительной степени устаревшим классом, замененным HashMap в Java 1.2.OpenJDK HashMap начинает работать в основном так же, как Hashtable, но если корзины становятся слишком большими, он переключается на использование корзин, содержащих TreeMap -подобные структуры (они быстрее ищут вещи, когда корзинаПереполненный).