Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.65/31: Рейтинг темы: голосов - 31, средняя оценка - 4.65
insideone
Модератор
Автор FAQ
3659 / 939 / 112
Регистрация: 10.01.2010
Сообщений: 2,527
1

hash строк

16.01.2010, 17:36. Просмотров 5578. Ответов 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
Нужно получить из строки sha256 - hmac - base64 Проверяю через:...

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

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

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

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

Ну и вопрос на всякий случай: а стОит оно того? Если у тебя несколько сотен различных строк, то не проще ли забить соответствие в массив, отсортировать и дальше искать бинарным поиском?
1
insideone
Модератор
Автор FAQ
3659 / 939 / 112
Регистрация: 10.01.2010
Сообщений: 2,527
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
Эксперт С++
2913 / 1262 / 114
Регистрация: 27.05.2008
Сообщений: 3,464
16.01.2010, 18:44 4
"Все уже украдено до нас!" (с)
У тебя написано class - стало быть, это C++. Что мешает использовать boost ? Там есть и эффективные (скоростные и отлаженные!) хешированные контейнеры, и готовые генераторы хешей.....
1
Evg
Эксперт CАвтор FAQ
19314 / 7169 / 533
Регистрация: 30.03.2009
Сообщений: 20,061
Записей в блоге: 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
3659 / 939 / 112
Регистрация: 10.01.2010
Сообщений: 2,527
16.01.2010, 18:52  [ТС] 6
Цитата Сообщение от CheshireCat Посмотреть сообщение
"Все уже украдено до нас!" (с)
У тебя написано class - стало быть, это C++. Что мешает использовать boost ? Там есть и эффективные (скоростные и отлаженные!) хешированные контейнеры, и готовые генераторы хешей.....
А оттуда точно можно их "изъять" без головомучительного трехгодового изучения запутаных мануалов на китайском?) Мне просто не нравится принцип по типу "нужно пройти одну остановку поэтому купим (украдем) вертолет") А вообще спасибо попробую, хотя интереснее самому реализовать, своё оно дороже, да и опыт. Кодю "для себя". В смысле самосовершенствуюсь.

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

Не по теме:

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

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

Да не суть, какое лучше. Это же зависит от того, что за строки. Имена переменных - одно, полные пути файлов - другое, интернетовские ссылки - третье. Просто экспериментальным путём можно прогнать несколько разных значений и выявить то, которое даёт наиболее ровное распределение в твоём случае
0
insideone
Модератор
Автор FAQ
3659 / 939 / 112
Регистрация: 10.01.2010
Сообщений: 2,527
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
Эксперт С++
2913 / 1262 / 114
Регистрация: 27.05.2008
Сообщений: 3,464
16.01.2010, 21:42 11
Цитата Сообщение от insideone Посмотреть сообщение
А оттуда точно можно их "изъять" без головомучительного трехгодового изучения запутаных мануалов на китайском?)
Вот как раз буст (как, впрочем, и STL) - вещь весьма нетривиальная в дизайне и внутреннем устройстве, но - очень и очень простая в использовании. Примерно как современный автомобиль - весьма сложно устроен "под капотом", но достаточно сесть, повернуть ключ и нажать газ......
Что же касается "изъять" - так в дистрибутив буста входит и специальная утилита bcp, которая автоматически извлекает из недр буста нужный тебе заголовок и все его зависимости впридачу.
1
Evg
Эксперт CАвтор FAQ
19314 / 7169 / 533
Регистрация: 30.03.2009
Сообщений: 20,061
Записей в блоге: 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
3659 / 939 / 112
Регистрация: 10.01.2010
Сообщений: 2,527
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
19314 / 7169 / 533
Регистрация: 30.03.2009
Сообщений: 20,061
Записей в блоге: 30
17.01.2010, 00:26 14
Если изменить тип процедуры с uint32_t на uint16_t, то отрежутся старшие части. Если такое не канает, то можно просто взять и выкинуть каждый чётный (или нечётный) бит и уплотнить оставшиеся 16 бит
0
insideone
Модератор
Автор FAQ
3659 / 939 / 112
Регистрация: 10.01.2010
Сообщений: 2,527
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
19314 / 7169 / 533
Регистрация: 30.03.2009
Сообщений: 20,061
Записей в блоге: 30
17.01.2010, 10:49 16
Ты бы для начала опробовал простые методы. Если они дадут хороший результат - зачем изврящаться с сложными?
0
insideone
Модератор
Автор FAQ
3659 / 939 / 112
Регистрация: 10.01.2010
Сообщений: 2,527
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
19314 / 7169 / 533
Регистрация: 30.03.2009
Сообщений: 20,061
Записей в блоге: 30
19.01.2010, 22:13 18
Я в Си++ не силён, так что создай лучше отдельную тему. Ну или может кто-то из знающих сюда заглянет
0
insideone
Модератор
Автор FAQ
3659 / 939 / 112
Регистрация: 10.01.2010
Сообщений: 2,527
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
alexanderwdark
109 / 95 / 8
Регистрация: 19.02.2009
Сообщений: 312
16.08.2010, 14:16 20
Здесь можно найти простые, быстрые и понятные алгоритмы хэширования строк - в сравнении с тестированием на разных текстах.
0
16.08.2010, 14:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.08.2010, 14:16

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

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

Ucoz hash pass to phpbb hash pass
в ucoz выглядит так пароль: $1$d9gE$qArqNHo6j6jBcey9gGCkZ. в phpbb:...


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

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

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