Форум программистов, компьютерный форум CyberForum.ru

Определение хэш-функции для контейнера - C++

Восстановить пароль Регистрация
 
Cend
2 / 2 / 0
Регистрация: 25.02.2013
Сообщений: 100
11.06.2016, 12:58     Определение хэш-функции для контейнера #1
На просторах stackoverflow нашел следующую реализацию для std::аrrаy:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
namespace std
{
    template<typename T, size_t N>
    struct hash<аrrаy<T, N> >
    {
        typedef аrrаy<T, N> argument_type;
        typedef size_t result_type;
 
        result_type operator()(const argument_type& a) const
        {
            hash<T> hasher;
            result_type h = 0;
            for (result_type i = 0; i < N; ++i)
            {
                h = h * 31 + hasher(a[i]);
            }
            return h;
        }
    };
}
Возникли следующие вопросы:
1. Правильно ли определена эта функция?
2. Что значит 31 в 15 строке?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.06.2016, 12:58     Определение хэш-функции для контейнера
Посмотрите здесь:

Хэш функции C++
C++ Нужны исходники хэш-функции
C++ Класс хэш-функции, выскакивает ошибка
C++ Тип контейнера как параметр шаблонной функции
Пример коллизии хэш функции C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nosey
 Аватар для Nosey
1184 / 351 / 102
Регистрация: 22.10.2014
Сообщений: 786
Завершенные тесты: 2
11.06.2016, 14:37     Определение хэш-функции для контейнера #2
Цитата Сообщение от Cend Посмотреть сообщение
1. Правильно ли определена эта функция?
Ну работать она будет, насколько качественно - это вопрос набора данных.
Цитата Сообщение от Cend Посмотреть сообщение
2. Что значит 31 в 15 строке?
Магическое число , существующее для уменьшения коллизий хешей.
Cend
2 / 2 / 0
Регистрация: 25.02.2013
Сообщений: 100
11.06.2016, 16:42  [ТС]     Определение хэш-функции для контейнера #3
Т.е. как делать правильную хэш функцию для своего типа в общем случае не известно и нигде не определено?

Добавлено через 5 минут
И сразу еще вопрос, может я что-то не так делаю, мне нужен контейнер
C++
1
std::unordered_map<uint64_t[4], std::string>
как его вообще правильно реализовать?
Nosey
 Аватар для Nosey
1184 / 351 / 102
Регистрация: 22.10.2014
Сообщений: 786
Завершенные тесты: 2
11.06.2016, 17:21     Определение хэш-функции для контейнера #4
Цитата Сообщение от Cend Посмотреть сообщение
Т.е. как делать правильную хэш функцию для своего типа в общем случае не известно и нигде не определено?
Именно так, но не заморачивайтесь о хэш функциях, пока оно не потребуется, а если потребуется и будет возможность заморочиться, то проанализируете ваши ключи и попробуете скорректировать равномерность распределения ключей определенной хэш функцией. Но это настощий ад, для неискушенного математика

Цитата Сообщение от Cend Посмотреть сообщение
И сразу еще вопрос, может я что-то не так делаю, мне нужен контейнер
std::unordered_map<uint64_t[4], std::string>
как его вообще правильно реализовать?
С массив и std::array - это разные типы. Т.е.:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
namespace std
{
    template<typename T, size_t N>
    struct hash<T[N]>
    {
        using argument_type = T[N];
        using result_type = size_t;
 
        result_type operator()(const argument_type& a) const
        {
            hash<T> hasher;
            result_type h = 0;
            for (result_type i = 0; i < N; ++i)
            {
                h = h * 31 + hasher(a[i]);
            }
            return h;
        }
    };
}
Cend
2 / 2 / 0
Регистрация: 25.02.2013
Сообщений: 100
11.06.2016, 17:38  [ТС]     Определение хэш-функции для контейнера #5
Не, я понимаю что разные вещи, вопрос заключается в другом. Если, как Вы сказали, это настоящий ад для неискушенного математика, нет ли каких то стандартных решений для начинающего разработчика? Имеется ввиду без определения хэш-функций
4AKE
29 / 29 / 12
Регистрация: 20.12.2010
Сообщений: 115
11.06.2016, 18:14     Определение хэш-функции для контейнера #6
Cend, без определения хеша - надо использовать ключ базового или библиотечного типа. Или не использовать map.
Nosey
 Аватар для Nosey
1184 / 351 / 102
Регистрация: 22.10.2014
Сообщений: 786
Завершенные тесты: 2
11.06.2016, 18:17     Определение хэш-функции для контейнера #7
Cend,
Еще раз скажу - не заморачивайтесь об этом и используйте верхнюю хэш функцию. До поры до времени(я бы оценил эту пору в >10000 элементов в контейнере, а на самом деле даже >100000) вы можете увеличивать количество бакетов(unordered_map::reserve), если у вас не критична память, это уменьшит колизии и избавит от балансировки.
Если же у вас >10k элементов и алгоритм использующий unordered_map критичен к производительности и памяти и без использования unordered_map этот алгоритм не переделать, то тогда можете начинать развлекаться с хэш функциями, но опять же, очень советую убедиться что ботлнек именно в работе unordered_map.

Маленький линк по хэш функциям: https://habrahabr.ru/post/219139/

Цитата Сообщение от Cend Посмотреть сообщение
нет ли каких то стандартных решений для начинающего разработчика? Имеется ввиду без определения хэш-функций
Для начинающего и без хэш функций есть "замена" std::map.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.06.2016, 18:37     Определение хэш-функции для контейнера
Еще ссылки по теме:

C++ Есть ли стандартные хэш функции
C++ Квадратичная фунция для хэш-таблицы
Написание хэш-функции C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4AKE
29 / 29 / 12
Регистрация: 20.12.2010
Сообщений: 115
11.06.2016, 18:37     Определение хэш-функции для контейнера #8
для std::unordered_map<uint64_t[4], std::string> можно так упороться:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <unordered_map>
#include <cstdint>
 
using namespace std;
 
typedef uint64_t KeyType;
 
struct Key {
    KeyType data[4];
    friend bool operator==(const Key& lhs, const Key& rhs) {
        return std::equal(lhs.data, lhs.data + 4, rhs.data);
    }
    friend ostream& operator<<(ostream& os, const Key& dt) {
        os << '{' << dt.data[0] << ',' << dt.data[1] << ',' << dt.data[2] << ',' << dt.data[3] << '}';
        return os;
    }
};
 
struct KeyHasher {
    std::size_t operator()(const Key& k) const {
        return ((hash<KeyType>()(k.data[0])
            ^ (hash<KeyType>()(k.data[1]) << 1)) >> 1)
            ^ (hash<KeyType>()(k.data[2]) << 1)
            ^ (hash<KeyType>()(k.data[3]) << 1);
    }
};
 
int main() {
    Key key1 = { 1, 2, 12, 8 };
 
    std::unordered_map<Key, std::string, KeyHasher> m = {
        { key1, "example" },
        { { 1, 3, 21, 9 }, "another" },
        { { 1, 4, 21, 9 }, "another2" },
    };
    m[{{ 1, 2, 12, 9 }}] = "test";
    m[Key( { 2, 2, 2, 2 } )] = "test2";
    m.insert({ { 2, 1, 2, 2 }, "test3" });
 
    for (auto elem : m) {
        std::cout << elem.first << " " << elem.second.data() << "\n";
    }
    cin.get();
    return 0;
}
хеш примерный, на коллизии не проверял
Yandex
Объявления
11.06.2016, 18:37     Определение хэш-функции для контейнера
Ответ Создать тему
Опции темы

Текущее время: 13:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru