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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Cend
2 / 2 / 0
Регистрация: 25.02.2013
Сообщений: 112
#1

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

11.06.2016, 12:58. Просмотров 245. Ответов 7
Метки нет (Все метки)

На просторах 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 строке?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.06.2016, 12:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Определение хэш-функции для контейнера (C++):

Хэш функции - C++
Задание: Написать программу которая реализует хэш-функцию за 3 последними цифрами, идентификационного номера. Реализовать добавления и...

Написание хэш-функции - C++
Решил освоить хэш-функции, ну и, соответственно, написать реализации большинства. Вопросы неизбежны, поэтому, думаю, буду отписываться в...

Умножение хэш-функции - C++
Пытаюсь сделать гост 34.10.94. Там получаю хэш функцию:0xFAFF37A615A816691CFF3EF8B68CA247E09525F39F8119832EB81975D366C4B1. Дальше по...

Есть ли стандартные хэш функции - C++
Есть ли в C++ стандартные хэш функции, в которые передаешь строку, получаешь на возврате строку, типа MD5 или CRC32. Спасибо.

Пример коллизии хэш функции - C++
Видел пример в вики по поводу коллизии хэш функции, но не понял его. То есть, коллизия случается, когда на входе разные данные, а на выходе...

Нужны исходники хэш-функции - C++
SOS!!! пришлите кто-нибудь исходники хэш-функции на sedar@narod.ru

7
Nosey
1348 / 399 / 107
Регистрация: 22.10.2014
Сообщений: 861
Завершенные тесты: 2
11.06.2016, 14:37 #2
Цитата Сообщение от Cend Посмотреть сообщение
1. Правильно ли определена эта функция?
Ну работать она будет, насколько качественно - это вопрос набора данных.
Цитата Сообщение от Cend Посмотреть сообщение
2. Что значит 31 в 15 строке?
Магическое число , существующее для уменьшения коллизий хешей.
1
Cend
2 / 2 / 0
Регистрация: 25.02.2013
Сообщений: 112
11.06.2016, 16:42  [ТС] #3
Т.е. как делать правильную хэш функцию для своего типа в общем случае не известно и нигде не определено?

Добавлено через 5 минут
И сразу еще вопрос, может я что-то не так делаю, мне нужен контейнер
C++
1
std::unordered_map<uint64_t[4], std::string>
как его вообще правильно реализовать?
0
Nosey
1348 / 399 / 107
Регистрация: 22.10.2014
Сообщений: 861
Завершенные тесты: 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;
        }
    };
}
1
Cend
2 / 2 / 0
Регистрация: 25.02.2013
Сообщений: 112
11.06.2016, 17:38  [ТС] #5
Не, я понимаю что разные вещи, вопрос заключается в другом. Если, как Вы сказали, это настоящий ад для неискушенного математика, нет ли каких то стандартных решений для начинающего разработчика? Имеется ввиду без определения хэш-функций
0
4AKE
29 / 29 / 12
Регистрация: 20.12.2010
Сообщений: 116
11.06.2016, 18:14 #6
Cend, без определения хеша - надо использовать ключ базового или библиотечного типа. Или не использовать map.
0
Nosey
1348 / 399 / 107
Регистрация: 22.10.2014
Сообщений: 861
Завершенные тесты: 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.
0
4AKE
29 / 29 / 12
Регистрация: 20.12.2010
Сообщений: 116
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;
}
хеш примерный, на коллизии не проверял
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.06.2016, 18:37
Привет! Вот еще темы с ответами:

Класс хэш-функции, выскакивает ошибка - C++
Помогите разобраться в чем проблема, неправильно выдает результат class hash_{ private: std::string message; ...

Возврат контейнера STL из функции - C++
Как правильно вернуть STL контейнер из функции НЕ ПО ЗНАЧЕНИЮ? std :: map&lt;std :: string, BTSComponent*&gt; BTSObject :: getComponents()...

Описать класс "хэш-таблица", используя unordered_set и заданную хэш-функцию - C++
Здравствуйте. Есть класс объектов и ключ сравнения: #pragma once #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;list&gt; #include...

Тип контейнера как параметр шаблонной функции - C++
Добрый день. Подскажите, пожалуйста, можно ли передавать тип контейнера как параметр в шаблонную функцию? Если да, то как это делается? ...


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

Или воспользуйтесь поиском по форуму:
8
Yandex
Объявления
11.06.2016, 18:37
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru