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

C++

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

hash строк - C++

16.01.2010, 17:36. Просмотров 5090. Ответов 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, не особо понял...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Evg
Эксперт CАвтор FAQ
17802 / 6008 / 387
Регистрация: 30.03.2009
Сообщений: 16,511
Записей в блоге: 26
17.01.2010, 10:49 #16
Ты бы для начала опробовал простые методы. Если они дадут хороший результат - зачем изврящаться с сложными?
0
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
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
17802 / 6008 / 387
Регистрация: 30.03.2009
Сообщений: 16,511
Записей в блоге: 26
19.01.2010, 22:13 #18
Я в Си++ не силён, так что создай лучше отдельную тему. Ну или может кто-то из знающих сюда заглянет
0
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
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 / 1
Регистрация: 19.02.2009
Сообщений: 312
16.08.2010, 14:16 #20
Здесь можно найти простые, быстрые и понятные алгоритмы хэширования строк - в сравнении с тестированием на разных текстах.
0
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
16.08.2010, 21:12 #21
insideone, когда-то проводили статистическое исследование простеньких (32 бита) хэш-функций и CRC32 показала не самые хорошие результаты. а вот такая вот оказалась вполне приемлимой, количество коллизий у нее было минимально:
C
1
2
3
4
5
6
7
8
9
10
11
unsigned int ROT13Hash (char *str, unsigned int len)
{
    unsigned int hash = 0;
    unsigned int i = 0;
 
    for (i = 0; i < len; str++, i++) {
        hash += (unsigned char)(*str);
        hash -= (hash << 13) | (hash >> 19);
    }
    return hash;
}
Цитата Сообщение от insideone Посмотреть сообщение
Чтобы она возвращала unsigned short нужно сделать с результатом ^ (sizeof(unsigned short int)*8)?
применение битовых операций никак не может уменьшить/увеличить количество бит в результате.
0
alexanderwdark
109 / 95 / 1
Регистрация: 19.02.2009
Сообщений: 312
17.08.2010, 10:02 #22
rot13 в моих тестах показала хорошие результаты, но не лучшие - твердый середнячок (правда с не очень большим отрывом от лидеров по основным тестам). Правда при такой простоте конструкции - это уже более чем хорошие результаты.

У crc32 есть неотъемлемый плюс - это стабильность. У этой функции не сильных "всплесков" на сложных наборах текстов при сравнительно небольшом числе коллизий (середнячок).

Смотрите таблички по моей ссылке в более раннем посте - там есть столбец среднее "число коллизий"

Там же есть и архив с исходниками хэш-функций.
0
Black Fregat
1381 / 1011 / 222
Регистрация: 31.05.2009
Сообщений: 4,240
17.08.2010, 10:18 #23
А еще есть совершенно простые Флетчер и Адлер (модификация Флетчера).
Адлер есть в Zlib (он там используется, но есть и отдельной функцией).
0
alexanderwdark
109 / 95 / 1
Регистрация: 19.02.2009
Сообщений: 312
17.08.2010, 10:22 #24
Цитата Сообщение от Black Fregat Посмотреть сообщение
А еще есть совершенно простые Флетчер и Адлер (модификация Флетчера).
Адлер есть в Zlib (он там используется, но есть и отдельной функцией).

У них очень много коллизий на строках (небольших массивах)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.08.2010, 10:22
Привет! Вот еще темы с ответами:

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 =...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
17.08.2010, 10:22
Ответ Создать тему
Опции темы

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