Использование HashSet для целых чисел

Question

У меня есть два списка. Я хочу найти наименьшее общее число в двух. Я думал об использовании HashSet, поскольку он не позволяет дублировать. Я могу узнать общие числа, добавив к ним оба элемента списка. И HashSet принимает только constant time для вставки. Это может дать мне O(n), чтобы найти самый маленький из двух. Но как HashSet может вставить n элементов в constant time? В этом случае для добавления последнего элемента требуется O(n), потому что для поиска правильного ведра он должен сравнивать хэш-код с n ковшими в худшем случае. Пожалуйста, исправьте это и спасибо заранее ..!

Answer 1

алгоритм выглядит довольно просто:

1. Построить HashSet, содержащий элементы списка A.
2. Инициализировать min быть чем-то большим, как Integer.MAX_VALUE.
3. Для каждого элемента в B, проверьте, находится ли он в HashSet. Если это так, и оно меньше min, тогда обновите min.

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

Answer 2

Поиск ведра постоянное - это зависит только от хэш-значения данного объекта, а не от существующих объектов.

Answer 3

Вы можете найти ответ в любой книге алгоритмов (например, Corman, Knuth). Коротко: bucketIndex = toPositiveInteger (хэш-код())% buckets.length