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

Ответ 1

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

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

Одна слабость линейного исследования заключается в том, что при плохом выборе хеш-функции первичная кластеризация может привести к значительному ухудшению производительности таблицы, Хотя цепное хеширование может по-прежнему страдать от плохих хеш-функций, оно менее чувствительно к элементам с соседними хэш-кодами, которые не оказывают неблагоприятного воздействия на время выполнения. Теоретически, линейное зондирование дает только ожидаемые O (1) поисковые запросы, если хеш-функции 5-независимые или если достаточная энтропия в ключах. Существует много способов решить эту проблему, поскольку, используя метод хэширования Робин Гуда или хэширование hopscotch, оба из которых имеют значительно лучшие худшие случаи, чем линейное исследование ванили.

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

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

Ответ 2

Линейное зондирование на самом деле более эффективно для памяти, когда хеш-таблица близка к полной.

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

Почему он использует меньше памяти?

Рассмотрим, как выглядят таблицы: (отдельные вариации цепочки по Wikipedia - есть и другие варианты, но они обычно используют больше памяти)

Linear             Separate chaining #1    Separate chaining #2
probing            List head in table      Pointer in table
|------|           |------|---|            |---|    |------|---|
|Object|           |Object|Ptr|            |Ptr| -> |Object|Ptr|
|------|           |------|---|            |---|    |------|---|
|Object|           |Object|Ptr|            |Ptr| -> |Object|Ptr|
|------|           |------|---|            |---|    |------|---|
| NULL |           | NULL |Ptr|            |Ptr|
|------|           |------|---|            |---|
 .                  .                       .
 .                  .                       .
 .                  .                       .

(Ptr означает "указатель" - любой указатель, не указывающий на что-то, может считаться NULL)

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

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

templatetypedef, вероятно, справедлив в том, что линейное зондирование обычно происходит быстрее (он редко ошибается), но он обычно учил, что отдельная цепочка выполняется быстрее, и вы видите это в основном API (например, Java-реализации, возможно, из-за этого, чтобы избежать случаев, когда линейное зондирование происходит намного медленнее (с несколькими хорошо известными, выбранные значения, вы можете быстро достичь производительности O(n) с линейным зондированием, в то время как отдельная цепочка была бы еще O(1)) или, возможно, по какой-то другой причине.