Как HashTables справляется с коллизиями?

Question

В своих классах степеней я слышал, что HashTable поместит новую запись в «следующий доступный» сегмент, если новая запись ключа столкнется с другой.

Как бы HashTable по-прежнему возвращал правильное значение, если это столкновение происходит при вызове одного с помощью ключа столкновения?

Я предполагаю, что Keys имеют тип String, а hashCode() возвращает значение по умолчанию, сгенерированное, скажем, Java.

Если я реализую свою собственную функцию хеширования и использую ее как часть справочной таблицы (т. Е. HashMap или Dictionary), какие существуют стратегии для устранения коллизий?

Я даже видел заметки, касающиеся простых чисел! Информация не очень понятна из поиска Google.

Answer 1

Хеш-таблицы обрабатывают коллизии одним из двух способов.

Вариант 1: Наличие в каждом сегменте связанного списка элементов, которые хэшируются в этом сегменте. Вот почему плохая хеш-функция может сделать поиск в хеш-таблицах очень медленным.

Вариант 2: Если все записи хеш-таблицы заполнены, то хеш-таблица может увеличить количество имеющихся в ней сегментов, а затем перераспределить все элементы в таблице. Хеш-функция возвращает целое число, и хеш-таблица должна взять результат хеш-функции и изменить его по размеру таблицы таким образом, чтобы можно было быть уверенным, что он попадет в корзину. Поэтому, увеличив размер, он будет перефразировать и запускать вычисления по модулю, которые, если вам повезет, могут отправлять объекты в разные корзины.

Java использует оба варианта 1 и 2 в своих реализациях хэш-таблицы.

Answer 2

Когда вы говорили о том, что «Хэш-таблица поместит новую запись в« следующую доступную »корзину, если новая запись ключа столкнется с другой.», Вы говорите о Открытой стратегии адресации разрешения коллизий. хеш-таблицы.

---

Существует несколько стратегий для хеш-таблицы для разрешения коллизий.

Первый тип большого метода требует, чтобы ключи (или указатели на них) были сохранены в таблице вместе со связанными значениями, которые дополнительно включают в себя:

• Отдельная цепочка

• Открытая адресация

• Объединенное хеширование
• Хеширование кукушки
• Хэширование Робин Гуда
• Хеширование с 2 вариантами выбора
• Хеширование Hopscotch

---

Другим важным методом обработки столкновений является Динамическое изменение размера , которое дополнительно имеет несколько способов:

• Изменение размера путем копирования всех записей
• Увеличение размера
• Монотонные клавиши

---

РЕДАКТИРОВАТЬ : вышеперечисленные заимствованы из wiki_hash_table , куда вы должны обратиться, чтобы узнать больше.

Answer 3

Есть несколько методов, доступных для обработки столкновений.Я объясню некоторые из них

Цепочка: В цепочке мы используем индексы массива для хранения значений.Если хэш-код второго значения также указывает на тот же индекс, мы заменяем это значение индекса на связанный список, и все значения, указывающие на этот индекс, сохраняются в связанном списке, а фактический индекс массива указывает на заголовок связанного списка.Но если существует только один хэш-код, указывающий на индекс массива, то значение непосредственно сохраняется в этом индексе.Та же логика применяется при получении значений.Это используется в Java HashMap / Hashtable, чтобы избежать коллизий.

Линейное зондирование: Этот метод используется, когда у нас в таблице больше индекса, чем значений, которые нужно сохранить.Техника линейного зондирования работает по принципу непрерывного увеличения, пока вы не найдете пустой слот.Псевдокод выглядит следующим образом:

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

Техника двойного хеширования: В этом методе мы используем две функции хеширования h1 (k) и h2 (k).Если слот в h1 (k) занят, то вторая функция хеширования h2 (k) используется для увеличения индекса.Псевдокод выглядит следующим образом:

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

Методы линейного зондирования и двойного хеширования являются частью техники открытой адресации, и его можно использовать только в том случае, если количество доступных слотов превышает количество добавляемых элементов.Это занимает меньше памяти, чем цепочка, потому что здесь не используется дополнительная структура, но она медленная из-за большого количества движения, пока мы не найдем пустой слот.Также в технике открытой адресации, когда элемент извлекается из слота, мы помещаем надгробную плиту, чтобы указать, что элемент удален отсюда, поэтому он пуст..

Answer 4

Я настоятельно рекомендую вам прочитать это сообщение в блоге, которое недавно появилось на HackerNews: Как работает HashMap в Java

Короче говоря, ответ

Что произойдет, если два разных объекта ключа HashMap будут иметь одинаковый хэш-код?

Они будут храниться в том же сегменте, но не в следующем узле связанного списка.И метод keys equals () будет использован для определения правильной пары значений ключей в HashMap.

Answer 5

Я слышал в своих классах степени, что HashTable разместит новую запись в «следующий доступный» ковш, если новый Ключ ввода сталкивается с другим.

На самом деле это не так, по крайней мере для Oracle JDK ( - это деталь реализации, которая может варьироваться в зависимости от реализации API). Вместо этого каждая корзина содержит связанный список записей до Java 8 и сбалансированное дерево в Java 8 или выше.

тогда как бы HashTable еще верните правильное значение, если это столкновение происходит при вызове одного вернуться с ключом столкновения?

Используется equals() для поиска фактически совпадающей записи.

Если я реализую свою собственную функцию хеширования и использовать его как часть справочной таблицы (то есть хэш-карта или словарь), что Существуют стратегии для борьбы с столкновения?

Существуют различные стратегии обработки столкновений с различными преимуществами и недостатками. Запись Википедии о хеш-таблицах дает хороший обзор.

Answer 6

Обновление с Java 8: Java 8 использует самоуравновешенное дерево для обработки коллизий, улучшая наихудший случай с O (n) до O (log n) для поиска.Использование самоуравновешенного дерева было введено в Java 8 как улучшение по сравнению с цепочкой (использовалось до Java 7), которая использует связанный список и имеет наихудший случай O (n) для поиска (так как ему необходимо пройтисписок)

Чтобы ответить на вторую часть вашего вопроса, вставка выполняется путем сопоставления данного элемента с заданным индексом в базовом массиве hashmap, однако, когда происходит столкновение, все элементы все равно должны бытьсохраняются (хранятся во вторичной структуре данных, а не просто заменяются в базовом массиве).Обычно это делается путем превращения каждого компонента массива (слота) во вторичную структуру данных (иначе говоря, в корзину), и элемент добавляется в корзину, находящуюся в данном индексе массива (если ключ еще не существует в корзине, вв этом случае он заменяется).

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

Обработка коллизий приносит худшую производительность вставки и поиска из O (1) в случае отсутствия обработки коллизий до O (n) для цепочки (связанный список используется в качестве вторичной структуры данных) и O(log n) для самоуравновешенного дерева.

Ссылки:

Java 8 имеет следующие улучшения / изменения объектов HashMap в случае сильных коллизий.

• Удалена альтернативная хеш-функция String, добавленная в Java 7.

• Баки, содержащие большое количество сталкивающихся ключей, вместо этого будут хранить свои записи в сбалансированном деревесвязанного списка после достижения определенного порога.

Вышеуказанные изменения обеспечивают производительность O (log (n)) в худших случаях (https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8)

* 1028)*

Answer 7

Поскольку существует некоторая путаница в отношении того, какой алгоритм использует HashMap Java (в реализации Sun / Oracle / OpenJDK), здесь приведены соответствующие фрагменты исходного кода (из OpenJDK, 1.6.0_20, в Ubuntu):

/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

Этот метод (цитата из строк 355–371) вызывается при поиске записи в таблице, например, из get(), containsKey() и некоторых других. Цикл for здесь проходит через связанный список, сформированный объектами записи.

Здесь код для объектов ввода (строки 691-705 + 759):

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

  // (methods left away, they are straight-forward implementations of Map.Entry)

}

Сразу после этого следует метод addEntry():

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

Это добавляет новую запись на передней части корзины со ссылкой на старую первую запись (или ноль, если таковой нет). Точно так же метод removeEntryForKey() проходит по списку и заботится об удалении только одной записи, оставляя остальную часть списка без изменений.

Итак, вот список связанных записей для каждого сегмента, и я очень сомневаюсь, что он изменился с _20 до _22, так как это было похоже с 1.2 на

.

(Этот код (c) 1997-2007 Sun Microsystems и доступен под лицензией GPL, но для копирования лучше использовать исходный файл, содержащийся в src.zip в каждом JDK от Sun / Oracle, а также в OpenJDK.)

Answer 8

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

Answer 9

Существуют различные методы разрешения коллизий. Некоторые из них: отдельная цепочка, открытая адресация, хэширование робин гуда, хеширование кукушки и т. Д.

Java использует раздельное связывание для разрешения коллизий в хэш-таблицах. Вот отличная ссылка на то, как это происходит: http://javapapers.com/core-java/java-hashtable/

Answer 10

вот очень простая реализация хеш-таблицы в Java.в только орудий put() и get(), но вы можете легко добавить все, что вам нравится.он основан на методе java hashCode(), который реализован всеми объектами.Вы можете легко создать свой собственный интерфейс,

interface Hashable {
  int getHash();
}

и заставить его реализовываться клавишами, если хотите.

public class Hashtable<K, V> {
    private static class Entry<K,V> {
        private final K key;
        private final V val;

        Entry(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    private static int BUCKET_COUNT = 13;

    @SuppressWarnings("unchecked")
    private List<Entry>[] buckets = new List[BUCKET_COUNT];

    public Hashtable() {
        for (int i = 0, l = buckets.length; i < l; i++) {
            buckets[i] = new ArrayList<Entry<K,V>>();
        }
    }

    public V get(K key) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        for (Entry e: entries) {
            if (e.key.equals(key)) {
                return e.val;
            }
        }
        return null;
    }

    public void put(K key, V val) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        entries.add(new Entry<K,V>(key, val));
    }
}