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

C++

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

hash строк - C++

16.01.2010, 17:36. Просмотров 5007. Ответов 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;
    }
};
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Evg
Эксперт CАвтор FAQ
17387 / 5625 / 351
Регистрация: 30.03.2009
Сообщений: 15,407
Записей в блоге: 26
16.01.2010, 18:17     hash строк #2
А нельзя просто посчитать сумму байтов, из которых состоит строка и сделать её по модулю x (тогда результат будет в диапазоне от 0 до x). Как вариант из каждого байта ещё вычесть 32 (что соответствует пробелу), чтобы не пропадал диапазон начальных символов, которые не используются. Делаешь такую тупую реализацию, а потом проверяешь, насколько равномерно оно улеглось

Ну и вопрос на всякий случай: а стОит оно того? Если у тебя несколько сотен различных строк, то не проще ли забить соответствие в массив, отсортировать и дальше искать бинарным поиском?
insideone
Модератор
Автор FAQ
3636 / 914 / 49
Регистрация: 10.01.2010
Сообщений: 2,464
16.01.2010, 18:31  [ТС]     hash строк #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
Мне кажется тогда для строк "АБ" и "БА" будут выдаваться одинаковые значения, хм...
CheshireCat
Эксперт С++
2891 / 1240 / 78
Регистрация: 27.05.2008
Сообщений: 3,340
16.01.2010, 18:44     hash строк #4
"Все уже украдено до нас!" (с)
У тебя написано class - стало быть, это C++. Что мешает использовать boost ? Там есть и эффективные (скоростные и отлаженные!) хешированные контейнеры, и готовые генераторы хешей.....
Evg
Эксперт CАвтор FAQ
17387 / 5625 / 351
Регистрация: 30.03.2009
Сообщений: 15,407
Записей в блоге: 26
16.01.2010, 18:51     hash строк #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 дают хорошее распределение
insideone
Модератор
Автор FAQ
3636 / 914 / 49
Регистрация: 10.01.2010
Сообщений: 2,464
16.01.2010, 18:52  [ТС]     hash строк #6
Цитата Сообщение от CheshireCat Посмотреть сообщение
"Все уже украдено до нас!" (с)
У тебя написано class - стало быть, это C++. Что мешает использовать boost ? Там есть и эффективные (скоростные и отлаженные!) хешированные контейнеры, и готовые генераторы хешей.....
А оттуда точно можно их "изъять" без головомучительного трехгодового изучения запутаных мануалов на китайском?) Мне просто не нравится принцип по типу "нужно пройти одну остановку поэтому купим (украдем) вертолет") А вообще спасибо попробую, хотя интереснее самому реализовать, своё оно дороже, да и опыт. Кодю "для себя". В смысле самосовершенствуюсь.

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

Не по теме:

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

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

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

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

Добавлено через 40 минут
Нашёл вот такую интересную вещь ещё http://www.azillionmonkeys.com/qed/hash.html
Чтобы она возвращала unsigned short нужно сделать с результатом ^ (sizeof(unsigned short int)*8)?
CheshireCat
Эксперт С++
2891 / 1240 / 78
Регистрация: 27.05.2008
Сообщений: 3,340
16.01.2010, 21:42     hash строк #11
Цитата Сообщение от insideone Посмотреть сообщение
А оттуда точно можно их "изъять" без головомучительного трехгодового изучения запутаных мануалов на китайском?)
Вот как раз буст (как, впрочем, и STL) - вещь весьма нетривиальная в дизайне и внутреннем устройстве, но - очень и очень простая в использовании. Примерно как современный автомобиль - весьма сложно устроен "под капотом", но достаточно сесть, повернуть ключ и нажать газ......
Что же касается "изъять" - так в дистрибутив буста входит и специальная утилита bcp, которая автоматически извлекает из недр буста нужный тебе заголовок и все его зависимости впридачу.
Evg
Эксперт CАвтор FAQ
17387 / 5625 / 351
Регистрация: 30.03.2009
Сообщений: 15,407
Записей в блоге: 26
16.01.2010, 23:58     hash строк #12
Цитата Сообщение от insideone Посмотреть сообщение
Нашёл вот такую интересную вещь ещё http://www.azillionmonkeys.com/qed/hash.html
Чтобы она возвращала unsigned short нужно сделать с результатом ^ (sizeof(unsigned short int)*8)?
Ссылка не работает, но если надо, то нужно просто тип результата unsigned short поставить - компилятор автоматом всё приведёт
insideone
Модератор
Автор FAQ
3636 / 914 / 49
Регистрация: 10.01.2010
Сообщений: 2,464
17.01.2010, 00:11  [ТС]     hash строк #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 раза быстрее, и относительно других тоже... и ваще типа самая быстрая)
А если указать тип результата то наверное просто лишние биты обрежутся? мне нужно сжать большее число в меньшее число... хм
Evg
Эксперт CАвтор FAQ
17387 / 5625 / 351
Регистрация: 30.03.2009
Сообщений: 15,407
Записей в блоге: 26
17.01.2010, 00:26     hash строк #14
Если изменить тип процедуры с uint32_t на uint16_t, то отрежутся старшие части. Если такое не канает, то можно просто взять и выкинуть каждый чётный (или нечётный) бит и уплотнить оставшиеся 16 бит
insideone
Модератор
Автор FAQ
3636 / 914 / 49
Регистрация: 10.01.2010
Сообщений: 2,464
17.01.2010, 01:15  [ТС]     hash строк #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 младших бит
}
Главное я думаю преобразовать строку в число с учетом не только какие там символа находятся но и с их позицией и длинной строки. Вскоре что нибудь скомбинирую. Ах и ещё интересно, что же если входные данные слишком большие то при возведении в квадрат на выходе получим совсем не квадрат. Интересно это так надо или стоит выделить локальную переменную с длинной побольше
Evg
Эксперт CАвтор FAQ
17387 / 5625 / 351
Регистрация: 30.03.2009
Сообщений: 15,407
Записей в блоге: 26
17.01.2010, 10:49     hash строк #16
Ты бы для начала опробовал простые методы. Если они дадут хороший результат - зачем изврящаться с сложными?
insideone
Модератор
Автор FAQ
3636 / 914 / 49
Регистрация: 10.01.2010
Сообщений: 2,464
19.01.2010, 21:44  [ТС]     hash строк #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*. Возможно ли?
Evg
Эксперт CАвтор FAQ
17387 / 5625 / 351
Регистрация: 30.03.2009
Сообщений: 15,407
Записей в блоге: 26
19.01.2010, 22:13     hash строк #18
Я в Си++ не силён, так что создай лучше отдельную тему. Ну или может кто-то из знающих сюда заглянет
insideone
Модератор
Автор FAQ
3636 / 914 / 49
Регистрация: 10.01.2010
Сообщений: 2,464
20.01.2010, 00:19  [ТС]     hash строк #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();
То все ОК...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.08.2010, 14:16     hash строк
Еще ссылки по теме:

Std::hash<.> C++
Консольный HASH под *nix C++
C++ WinAPI MD5 Hash посредством WinApi
Error C2338: The C++ Standard doesn't provide a hash for this type C++
Получить hash C++ Builder

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

Или воспользуйтесь поиском по форуму:
alexanderwdark
109 / 95 / 1
Регистрация: 19.02.2009
Сообщений: 312
16.08.2010, 14:16     hash строк #20
Здесь можно найти простые, быстрые и понятные алгоритмы хэширования строк - в сравнении с тестированием на разных текстах.
Yandex
Объявления
16.08.2010, 14:16     hash строк
Ответ Создать тему
Опции темы

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