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

Ответ 1

Таблицы хэшей относятся к коллизиям одним из двух способов.

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

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

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

Ответ 2

Когда вы говорили о "Hash Table", в новую клетку будет добавлена ​​новая запись, если новая запись Key столкнутся с другой. ", вы говорите о стратегии Open address Collision разрешение хэш-таблицы.

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

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

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

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

• Объединенное хэширование
• Хэширование кукушки
• Хешинг Робин Гуда
• хеширование 2-х элементов
• хеширование хмеля

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

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

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

Ответ 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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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

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

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

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

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

Ответ 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)

Ответ 7

Как есть некоторая путаница в отношении того, какой алгоритм использует Java HashMap (в реализации 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);
}

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

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

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

Ответ 8

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

Ответ 9

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

Ответ 10

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

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