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


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

2 3

2 ответа:

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

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

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

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