Уточнение HashSet C++

Question

Я потерял эту тему, которую я изучал. В моем классе мы реализуем собственный хэш-набор. Таким образом, мы имеем базовую структуру данных, такую ​​как вектор или массив, и используем хэш-функцию, чтобы быстро определить, находится ли элемент в наборе. Это та часть, которой я не придерживаюсь. Как использовать хеш-функцию для этого определения?

Answer 1

представьте, что вы есть основной массив размером 100, и вы можете вставить только значения от 0 до 99.

что-то вроде этого:

class UselessHashMap 
{ 
public: 
    void insert(int value){ 
    _arr[hash(i)] = i; 
    } 
private: 
    int hash(int i) { return i }; 
    std::array<int,100> _arr; 
} 

теперь представьте, что вы хотите хранить более 100 элементов, и вы не можете иметь массив с бесконечным размером (std :: numeric_limits :: max()). В этом случае ваша хеш-функция должна вернуть вам значение от 0 до 99, и, конечно, ваш класс UselessHashMap также должен будет заботиться о столкновениях, потому что эта функция может возвращать одинаковое значение для разных входов.