it-swarm-ru.tech

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

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

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

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

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

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

81
Alex

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

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

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

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

84
ams

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


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

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

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

enter image description here

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

enter image description here

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

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

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

EDIT: вышеперечисленные заимствованы из wiki_hash_table , куда вы должны обратиться, чтобы получить больше информации.

65
herohuyongtao

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

Цепочка: В цепочке мы используем индексы массива для хранения значений. Если хэш-код второго значения также указывает на тот же индекс, мы заменяем это значение индекса на связанный список, и все значения, указывающие на этот индекс, сохраняются в связанном списке, а фактический индекс массива указывает на заголовок связанного списка. Но если существует только один хэш-код, указывающий на индекс массива, то значение непосредственно сохраняется в этом индексе. Та же логика применяется при получении значений. Это используется в 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

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

Для получения дополнительной информации см. этот сайт .

17
Jatinder Pal

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

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

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

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

16
zengr

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

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

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

Он использует equals(), чтобы найти фактически совпадающую запись.

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

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

7
Michael Borgwardt

Обновление с 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-в-Java-8 )

5
Daniel Valland

Поскольку существует некоторая путаница в отношении того, какой алгоритм использует 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 здесь проходит через связанный список, сформированный объектами entry.

Вот код для ввода объектов (строки 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.)

3
Paŭlo Ebermann

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

2
Hovercraft Full Of Eels

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

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

1

вот очень простая реализация хеш-таблицы в 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));
    }
}
1
Jeffrey Blattman