Почему сложность хеш-соединения O (n + m)?

Question

После того как я сделал поиск в Интернете, я обнаружил, что сложность алгоритма Hash Join для объединения двух таблиц называется O (N + M), где N и M - количество кортежей из двух таблиц.

Интересно, почему это O (N + M), вместо O (N * M) в худшем случае?

Насколько я знаю, Hash Join является реализацией equi-соединения: если заданы две таблицы R и S, то следует выбирать кортежи t из их кросс-произведения R * S, где t [RA] = t [SA] а представляет собой общий признак R и S.

Примечания: 1) Интересно, если сложность O (N + M), особенно, когда значение данных является не уникальны в атрибуте соединения (т.е. мы не присоединяются к ключевым атрибутам). 2) Обратите внимание, что соединение атрибута A может быть или не быть ключом.

Answer 1

Алгоритм поиска в основном:

1. хэш каждый кортеж из R (O (п))

2. хэш каждый кортеж из S (O (м))

   2.1 каждая Посмотрите на хеширование R (O (1))

   2.2 только если соответствующий хэш в найденном для R, сравните фактические значения кортежа (O (1))

Следовательно, вам нужно всего вычислить один хэш на каждый кортеж (n + m) и выполнить поиск хэшей, который идеально подходит для O (1).

Конечно, если хеш-функция не соответствует фактическим данным, или хеш-таблица слишком мала, поиск хэшей все равно будет O (1), но вам, возможно, придется выполнять множество полных сопоставлений кортежей, большинство из которых выход false. Таким образом, худший худший случай, для худший случай хеш-таблица, снова подходит к O (n * m).