Использование динамического массива для обработки столкновений в хэш-таблицах

Question

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

Что мне не хватает?

Answer 1

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

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

Надеюсь, это поможет!

Answer 2

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