Хэширование

@cinekst_207 · Регистрация: 25.03.2018

Студворк — интернет-сервис помощи студентам

Здравствуйте, вот прям вообще не понимаю, что нужно делать и что есть что и где

.
1)Преобразование строкового ключа в целое число: Сложение двухбайтовых слов; после каждого сложения – циклический сдвиг суммы на один разряд влево.
2)Хеширование целочисленного ключа: Алгоритм середины квадрата.
3)Разрешение коллизий: Алгоритм двойного хеширования.

Как я понимаю, нужно сначала преобр. строку, потом полученную сумму что-ли надо прогнать через хэш-функцию, и потом проверить данные хэша через АДХ, так чтоли?
По 1-му пункту вроде понял:

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
unsigned short int Hash_Func(char *key) {
 
    unsigned short int sum = 0;
    char space = ' ';
 
    for (int i = 0; (i+2) <= strlen(key); i += 2) {
        // Если сумма после сложения увеличилась :
        if (sum >= (sum + abs(key[i]) + abs(key[i + 1])))
            sum = (sum + abs(key[i]) + abs(key[i + 1])+1);
        // Иначе :
        else sum = (sum + abs(key[i]) + abs(key[i + 1]));
        //Организация циклического сдвига влево :
        if (sum & 0x8000 != 0) sum = (sum << 1) + 1; 
        else  sum = (sum << 1);
    }
 
    if (i == (strlen(key) - 1)) {
        //Если сумма после сложения увеличилась :
        if (sum >= (sum + abs(key[i]) + space))
            sum = (sum + abs(key[i]) + space + 1);
        // Иначе :
        else sum = (sum + abs(key[i]) + space);
        //Организация циклического сдвига влево :
        if (sum & 0x8000!=0) sum = (sum << 1) + 1; 
        else  sum=(sum<<1);
    }
 
    return sum;
}

А дальше что делать? Примерами кода можете помочь?

@L0M · 07.11.2018, 00:32

Не прокатит.

Во-первых, в 17-й строке переменной i не существует. Это переменная, объявленная в цикле for (6-я строка). И по окончании цикла она умерает. Так говорит Стандарт.

Во-вторых, из всего кода правильно написан только циклический сдвиг влево. Всё остальное - в корзину.

Надо в цикле брать из строки по 2 char'а (2 байта), преобразовывать их в unsigned short ("двухбайтовое слово"), а затем суммировать с последующим циклическим сдвигом влево.

Единственная сложность - обработать конец строки нечётной длины. Здесь надо аккуратно.

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

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
#include <iostream>
 
using namespace std;
 
union TwoBytes {
    char ch[2];
    unsigned short us;
};
 
inline void rot_left(unsigned short &us) {
    us = (us & 0x8000 ? (us << 1) + 1 : us << 1);
}
 
unsigned short makeHash(const char *key) {
    TwoBytes word;
    unsigned short sum = 0;
    size_t i = 0;
    while (key[i]) {
        word.ch[i % 2] = key[i];
        if (i % 2 == 1) {
            sum += word.us;
            rot_left(sum);
        }
        ++i;
    }
    if (i % 2 == 1) {
        word.ch[1] = '\0';
        sum += word.us;
        rot_left(sum);
    }
    return sum;
}
 
int main() {
    const char *str = "Hello, World!";
    unsigned short hash = makeHash(str);
    cout << hash << endl;
    return 0;
}

IGPIGP · 07.11.2018, 09:18

Сообщение от L0M

Надо в цикле брать из строки по 2 char'а (2 байта),

А где сказано что вопрос ограничен 8-битными символами? Я бы понял задание как приглашение работать с wchar_t и wstring. Дело не только в том, что китайцы тоже люди. Там и кирилица представлена по человечески. Упрощение алгоритма - бонус.

@cinekst_207 · 07.11.2018, 10:43 **[ТС]**

Я правильно понима, то код для 1го пункта же?

@L0M · 07.11.2018, 12:40

Сообщение от cinekst_207

Я правильно понима, то код для 1го пункта же?

Да. Вы привели свой вариант кода - я его подправил в соответствии со своим пониманием задачи.

Сообщение от IGPIGP

А где сказано что вопрос ограничен 8-битными символами?

См. п.1 задания: "Сложение двухбайтовых слов". В данном случае строка символов - это просто для удобства отладки. С таким же успехом это мог бы быть некий буфер с двоичными данными, заполненяемый на произвольную длину. И реальный тип данных, для которых вычисляется хеш, здесь не важен.

@cinekst_207 · 07.11.2018, 14:36 **[ТС]**

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

@L0M · 07.11.2018, 16:15

cinekst_207, я не знаю.

У вас, видимо, есть преподаватель, у него проконсультируйтесь.
А для начала погуглите алгоритмы, упомянутые в пп. 2 и 3, а заодно и коллизии при хешировании.

IGPIGP · 07.11.2018, 16:15

Сообщение от L0M

См. п.1 задания: "Сложение двухбайтовых слов".

Именно это я и смотрю.

Сообщение от L0M

В данном случае строка символов - это просто для удобства отладки.

Не очевидно.

@L0M · 07.11.2018, 17:07

Сообщение от IGPIGP

Цитата Сообщение от L0M
См. п.1 задания: "Сложение двухбайтовых слов".
Именно это я и смотрю.

Я не очень понимаю предмет дискуссии. Функции, которую я написал, вообще глубоко по барабану какие данные расположены по адресу key. Единственное ограничение - это нулевой байт, который является маркером конца данных. Не устраивает такое ограничение - добавьте в функцию второй параметр, который будет показывать длину данных в байтах, и поменяйте условие в while.

А на счёт wchar_t, wstring и национальных алфавитов...

Вы в курсе, что sizeof(wchar_t) are implementation-defined?
В вашей реализации компилятора на вашей ОС на вашем железе размер wchar_t какой? И какая из Юникодных кодировок в ваш wchar_t влезает? И почему вы обходите стороной utf8, символ в которой может занимать и 6 байт?
Вы под Виндой используете компилятор от Microsoft. Правильно? И свято верите, что размер wchar_t 2 байта. А Linux + gcc на том же железе считают, что размер wchar_t 4 байта.

А то, что "там и кириллица представлена по-человечески" - вопрос тот ещё. Тут как бы дело не только в таблице символов (cp866, cp1251, utf8, utf16 и т.п.), но и в поддержке этой таблицы со стороны как ОС, так и пользовательского ПО. В Винде это, традиционно, жопа.

Для разминки можете попробовать в консоли вывести кириллицу, представленную в программе как wide-char.

IGPIGP · 07.11.2018, 18:51

Сообщение от L0M

Я не очень понимаю предмет дискуссии.

Я тоже. То что Вы говорите о кодировках и локализациях имеет место быть. Более того, дело даже не в OS (хотя куда же без них). Сегодня 32-разрядные процессоры уже становятся раритетом и строки как массивы байтов для железа это предмет некоторой распаковки, так как побайтно уже никто и ничего не обрабатывает.
Тем не менее мы все тут свято верим в байтовый массив и си-строку. Именно эта вера возмутилась на именно двухбайтовое слово. Поэтому я и предположил широкосимвольные строки. Да, - под виндой. Потому, что преподы и студенты под ней (обычно). Я не берусь обсуждать, как о ни из под неё выглядывают, но факт есть факт. Иначе побайтово тоже неплохо было бы.
Что касается:

Сообщение от L0M

Вы под Виндой используете компилятор от Microsoft. Правильно?

То - да, но не совсем (кроме msvs есть codebloks + G++). На виртулке Ubuntu 16.04 и Qt + G++ amd64. На работе - чистая Ubuntu 16.04 и немного Qnx (на ряде устройств).

Сообщение от L0M

В Винде это, традиционно, жопа.

Если бы только. Эта фирма сильна именно своими традициями. Тут совершенно согласен.

@L0M · 08.11.2018, 01:13

Сообщение от IGPIGP

Именно эта вера возмутилась на именно двухбайтовое слово.

А вот как раз здесь я совершенно ни при чём

Во-первых, "слово" - оно всегда двухбайтовое (экзотические архитектуры не рассматриваем!). Это повелось ещё со времён, когда 16-битная архитектура процессоров пришла на смену 8-битной. И дожило до наших дней. В WinAPI дефайн WORD - это оно, СЛОВО: беззнаковое целое размером в 16 бит. А ещё есть дефайны DWORD - двойное слово - 32 бита и QWORD - четверное слово - 64 бита. Но вначале было слово.

Правда до слова был таки байт

Во-вторых, "двухбайтовое слово" - это цитата из задания ТС.

Сообщение от IGPIGP

Иначе побайтово тоже неплохо было бы.

Ну, в общем-то обычно и делают побайтово. А вот хеш наоборот, делают более длинный. 16 бит для хэша - это курам на смех.

Думаю (уверен), что такая формулировка задачи - плод воспалённой фантазии какого-то преподавателя, которому для 150 балбесов на потоке надо изобрести 150 разных задач примерно на одну тему. А на следующий год внести в них некоторое разнообразие, что бы осложнить копипасту следующему поколению. Препов, конечно, тоже можно понять... Но иногда встречаются такие перлы... Собственно за примерами далеко ходить не надо - достаточно пробежаться по темам этого раздела форума

IGPIGP · 08.11.2018, 09:12

Сообщение от L0M

Правда до слова был таки байт

Бедный Байт , вечно ему достаётся. Но если уж говорить о начале-таки, то сказано:
***
Вначале была бага,
И бага была у Бога,
И бага была - Бог.
. . .
До сих пор, кстати, самая мощная бага из всех сущих.

Сообщение от L0M

Ну, в общем-то обычно и делают побайтово.

О чём и речь.
Анекдот:
Едут по прерии два индейца - Большой и Малый. После длительного молчания тот который Большой (Абрам, безусловно), обвёл ещё раз грустным взглядом пустыню и говорит: -"Изя, но это же не переносимо!". Изя сурово и молчаливо кивнул в ответ.
Я тоже за то чтобы байт был один, в студенческих задачках с си-строками.

Сообщение от L0M

Думаю (уверен), что такая формулировка задачи - плод воспалённой фантазии какого-то преподавателя, которому для 150 балбесов на потоке надо изобрести 150 разных задач примерно на одну тему.

Именно.

@cinekst_207 · 08.11.2018, 16:01 **[ТС]**

L0M, вобщем спросил я у препода - ответил, что надо преобразовать слово в хэш, потом этот хэш прогнать через алгоритм середины квадрата, потом всё это добро полученное прогнать через алгоритм двойного хэширования.
Вот код с 1 -> 2 пунктами (создаём хэш для строк. ключа, потом преобразуется данный хэш в другой хэш через алгоритм сер. квадрата для целочисленного ключа):

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <ctime>
 
using namespace std;
/// Двухбайтовое слово :
union TwoBytes {
 
    char ch[2];
    unsigned short us;
};
/// Функция сдвига влево :
inline void rot_left(unsigned short &us) {
    us = (us & 0x8000 ? (us << 1) + 1 : us << 1);
}
/// Хэш-функция для строкового -> целочисленного ключа :
unsigned short makeHash(string key) {
 
    TwoBytes word;
    unsigned short hash = 0;
    size_t i = 0;
 
    while (key[i]) {
 
        word.ch[i % 2] = key[i];
 
        if (i % 2 == 1) {
 
            hash += word.us;
            rot_left(hash);
        }
 
        ++i;
    }
 
    if (i % 2 == 1) {
 
        word.ch[1] = '\0';
        hash += word.us;
        rot_left(hash);
    }
 
    srand(time(0));
 
    short temp_1 = hash, temp_2 = pow(hash, 2), l1 = 0, l2 = 0;
 
    while (temp_1) {
 
        temp_1 /= 10;
        l1++;
    }
 
    while (temp_2) {
 
        temp_2 /= 10;
        l2++;
    }
 
    if (l2 == l1 * 2)
        while (l1) { rot_left(hash = pow(hash, 2)); l1--; }
 
    else
        while (l1) { rot_left(hash = pow(hash, 2) * 10 + rand() % 9); l1--; }
 
    return hash;
}
/// Главная функция :
int main() {
    
    ifstream fin_line("a.txt", ios_base::in);
    /// Задание A :
    cout << "Task #1-2 :" << endl;
 
    string str;
    unsigned short hash = 0;
    int i = 1;
 
    while (!fin_line.eof()) {
 
        fin_line >> str;
        hash = makeHash(str);
        str.clear();
 
        cout << "Line #" << i << " -> hash-code: " << hash << endl;
 
        i++;
        hash = 0;
    }
 
    fin_line.close();
    hash = 0;
    i = 1;
    /// Задание X :
    system("pause");
    return 0;
}

Но чувствую, что что-то не правильно, ибо выдаёт почти везде одинаковый хэш:

@cinekst_207 · 08.11.2018, 16:09 **[ТС]**

Алгоритм середины квадрата трактуется примерно так : Он состоит в возведении значения ключа k в квадрат (результат должен получаться
двойной длины!) и вырезании нужного числа разрядов из середины квадрата с помощью
сдвига и маскирования бит. Алгоритм хорошо работает, если среди значений ключа не
слишком часто встречаются числа, содержащие много нулей слева или справа

@L0M · 09.11.2018, 00:36

Во-первых, не стоило пихать второй алгоритм в ту же функцию.

Во-вторых, вы дибо неправильно реализовали алгоритм середины квадрата, либо взяли какую-то странную трактовку. Лёгкле гугление дало два описания: чисто числовой (скорее всего это вам и надо) и позиционно-цифровой. Я сделал обе реализации.

Ещё в вашем коде есть неоднозначное место: исходные строки вы считываете через >>. Если из файла нужно считывать пословно, то всё правильно, если построчно, то надо так, как в моём варианте.

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <ctime>
 
using namespace std;
/// Двухбайтовое слово :
union TwoBytes {
 
    char ch[2];
    unsigned short us;
};
/// Функция сдвига влево :
inline void rot_left(unsigned short &us) {
    us = (us & 0x8000 ? (us << 1) + 1 : us << 1);
}
/// Хэш-функция для строкового ключа :
unsigned short makeHash(const string &key) {
 
    TwoBytes word;
    unsigned short hash = 0;
    size_t i = 0;
 
    while (key[i]) {
 
        word.ch[i % 2] = key[i];
 
        if (i % 2 == 1) {
 
            hash += word.us;
            rot_left(hash);
        }
 
        ++i;
    }
 
    if (i % 2 == 1) {
 
        word.ch[1] = '\0';
        hash += word.us;
        rot_left(hash);
    }
    return hash;
}
 
/// Хэш-функция для целочисленного ключа :
unsigned short  middleSquare(unsigned short num) {
    unsigned int square, inum = num;
    square = inum * inum;
    unsigned short result = (unsigned short)((square & 0xffff00) >> 8);
    //cout << inum << " -> " << result << endl;
    return result;
}
 
/// Хэш-функция для целочисленного ключа (позиционно-цифровой вариант):
unsigned short  middleSquare_lex(unsigned short num, size_t rounds = 5) {
    stringstream ss;
    unsigned int square, inum = num;
    while (rounds--) {
        square = inum * inum;
        ss.str("");
        ss.clear();
        ss << setw(10) << setfill('0') << square;
        //cout << inum << " -> " << ss.str() << endl;
        ss.str(ss.str().substr(3, 5));
        ss >> inum;
    }
    return (unsigned short)inum;
}
 
/// Главная функция :
int main() {
 
    ifstream fin_line("a.txt", ios_base::in);
    /// Задание A :
    cout << "Task #1-2 :" << endl;
 
    string str;
    unsigned short hash = 0;
    int i = 1;
 
    while (!fin_line.eof()) {
 
        //fin_line >> str;
        getline(fin_line, str);
        hash = middleSquare(makeHash(str));
 
        //cout << "[" << str << "]\n";
        cout << "Line #" << i << " -> hash-code: " << hash << endl;
 
        i++;
        hash = 0;
    }
 
    fin_line.close();
    hash = 0;
    i = 1;
    /// Задание X :
    //system("pause");
    return 0;
}

@cinekst_207 · 09.11.2018, 00:51 **[ТС]**

На счет пословно, да, он сказал, что надо пословно, иначе разрешение коллизий не будет иметь смысла, т.к. одинаковых строк (в нормальных текстах) не бывает

@L0M · 09.11.2018, 01:57

Но коллизия - это одинаковые хеши при разных ключах.

В данной реализации наличие коллизий будет обеспечивать малая длина хеша. Подайте на вход построчно текст, длиной более 65536 уникальных строк - и присутствие хотя бы одной коллизии будет обеспечено. Но конечно со словами проще, дешевле, доступнее.

IGPIGP · 10.11.2018, 09:33

Сообщение от L0M

В данной реализации наличие коллизий будет обеспечивать малая длина хеша

малая длина строк (если такие есть) - не менее а даже более существенна. Длина хеша как правило определяется типом данных для хеш-ключа. Для случая строк, не выгодно выбирать длинные хеши так как теряется смысл всей затей. Например, если для 30-байтовых строк выбрать 30-ти байтовые ключи, то получим те же строки (вид сбоку) + заморочки всё это вычислить. Это уже не хеширование а шифрование получится (если не терять однозначность). А вот короткие строки это сложно и простая хеш функция легко набирает много коллизий. Для двухбайтовых "символов" длина строк уменьшается.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@cinekst_207 7 / 7 / 5 Регистрация: 25.03.2018 Сообщений: 377
	07.11.2018, 10:43 [ТС]
	Я правильно понима, то код для 1го пункта же? 0

@cinekst_207 7 / 7 / 5 Регистрация: 25.03.2018 Сообщений: 377
	07.11.2018, 14:36 [ТС]
	L0M, а потом что нужно? Нужно написать отдельную хэш-функцию, которая вычисляет хэш для целоч. ключа? Т.е. могу быть два разных входных данных? И потом нужно одну из этих функций прогнать через двойное хэширование? 0

@L0M Мозгоправ 1745 / 1039 / 468 Регистрация: 01.10.2018 Сообщений: 2,138 Записей в блоге: 2
	07.11.2018, 16:15
	cinekst_207, я не знаю. У вас, видимо, есть преподаватель, у него проконсультируйтесь. А для начала погуглите алгоритмы, упомянутые в пп. 2 и 3, а заодно и коллизии при хешировании. 0

@cinekst_207 7 / 7 / 5 Регистрация: 25.03.2018 Сообщений: 377
	08.11.2018, 16:09 [ТС]
	Алгоритм середины квадрата трактуется примерно так : Он состоит в возведении значения ключа k в квадрат (результат должен получаться двойной длины!) и вырезании нужного числа разрядов из середины квадрата с помощью сдвига и маскирования бит. Алгоритм хорошо работает, если среди значений ключа не слишком часто встречаются числа, содержащие много нулей слева или справа 0

@cinekst_207 7 / 7 / 5 Регистрация: 25.03.2018 Сообщений: 377
	09.11.2018, 00:51 [ТС]
	На счет пословно, да, он сказал, что надо пословно, иначе разрешение коллизий не будет иметь смысла, т.к. одинаковых строк (в нормальных текстах) не бывает 0

@L0M Мозгоправ 1745 / 1039 / 468 Регистрация: 01.10.2018 Сообщений: 2,138 Записей в блоге: 2
	09.11.2018, 01:57
	Но коллизия - это одинаковые хеши при разных ключах. В данной реализации наличие коллизий будет обеспечивать малая длина хеша. Подайте на вход построчно текст, длиной более 65536 уникальных строк - и присутствие хотя бы одной коллизии будет обеспечено. Но конечно со словами проще, дешевле, доступнее. 2

Хэширование

Решение