Какой массив вставить в хеш-таблицу для сравнения двух массивов

Question

На прошлой неделе я получил интервью с компанией Top software. И среди многих вопросов я получил эту проблему. Чтобы получить общие элементы двух массивов, используйте хеш-таблицу, которую вы вставите в хеш-таблицу (предположим, что коллизия хэшей отсутствует). Размер массива намного больше, чем у другого. Могу ли я получить некоторые объяснения по этому поводу? Я также хочу знать о случае с коллизией хэшей. Спасибо.

Answer 1

Средний случай хэша для вставки и поиска равен O (1), поэтому, если мы предположим, что столкновения нет, и это идеальный хеш, то общая сложность для обоих случаев будет равна (размер меньшего и большего массивов равен 'm' и «М» соответственно)

M x O(1) + m x O(1)

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

m x O(m) + M x O(m)