Являются ли элементы резервного массива таблицы Ha sh связанными списками от начальной точки при использовании раздельного связывания?

Question

Как обычно, провёл довольно много исследований в разных книгах и академических статьях c, но не могу получить четкую картину.

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

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

Один инструктор даже сказал так, что:

Элементы массива резервного копирования в отдельной цепочке, являются связанными списками.

Мой вопрос следующий: является ли тип резервного массива Linked List из момент создания таблицы Ha sh (при реализации отдельной стратегии сцепления) или она преобразуется в этот массив после первого столкновения? потому что наличие связанных списков в качестве каждого элемента резервного массива означает, что эти связанные списки должны быть списком элементов, которые, в свою очередь, являются записями / сегментами пары ключ-значение. Это все действительно потребляет много памяти и ресурсов, я считаю.

Спасибо.

Answer 1

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

Обратите внимание, что сам резервный массив не является связанный список. Вспомогательный массив для таблицы ha sh, которая использует зондирование или повторное хеширование, вероятно, будет массивом записей динамического размера. Ваша запись будет выглядеть примерно так:

class Entry {
    String: key;
    SomeObject: value;
}

Если вы используете отдельную цепочку, объект Entry получает дополнительное поле: ссылку на следующий элемент, хэшированный в том же сегменте:

class Entry {
    String: key;
    SomeObject: value;
    Entry: next;
}

Разница в памяти для первого элемента на самом деле не достаточна для беспокойства.

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