Какую вещь hash_map хранит в качестве ключей?

Question

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

Заранее спасибо

Answer 1

Хеш-функция используется для размещения пары <key,value>, поэтому при вставке числа в качестве ключа оно сохраняется в позиции, назначенной функцией, с данными, связанными в качестве значения.

Вам нужно только попытаться получить это целое число в качестве ключа и увеличить его значение.

Answer 2

Ответ зависит от ограничений реализации, но если числа int32 или меньше, я предпочитаю ленивое выделение 512 МБ (поэтому отдельные физические страницы будут выделяться только при его использовании, частное отображение / dev /ноль - это традиционный подход в Unix) и использовать его в качестве набора битов.Если размер слова меньше, вам придется прибегнуть к какому-либо хешу (возможно, многоуровневому), варианту k-арного дерева или некоторой комбинации вышеперечисленного.хэш или

Если вы ищете что-то большее, чем int32, вы не предоставили достаточно информации, чтобы дать совет.То же самое относится, если вы не можете позволить себе 512 МБ ОЗУ для вашего набора битов.

Answer 3

hash_map хешированный ассоциативный контейнер , означающий, что они связывают ключ со значением.Так что да, значение, которое вы ему даете, хранится в hash_map.Обычно у вас нет прямого доступа к хеш-коду.Чтобы решить вашу проблему с hash_map, вам нужно будет сделать что-то вроде myHashMap[myInt] = true;, когда вы получите myInt.Затем для следующего int вам нужно будет проверить, сохранен ли ваш int ...

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

my2c