стандартной библиотеки C++ хэш-код образца

Question

Я решил проблему, чтобы найти дубликаты в списке

Я использовал свойство набора, что он содержит только уникальные члены

set<int> s; 

// insert the new item into the set 
s.insert(nums[index]); 

// if size does not increase there is a duplicate 
if (s.size() == previousSize) 
{ 
    DuplicateFlag = true; 
    break; 
} 

Сейчас я пытаюсь решить та же проблема с хеш-функциями в стандартной библиотеке. У меня есть пример кода, как это

#include <functional> 

using namespace __gnu_cxx; 
using namespace std; 

hash<int> hash_fn2; 
int x = 34567672; 
size_t int_hash2 = hash_fn2(x); 

cout << x << " " << int_hash2 << '\n'; 

х и int_hash2 всегда одинаковы ли я что-то пропустил?

Answer 1

Для std::hash<int>, это нормально, чтобы вернуть оригинальное значение int. От specification необходимо только убедиться, что для двух разных параметрови k2, которые не равны, вероятность того, что std::hash<Key>()(k1) == std::hash<Key>()(k2) должна быть очень малой, приближается к 1.0/std::numeric_limits<size_t>::max(). Четкое возвращение исходного значения удовлетворяет требованию для std::hash<int>.

Answer 2

x и int_hash2 всегда одинаковы. Мне что-то не хватает?

Да. Вы говорите «Я пытаюсь решить ту же проблему с помощью хеш-функций», но функции хеша не являются функциональными альтернативами std::set<> и не могут сами по себе использовать для решения вашего пороблема. Вероятно, вы захотите использовать std::unordered_set<>, который будет использовать таблицу хеша , используя функцию std::hash<> (по умолчанию), чтобы помочь ей отобразить элементы из «ведра». Для целей хэш-таблицы хеш-функция для целых чисел, которая возвращает вход, обычно достаточно хороша, и если не предполагается, что программист предоставит свою предпочтительную альтернативу в качестве параметра шаблона.

В любом случае, все, что вам нужно сделать, чтобы попробовать хеш-таблицу, это изменить std:set<int> s; на std::unordered_set<int> s; в вашем исходном коде.