С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 07.04.2024
Сообщений: 7

Реализация класса хэширования для текста

13.07.2024, 19:13. Показов 1426. Ответов 19

Студворк — интернет-сервис помощи студентам
В чем ошибка реализации хэш класса ? Почему постоянно образуются коллизии большие и правильно ли параметры p, q задаются ?

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
class Hash {
private:
    int p, q;
    vector<vector<pair<int, int>>> hash_table;
public:
    Hash() = default;
    Hash(string text) {
        bool is_created_table;
        do {
            is_created_table = true;
            p = rand();
            q = ( 10078200 + rand() % 10000 ) % 100000000;
            hash_table.clear();
            hash_table.resize(q);
            for (int i = 0; i < text.size(); ++i) {
                int last = 0;
                for (int j = i; j < text.size(); ++j) {
                    int key = (last * p + text[j]) % q;
                    if (hash_table[key].size() > log2(q)) {
                        is_created_table = false;
                        break;
                    }
                    hash_table[key].push_back({ i, j });
                    last = key;
                }
            }
        } while (!is_created_table);
    }
 
    /*int getKey(string sub_str, string text) {
    }*/
};
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
13.07.2024, 19:13
Ответы с готовыми решениями:

Реализация алгоритма хэширования MD5
привет, пожалуста помогите написать програму какая шіфрует даные в формате MD5. Оч надо пожалуста..

Реализация 2-х методов хэширования
Привет всем. Нужна помощь в реализации 2-х методов хэшеирования: 1) Деление по модулю t 2) Средняя часть квадрата Кто знает,...

Собственная реализация хэширования MD5
Помогите с реализацией md5 на C# без использования System.Security.Cryptography. Гуглил, везде или не полный код или не рабочий. Может у...

19
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6147 / 2840 / 1040
Регистрация: 01.06.2021
Сообщений: 10,348
13.07.2024, 19:35
rodn1k, используй готовые функции

C++
1
2
3
4
5
6
7
8
9
#include <iostream>
#include <string>
#include <string_view>
 
int main()
{
    std::cout << std::hash<std::string>{}("meow") << '\n';
    std::cout << std::hash<std::string_view>{}("meow") << '\n';
}
0
0 / 0 / 0
Регистрация: 07.04.2024
Сообщений: 7
13.07.2024, 20:04  [ТС]
Это учебное задание, самому надо такой класс реализовать
0
13.07.2024, 20:47

Не по теме:

rodn1k, в инете полно кодов, воруй один. например, на перезагрузке стека точно есть

0
Заблокирован
13.07.2024, 20:59
Лучший ответ Сообщение было отмечено rodn1k как решение

Решение

Цитата Сообщение от rodn1k Посмотреть сообщение
Это учебное задание, самому надо такой класс реализовать
И что он делает ?

Добавлено через 2 минуты
Дошло.
Создать хеши, индексы для быстрого поиска подстрок.
Где то я такое видел...

Добавлено через 8 минут
Если просто хеширование строки, то первый подходящий : Полиномиальное хэширование
0
Неэпический
 Аватар для Croessmah
18144 / 10728 / 2066
Регистрация: 27.09.2012
Сообщений: 27,026
Записей в блоге: 1
13.07.2024, 22:05
Цитата Сообщение от rodn1k Посмотреть сообщение
q = ( 10078200 + rand() % 10000 ) % 100000000;
q = ((kx + b)%p)%m, где
k > 0, m > 0, p > 0, p > m, p - простое
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
13.07.2024, 22:21
Цитата Сообщение от rodn1k Посмотреть сообщение
q = ( 10078200 + rand() % 10000 ) % 100000000;
А что за алгоритм, использующий (псевдо)случайные значения? оО
0
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6147 / 2840 / 1040
Регистрация: 01.06.2021
Сообщений: 10,348
14.07.2024, 01:40
lemegeton, "убийственный" хеш называется
1
14.07.2024, 09:27

Не по теме:

Цитата Сообщение от Royal_X Посмотреть сообщение
"убийственный" хеш называется
генератор коллизий...

0
0 / 0 / 0
Регистрация: 07.04.2024
Сообщений: 7
14.07.2024, 11:10  [ТС]
это псевдослучайные числа ?

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
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <ctime>
 
using namespace std;
 
class Hash {
private:
    int p, q;
    vector<vector<pair<int, int>>> hash_table;
public:
    Hash() = default;
    Hash(string text) {
        bool is_created_table;
        do {
            is_created_table = true;
            p = rand();
            q = ( 10078200 + rand() % 10000 ) % 100000000;
            hash_table.clear();
            hash_table.resize(q);
            for (int i = 0; i < text.size(); ++i) {
                int last = 0;
                for (int j = i; j < text.size(); ++j) {
                    int key = (last * p + text[j]) % q;
                    if (hash_table[key].size() > log2(q)) {
                        is_created_table = false;
                        break;
                    }
                    hash_table[key].push_back({ i, j });
                    last = key;
                }
            }
        } while (!is_created_table);
    }
 
    /*int getKey(string sub_str, string text) {
    }*/
};
 
int main() {
    srand(time(0));
    string str;
 
    ifstream in("text8");
    if (in.is_open()) {
        getline(in, str);
    }
    else {
        std::cout << "Error...";
        throw;
    }
    
    Hash h_str(str);
}
0
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6147 / 2840 / 1040
Регистрация: 01.06.2021
Сообщений: 10,348
14.07.2024, 11:47
rodn1k, видимо, ты использовал плохую модель или промт отстойный. На форуме принято показывать свои попытки, а не просто чужой говнокод. Не нужно врать, что это ты сам написал. Не понимаешь даже, где псевдослучайные числа...
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
14.07.2024, 14:24
Цитата Сообщение от Royal_X Посмотреть сообщение
lemegeton, "убийственный" хеш называется
Это потому, что потом по нему ничерта не найдешь?

Мне вот понравился FNV1a. Простенько и минималистично.
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
#include <iostream>
#include <cstdint>
#include <vector>
 
/**
 * @see http://isthe.com/chongo/tech/comp/fnv/#FNV-param
 */
template<typename Iterator>
uint64_t getFNV1a64(Iterator begin, Iterator end) {
    static const uint64_t FNV_PRIME = 1099511628211u;
    static const uint64_t OFFSET_BASIS = 14695981039346656037u;
 
    size_t result = OFFSET_BASIS;
    while (begin != end) {
        result ^= *begin++;
        result *= FNV_PRIME;
    }
 
    return result;
}
 
struct Hash {
    uint64_t operator()(const std::string &string) {
        return getFNV1a64(string.begin(), string.end());
    }
};
 
int main() {
    Hash hash;
 
    std::string text = "something for everybody";
    std::cout << hash(text);
 
    const size_t buckets = 64;
    std::vector<std::vector<std::pair<uint64_t, std::string>>> hashTable(buckets, std::vector<std::pair<uint64_t, std::string>>());
    auto hashKey = hash(text);
    hashTable[hashKey % buckets].push_back({hashKey, text});
 
    return 0;
}
Добавлено через 16 минут
Цитата Сообщение от rodn1k Посмотреть сообщение
Почему постоянно образуются коллизии большие
Кто такие "большие коллизии"?
Тексты вообще довольно однообразны как числа.
Почти любые алгоритмы будут давать большое количество коллизий.
2
0 / 0 / 0
Регистрация: 07.04.2024
Сообщений: 7
14.07.2024, 20:12  [ТС]
1. Это мой код. 2. Почему это не случайные числа, если я запускал программу и разные числа присваиваются ? Даже если они псевдослучайные то ведь с 3-4 попытки должна таблица получаться без длинных коллизий.
0
Заблокирован
15.07.2024, 00:23
Цитата Сообщение от lemegeton Посмотреть сообщение
Мне вот понравился FNV1a. Простенько и минималистично.
Кликните здесь для просмотра всего текста

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <random>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <cstdint>
 
struct WordGenerator{
   
   WordGenerator():gen((std::random_device()())), alpha_dist('a', 'z'),
      length_dist({5, 17, 22, 19, 11, 8, 6, 4, 3, 2})
   {}
   
   std::string operator()(){
      auto alpha_gen = [&gen = gen, &alpha_dist = alpha_dist](){return alpha_dist(gen);}; 
      std::string word(length_dist(gen)+1, {});
      std::generate(word.begin(), word.end(), alpha_gen);
      return  word;
   }
 
private:
   std::mt19937 gen;
   std::uniform_int_distribution<unsigned> alpha_dist;
   std::discrete_distribution<>            length_dist;
};
 
template<typename Iterator>
uint64_t getFNV1a64(Iterator begin, Iterator end) {
    static const uint64_t FNV_PRIME = 1099511628211u;
    static const uint64_t OFFSET_BASIS = 14695981039346656037u;
 
    size_t result = OFFSET_BASIS;
    while (begin != end) {
        result ^= *begin++;
        result *= FNV_PRIME;
    }
 
    return result;
}
uint64_t Proxy(const std::string& word){
   return getFNV1a64(word.begin(), word.end());
}
 
int main(){
   const std::size_t test_count = 100000;
   std::unordered_set<std::string> words;
   unsigned gen_cnt = 0;
   
   WordGenerator word_gen;
   
   while(words.size() != test_count){
      words.insert(word_gen());
      ++gen_cnt;
   }
   
   std::cout << "generates " << gen_cnt << std::endl;
   {   
      std::unordered_set<std::uint64_t> hashes;
      std::hash<std::string> hasher;
      for(const auto& word : words)
         hashes.insert(hasher(word));
      std::cout << "Test count : " << test_count << std::endl;
      std::cout << "Unique hashes by < std::hash > : " << hashes.size() << std::endl;
   }
   
   {   
      std::unordered_set<std::uint64_t> hashes;
      for(const auto& word : words)
         hashes.insert(Proxy(word));
      std::cout << "Test count : " << test_count << std::endl;
      std::cout << "Unique hashes by < getFNV1a64 > : " << hashes.size() << std::endl;
   }
}
Code
1
2
3
4
5
generates 155493
Test count : 100000
Unique hashes by < std::hash > : 100000
Test count : 100000
Unique hashes by < getFNV1a64 > : 100000
Code
1
2
3
4
5
generates 2047491
Test count : 1000000
Unique hashes by < std::hash > : 1000000
Test count : 1000000
Unique hashes by < getFNV1a64 > : 1000000


Я что-то напутал или действительно все хеши уникальные ???

Цитата Сообщение от lemegeton Посмотреть сообщение
Почти любые алгоритмы будут давать большое количество коллизий.
Непонятно это утверждение...
1
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
15.07.2024, 00:23
Цитата Сообщение от SmallEvil Посмотреть сообщение
Я что-то напутал или действительно все хеши уникальные ???
Да нет конечно. )
Свести больше восьми байт к восьми без коллизий нереалистично. Но на больших текстах даёт неплохое распределение.

Цитата Сообщение от SmallEvil Посмотреть сообщение
Непонятно это утверждение...
Я имел в виду что хэши в случае текста это сведение большого количества байт к малому. Коллизии обязательно будут, и чем длиннее тексты, тем больше (вероятность) коллизий. В случае очень похожих значений, как, например, предложения из текстов из книжек, лучше подбирать алгоритм с хорошей дистрибуцией, чем с низкой вероятностью коллизии. Например, чтоб hash("abc") != hash("cba") и т.п.
0
Заблокирован
15.07.2024, 00:25
Цитата Сообщение от lemegeton Посмотреть сообщение
Коллизии обязательно будут, и чем длиннее тексты
Цитата Сообщение от SmallEvil Посмотреть сообщение
Code
1
2
3
4
5
generates 2047491
Test count : 1000000
Unique hashes by < std::hash > : 1000000
Test count : 1000000
Unique hashes by < getFNV1a64 > : 1000000
Это короткий тест ?

Могу и с книжки взять, не думаю что что-то изменится.
0
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6147 / 2840 / 1040
Регистрация: 01.06.2021
Сообщений: 10,348
15.07.2024, 00:25
Цитата Сообщение от SmallEvil
Непонятно это утверждение...
Насчёт большого количества не согласен, но то, что такие коллизии всегда будут, то это факт. В говнокодах (алгоритмах, написанных школьниками) таких коллизий и вправду будет много. Но в современных криптостойких хэш-функциях вероятность появления коллизии близка нулю. И тем не менее, она может появиться)
0
Заблокирован
15.07.2024, 00:32
Цитата Сообщение от lemegeton Посмотреть сообщение
Коллизии обязательно будут
Это то понятно, тип то 64 бита, коллизии начнутся, вопрос когда ?

Добавлено через 5 минут

Не по теме:

Цитата Сообщение от lemegeton Посмотреть сообщение
Коллизии обязательно будут, и чем длиннее тексты
Прочитал "тесты", пора спать ))

0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
15.07.2024, 00:33
Цитата Сообщение от SmallEvil Посмотреть сообщение
Это то понятно, тип то 64 бита, коллизии начнутся, вопрос когда ?
в этом смысле -- довольно нескоро, конечно, при хорошей дистрибуции. )
Или искусственно подобрать коллизии. Тоже можно попробовать.
0
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6147 / 2840 / 1040
Регистрация: 01.06.2021
Сообщений: 10,348
15.07.2024, 00:34
SmallEvil, а я прочёл цитату и твой коммент и сразу не понял, почему тебе пора спать, значит и мне пора спать.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
15.07.2024, 00:34
Помогаю со студенческими работами здесь

Собственная реализация хэширования пароля
Заказчик выдвинул два требования. 1)пользователи и все что с ними связано хранятся в общей базе 2)пароли хранятся там же в виде...

Реализация класса для шахматного коня
Реализуйте класс для шахматного коня (Knight). Интерфейс этого класса должен соответствовать интерфейсу шахматной фигуры, который разбирали...

Реализация итератора для шаблонного класса
Изучаю С++. Решил реализовать свой вариант контейнера vector. Класс решил сделать шаблонным. Чтобы следовать идеи интерфейс - реализация,...

Реализация конструктора копирования для класса
P.S плохо с русским Этот конструктор копирования сломал мне мозг И вот что я понемаю когда мы делаем так foo objCopy(obj); ...

Класс для представления хэширования в строку
Покажите, как правильно реализовать


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru