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

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 40, средняя оценка - 4.95
insideone
Модератор
Автор FAQ
3652 / 932 / 54
Регистрация: 10.01.2010
Сообщений: 2,499
#1

hash строк - C++

16.01.2010, 17:36. Просмотров 5389. Ответов 23
Метки нет (Все метки)

Доброго времени суток! =)
Зачем: Для игры понадобилась база данных стандартных строк типа как данные для удобного перевода (всмысле весь текст вне игры). Чтобы в коде было удобнее обращаться к строкам хотелось бы ввести простые имена вида D12.S10 который допустим будет указывать на то что строка будет для диалога 12 и это будет 10 реплика. Это только пример и впринципе эти простые имена будут очень разные. Но чтобы обратиться к элементам массива строк нужен числовой индекс (иначе - смещение). В качестве этого индекса я буду использовать число возвращаемого из массива key в котором по индексу возвращаемого хэшем хранится реальный индекс где число лежит. Все это демонстрируется кодом:
C++
1
2
3
4
5
6
7
8
9
class DataBase {
    char* data[32676];
    unsigned short key[32676];
public:
    char* operator[] (char* strKey){
        return data[key[_hash(strKey)]];
    }
/* а также другие */
}
Вопрос: как написать функцию которая возвращает число в промежутке [0,x] исхода из входной строки. В общем как сделать правильно hash для строк и чтобы поменьше коллизий

Пока я написал что то вроде того, но помоему плохо очень
C++
1
2
3
4
5
6
7
8
9
10
11
12
    unsigned short _hash(char* hashed){
        unsigned short int seed = 0;
        unsigned short int temp = 0;
        while ( (*hashed) != NULL )
        {
            memcpy(&temp, hashed, sizeof(char));
            seed += temp;
            hashed++;
        }
    return strlen(hashed)+seed;
    }
};
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2010, 17:36
Я подобрал для вас темы с готовыми решениями и ответами на вопрос hash строк (C++):

Самая длинная общая подпоследовательность строк/ НОП строк (Динамическое программирование) - C++
Доброго времени суток. Помогите пожалуйста разобраться с алгоритмом НОП строк. Суть алгоритма. Необходимо найти самую длительную...

Получить hash - C++ Builder
Нужно получить из строки sha256 - hmac - base64 Проверяю через: quickhash.com Но у меня почему то не сходится. std::string...

Таблица строк - определить количество строк, TStringGrid - C++ Builder
Как определить количество строк, не содержащих ни одного нулевого элемента в TStringGrid (таблица строк)? Так чтобы при нажатии на...

MD5 Hash посредством WinApi - C++ WinAPI
Добрый день. Нужна помощь по крипто апи. Мне нужно зашифровать строку данных, делаю я это таким образом: #include "stdafx.h" ...

Hash+++ - C++
Скажите пожалуйста где скачать Hash subj и Hash on coure it

Std::hash<.> - C++
а для чего конкретно он применяется? читал на с++/reference, не особо понял...

23
Evg
Эксперт CАвтор FAQ
18885 / 6841 / 498
Регистрация: 30.03.2009
Сообщений: 19,270
Записей в блоге: 30
16.01.2010, 18:17 #2
А нельзя просто посчитать сумму байтов, из которых состоит строка и сделать её по модулю x (тогда результат будет в диапазоне от 0 до x). Как вариант из каждого байта ещё вычесть 32 (что соответствует пробелу), чтобы не пропадал диапазон начальных символов, которые не используются. Делаешь такую тупую реализацию, а потом проверяешь, насколько равномерно оно улеглось

Ну и вопрос на всякий случай: а стОит оно того? Если у тебя несколько сотен различных строк, то не проще ли забить соответствие в массив, отсортировать и дальше искать бинарным поиском?
1
insideone
Модератор
Автор FAQ
3652 / 932 / 54
Регистрация: 10.01.2010
Сообщений: 2,499
16.01.2010, 18:31  [ТС] #3
Скорее всего строк будет много. С другой стороны если их много вероятность коллизии ключа строки возрастает... просто мне хочется предпочесть скорость последующего обращения к строкам, пожертвовав небольшим количеством памяти. Если использовать поиск скорость обращения упадет. Хм, даже не знаю... не думаю что на много.
В общем я щас попробовал CRC вроде разные числа выдает
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    unsigned short _hash(char* hashed){
        unsigned short crc = 0xFFFF;
        unsigned char i;
        unsigned char len = strlen(hashed);
     
        while( len-- )
        {
            crc ^= *hashed++ << 8;
     
            for( i = 0; i < 8; i++ )
            crc = crc & 0x8000 ? ( crc << 1 ) ^ 0x1021 : crc << 1;
        }
        return crc;
    }
А нельзя просто посчитать сумму байтов, из которых состоит строка и сделать её по модулю x
Мне кажется тогда для строк "АБ" и "БА" будут выдаваться одинаковые значения, хм...
0
CheshireCat
Эксперт С++
2903 / 1252 / 81
Регистрация: 27.05.2008
Сообщений: 3,437
16.01.2010, 18:44 #4
"Все уже украдено до нас!" (с)
У тебя написано class - стало быть, это C++. Что мешает использовать boost ? Там есть и эффективные (скоростные и отлаженные!) хешированные контейнеры, и готовые генераторы хешей.....
1
Evg
Эксперт CАвтор FAQ
18885 / 6841 / 498
Регистрация: 30.03.2009
Сообщений: 19,270
Записей в блоге: 30
16.01.2010, 18:51 #5
> Скорее всего строк будет много

Тут главное не количество строк, а количество РАЗНЫХ строк

> Мне кажется тогда для строк "АБ" и "БА" будут выдаваться одинаковые значения, хм...

В книжке нашёл вот такой пример, ориентированный на строки

C
1
2
3
4
5
#define MULTIPLER 31
unsigned h = 0;
for (... по всем элементам строки)
  h = MULTIPLER * h + (unsigned char)str[i]; /* приводят к беззнаковому, чтобы итоговое число было положительное */
h = h % КОличество_элементов
Пишут, что эмпирически установленные значения 31 и 37 дают хорошее распределение
2
insideone
Модератор
Автор FAQ
3652 / 932 / 54
Регистрация: 10.01.2010
Сообщений: 2,499
16.01.2010, 18:52  [ТС] #6
Цитата Сообщение от CheshireCat Посмотреть сообщение
"Все уже украдено до нас!" (с)
У тебя написано class - стало быть, это C++. Что мешает использовать boost ? Там есть и эффективные (скоростные и отлаженные!) хешированные контейнеры, и готовые генераторы хешей.....
А оттуда точно можно их "изъять" без головомучительного трехгодового изучения запутаных мануалов на китайском?) Мне просто не нравится принцип по типу "нужно пройти одну остановку поэтому купим (украдем) вертолет") А вообще спасибо попробую, хотя интереснее самому реализовать, своё оно дороже, да и опыт. Кодю "для себя". В смысле самосовершенствуюсь.

Цитата Сообщение от Evg Посмотреть сообщение
В книжке нашёл вот такой пример, ориентированный на строки
Интересно, я обязательно попробую =)

Не по теме:

А я в какой то книжке читал что 42 лучше))

0
Evg
Эксперт CАвтор FAQ
18885 / 6841 / 498
Регистрация: 30.03.2009
Сообщений: 19,270
Записей в блоге: 30
16.01.2010, 18:56 #7
В посте 5 добавил последнюю строку в коде (а то пропустил)
0
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
16.01.2010, 18:59 #8
Цитата Сообщение от insideone Посмотреть сообщение
нужно пройти одну остановку поэтому купим (украдем) вертолет
в случае с бустом - вертолёт бесплатный. и летать на нём можно хоть до посинения.
0
Evg
Эксперт CАвтор FAQ
18885 / 6841 / 498
Регистрация: 30.03.2009
Сообщений: 19,270
Записей в блоге: 30
16.01.2010, 18:59 #9
> А я в какой то книжке читал что 42 лучше))

Да не суть, какое лучше. Это же зависит от того, что за строки. Имена переменных - одно, полные пути файлов - другое, интернетовские ссылки - третье. Просто экспериментальным путём можно прогнать несколько разных значений и выявить то, которое даёт наиболее ровное распределение в твоём случае
0
insideone
Модератор
Автор FAQ
3652 / 932 / 54
Регистрация: 10.01.2010
Сообщений: 2,499
16.01.2010, 19:53  [ТС] #10
Цитата Сообщение от zim22 Посмотреть сообщение
в случае с бустом - вертолёт бесплатный. и летать на нём можно хоть до посинения.
А топливо для вертолета, ремонтировать его... опятже ставить куда то надо)) Я в смысле зачем пушкой по мошкам) Ладно в любом случае я попробую потом посмотрим)

Да не суть, какое лучше. Это же зависит от того, что за строки.
Это была шутка =) Именно поэтому я пометил её как оффтоп. 42 число особое :-))

Добавлено через 40 минут
Нашёл вот такую интересную вещь ещё http://www.azillionmonkeys.com/qed/hash.html
Чтобы она возвращала unsigned short нужно сделать с результатом ^ (sizeof(unsigned short int)*8)?
0
CheshireCat
Эксперт С++
2903 / 1252 / 81
Регистрация: 27.05.2008
Сообщений: 3,437
16.01.2010, 21:42 #11
Цитата Сообщение от insideone Посмотреть сообщение
А оттуда точно можно их "изъять" без головомучительного трехгодового изучения запутаных мануалов на китайском?)
Вот как раз буст (как, впрочем, и STL) - вещь весьма нетривиальная в дизайне и внутреннем устройстве, но - очень и очень простая в использовании. Примерно как современный автомобиль - весьма сложно устроен "под капотом", но достаточно сесть, повернуть ключ и нажать газ......
Что же касается "изъять" - так в дистрибутив буста входит и специальная утилита bcp, которая автоматически извлекает из недр буста нужный тебе заголовок и все его зависимости впридачу.
1
Evg
Эксперт CАвтор FAQ
18885 / 6841 / 498
Регистрация: 30.03.2009
Сообщений: 19,270
Записей в блоге: 30
16.01.2010, 23:58 #12
Цитата Сообщение от insideone Посмотреть сообщение
Нашёл вот такую интересную вещь ещё http://www.azillionmonkeys.com/qed/hash.html
Чтобы она возвращала unsigned short нужно сделать с результатом ^ (sizeof(unsigned short int)*8)?
Ссылка не работает, но если надо, то нужно просто тип результата unsigned short поставить - компилятор автоматом всё приведёт
0
insideone
Модератор
Автор FAQ
3652 / 932 / 54
Регистрация: 10.01.2010
Сообщений: 2,499
17.01.2010, 00:11  [ТС] #13
Ссылка работала и работает) Впрочем неважно
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 "pstdint.h" /* Replace with <stdint.h> if appropriate */
#undef get16bits
#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
  || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
#define get16bits(d) (*((const uint16_t *) (d)))
#endif
 
#if !defined (get16bits)
#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                       +(uint32_t)(((const uint8_t *)(d))[0]) )
#endif
 
uint32_t SuperFastHash (const char * data, int len) {
uint32_t hash = len, tmp;
int rem;
 
    if (len <= 0 || data == NULL) return 0;
 
    rem = len & 3;
    len >>= 2;
 
    /* Main loop */
    for (;len > 0; len--) {
        hash  += get16bits (data);
        tmp    = (get16bits (data+2) << 11) ^ hash;
        hash   = (hash << 16) ^ tmp;
        data  += 2*sizeof (uint16_t);
        hash  += hash >> 11;
    }
 
    /* Handle end cases */
    switch (rem) {
        case 3: hash += get16bits (data);
                hash ^= hash << 16;
                hash ^= data[sizeof (uint16_t)] << 18;
                hash += hash >> 11;
                break;
        case 2: hash += get16bits (data);
                hash ^= hash << 11;
                hash += hash >> 17;
                break;
        case 1: hash += *data;
                hash ^= hash << 10;
                hash += hash >> 1;
    }
 
    /* Force "avalanching" of final 127 bits */
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;
 
    return hash;
}
Просто там типа тесты и показано что относительно CRC32 оно работает в 3-4 раза быстрее, и относительно других тоже... и ваще типа самая быстрая)
А если указать тип результата то наверное просто лишние биты обрежутся? мне нужно сжать большее число в меньшее число... хм
0
Evg
Эксперт CАвтор FAQ
18885 / 6841 / 498
Регистрация: 30.03.2009
Сообщений: 19,270
Записей в блоге: 30
17.01.2010, 00:26 #14
Если изменить тип процедуры с uint32_t на uint16_t, то отрежутся старшие части. Если такое не канает, то можно просто взять и выкинуть каждый чётный (или нечётный) бит и уплотнить оставшиеся 16 бит
0
insideone
Модератор
Автор FAQ
3652 / 932 / 54
Регистрация: 10.01.2010
Сообщений: 2,499
17.01.2010, 01:15  [ТС] #15
О, ещё понравилось вот это // источник http://rsdn.ru/article/alg/bintree/hash.xml
Метод середины квадрата (midsquare technique) предусматривает преобразование ключа в целое число, возведение его в квадрат и возвращение в качестве значения функции последовательности битов, извлеченных из середины полученного числа. Предположим, что ключ есть целое 32-битное число. Тогда следующая хеш-функция извлекает средние 10 бит возведенного в квадрат ключа.// возвратить средние 10 бит произведения key*key
C++
1
2
3
4
5
6
int HF(int key);
{
  key *= key;           // возвести ключ в квадрат
  key >>= 11;           // отбросить 11 младших бит
  return key % 1024     // возвратить 10 младших бит
}
Главное я думаю преобразовать строку в число с учетом не только какие там символа находятся но и с их позицией и длинной строки. Вскоре что нибудь скомбинирую. Ах и ещё интересно, что же если входные данные слишком большие то при возведении в квадрат на выходе получим совсем не квадрат. Интересно это так надо или стоит выделить локальную переменную с длинной побольше
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.01.2010, 01:15
Привет! Вот еще темы с ответами:

Hash - таблица - C++
Собственно всегда считал, что map - обычная хеш-таблица, оказалось нет, это какое-то древовидная упорядоченная хэш-таблица (без понятия,...

Ucoz hash pass to phpbb hash pass - phpBB
в ucoz выглядит так пароль: $1$d9gE$qArqNHo6j6jBcey9gGCkZ. в phpbb: $H$9NOBUC.KuIBSNJ8w4DRbrOsxqYxzyY. Как перенести пароль...

Hash tables - C (СИ)
Доброго времени суток, Подскажите пожалуйста, как разместить в ячейку таблицы( индекс известен), полученное слово, все слова должны быть...

Расшифровка hash - PHP
Подскажите, реально ли расшифровать функцию hash &quot;sha256&quot; есть код &lt;?php $day_hash =...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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