Алгоритм соединения хешированием

11-05-2021, 03:43

Алгоритм соединения хешированием (англ. hash join) — разновидность алгоритма соединения.

Алгоритм получает на вход две таблицы и условие соединения. Результатом его работы является таблица с результатами соединения.

Меньшая из двух входных таблиц помещается в специальную структуру данных в памяти: хеш-таблицу, которая обеспечивает очень высокую скорость поиска. Затем для каждой строки из большей таблицы выполняется поиск значений, соответствующих условию соединения. Результаты помещаются в выходную таблицу.

На псевдокоде алгоритм можно описать примерно так:

[ХешТаблица] = СтроитьХешТаблицу([МеньшаяТаблица], [Имена колонок МеньшейТаблицы по которым будет делаться соединение]); Для каждой строки [r] из [БольшаяТаблица] Вывести ([r], ИскатьВХешТаблице([ХешТаблица],[Имена колонок БольшойТаблицы по которым делается соединение]));

Преимущества

  • Соединение хешированием существенно быстрее соединения вложенными циклами. При относительно небольшом размере меньшей таблицы это самый эффективный вид соединения.

Недостатки

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

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


  • Гидрид рубидия
  • Угловой шов
  • Угловой шов
  • Фотостабилизатор
  • GLR-парсер

  •  

    • Яндекс.Метрика
    • Индекс цитирования