Почему связанные списки почти всегда используются с отдельной цепочкой?

Question

Кажется, что каждый раз, когда я вижу упоминание об отдельной цепочке в хеш-таблице, связанный список используется в качестве структуры данных для хранения элементов с коллизиями. Почему это? Например, почему вы не можете использовать вектор / массив данных?

Answer 1

Вы можете использовать вектор / ArrayList, но:

• Вам не нужны никакие функции, предоставляемые ArrayList, которых нет в связанном списке, например, индексация в списке за O (1).
• ArrayLists, как правило, имеют емкость больше, чем их текущая длина, что тратит впустую память.
• ArrayLists иногда должны увеличивать свою емкость, что медленно.

Answer 2

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

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