Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.53/49: Рейтинг темы: голосов - 49, средняя оценка - 4.53
Автор FAQ
3684 / 961 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
1

hash строк

16.01.2010, 17:36. Показов 8939. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.01.2010, 17:36
Ответы с готовыми решениями:

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

MD5 Hash посредством WinApi
Добрый день. Нужна помощь по крипто апи. Мне нужно зашифровать строку данных, делаю я это таким...

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

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

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

Ну и вопрос на всякий случай: а стОит оно того? Если у тебя несколько сотен различных строк, то не проще ли забить соответствие в массив, отсортировать и дальше искать бинарным поиском?
1
Автор FAQ
3684 / 961 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
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
Эксперт С++
2921 / 1270 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
16.01.2010, 18:44 4
"Все уже украдено до нас!" (с)
У тебя написано class - стало быть, это C++. Что мешает использовать boost ? Там есть и эффективные (скоростные и отлаженные!) хешированные контейнеры, и готовые генераторы хешей.....
1
Evg
Эксперт CАвтор FAQ
21204 / 8220 / 633
Регистрация: 30.03.2009
Сообщений: 22,538
Записей в блоге: 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 дают хорошее распределение
3
Автор FAQ
3684 / 961 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
16.01.2010, 18:52  [ТС] 6
Цитата Сообщение от CheshireCat Посмотреть сообщение
"Все уже украдено до нас!" (с)
У тебя написано class - стало быть, это C++. Что мешает использовать boost ? Там есть и эффективные (скоростные и отлаженные!) хешированные контейнеры, и готовые генераторы хешей.....
А оттуда точно можно их "изъять" без головомучительного трехгодового изучения запутаных мануалов на китайском?) Мне просто не нравится принцип по типу "нужно пройти одну остановку поэтому купим (украдем) вертолет") А вообще спасибо попробую, хотя интереснее самому реализовать, своё оно дороже, да и опыт. Кодю "для себя". В смысле самосовершенствуюсь.

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

Не по теме:

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

0
Evg
Эксперт CАвтор FAQ
21204 / 8220 / 633
Регистрация: 30.03.2009
Сообщений: 22,538
Записей в блоге: 30
16.01.2010, 18:56 7
В посте 5 добавил последнюю строку в коде (а то пропустил)
0
depict1
281 / 146 / 4
Регистрация: 11.07.2009
Сообщений: 606
16.01.2010, 18:59 8
Цитата Сообщение от insideone Посмотреть сообщение
нужно пройти одну остановку поэтому купим (украдем) вертолет
в случае с бустом - вертолёт бесплатный. и летать на нём можно хоть до посинения.
0
Evg
Эксперт CАвтор FAQ
21204 / 8220 / 633
Регистрация: 30.03.2009
Сообщений: 22,538
Записей в блоге: 30
16.01.2010, 18:59 9
> А я в какой то книжке читал что 42 лучше))

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

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

Добавлено через 40 минут
Нашёл вот такую интересную вещь ещё http://www.azillionmonkeys.com/qed/hash.html
Чтобы она возвращала unsigned short нужно сделать с результатом ^ (sizeof(unsigned short int)*8)?
0
Эксперт С++
2921 / 1270 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
16.01.2010, 21:42 11
Цитата Сообщение от insideone Посмотреть сообщение
А оттуда точно можно их "изъять" без головомучительного трехгодового изучения запутаных мануалов на китайском?)
Вот как раз буст (как, впрочем, и STL) - вещь весьма нетривиальная в дизайне и внутреннем устройстве, но - очень и очень простая в использовании. Примерно как современный автомобиль - весьма сложно устроен "под капотом", но достаточно сесть, повернуть ключ и нажать газ......
Что же касается "изъять" - так в дистрибутив буста входит и специальная утилита bcp, которая автоматически извлекает из недр буста нужный тебе заголовок и все его зависимости впридачу.
1
Evg
Эксперт CАвтор FAQ
21204 / 8220 / 633
Регистрация: 30.03.2009
Сообщений: 22,538
Записей в блоге: 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
Автор FAQ
3684 / 961 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
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
21204 / 8220 / 633
Регистрация: 30.03.2009
Сообщений: 22,538
Записей в блоге: 30
17.01.2010, 00:26 14
Если изменить тип процедуры с uint32_t на uint16_t, то отрежутся старшие части. Если такое не канает, то можно просто взять и выкинуть каждый чётный (или нечётный) бит и уплотнить оставшиеся 16 бит
0
Автор FAQ
3684 / 961 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
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
Evg
Эксперт CАвтор FAQ
21204 / 8220 / 633
Регистрация: 30.03.2009
Сообщений: 22,538
Записей в блоге: 30
17.01.2010, 10:49 16
Ты бы для начала опробовал простые методы. Если они дадут хороший результат - зачем изврящаться с сложными?
0
Автор FAQ
3684 / 961 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
19.01.2010, 21:44  [ТС] 17
C++
1
2
3
4
5
6
7
8
9
10
11
class StringGroup{
private:
    const char* data[HASH_MAX_LEN];
public:
    StringGroup();
    const char* operator[] (const char* newKey);
};
const char* StringGroup::operator[] (const char* StringKey){
    unsigned short int IntKey = Math::Hash(StringKey);
return data[IntKey];
}
Продвигаюсь, но...
C++
1
2
3
StringGroup Strings;
std::string Str = "abc";
Strings["any_key"] = new const char (Str.c_str());
В общем смысл чтобы динамически выделять память для базы строк для каждой строки.
К тому же Strings["any_key"] может использоваться в конктексте забора строки, так что она должна возвращать const char*. Возможно ли?
0
Evg
Эксперт CАвтор FAQ
21204 / 8220 / 633
Регистрация: 30.03.2009
Сообщений: 22,538
Записей в блоге: 30
19.01.2010, 22:13 18
Я в Си++ не силён, так что создай лучше отдельную тему. Ну или может кто-то из знающих сюда заглянет
0
Автор FAQ
3684 / 961 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
20.01.2010, 00:19  [ТС] 19
По смыслу мне надо вернуть ссылку на указатель char* но мне кажется это невозможно(( Создам пожалуй, если в ближайшее время сам не разберусь)

Добавлено через 40 минут
отлично, чтобы вернуть ссылку на указатель нужно написать так
const char*& operator[] (const char* newKey);
и все ОК =)

Добавлено через 26 минут
однако, как выделить возвращаемой ссылке память? мне нужно выделить память под const char [] а строку взять из std::string
т.е. нечто подобное
C++
1
Strings[KEYWORD.c_str()] = new char[](CURLINE.c_str());
Можно было бы выделить память а потом допустим туда записать (хотя опять же трудности есть), но... хотелось бы хранить в const char*

Добавлено через 44 минуты
Потерял надежду на const char* сделал так, однако после memcpy никакого толку нет.
C++
1
2
Strings[Key] = new char[len];
memcpy(&Strings[Key], CURLINE.c_str(), len);
Если писать
C++
1
2
Strings[Key] = "АБВГД";
Strings[Key] = CURLINE.c_str();
То все ОК...
0
109 / 95 / 8
Регистрация: 19.02.2009
Сообщений: 312
16.08.2010, 14:16 20
Здесь можно найти простые, быстрые и понятные алгоритмы хэширования строк - в сравнении с тестированием на разных текстах.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.08.2010, 14:16

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

PERFECT HASH FUNCTION
Вопрос таков, подскажите хэш функцию: формат AcccAA- где A-заглавные буквы,c-цифры. всего 1500...

Hash. Не получается написать хэш
В чем ошибка? Пишет: &quot;hash&quot; не является однозначным #include &lt;iostream&gt; #include &lt;string&gt;...

списки, вектора, map, Hash
интересует информация о следующих &quot;типах&quot; std::vector и std::deque Списки, деревья std::list,...


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

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

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