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

C++

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

hash строк - C++

16.01.2010, 17:36. Просмотров 5012. Ответов 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;
    }
};
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
16.08.2010, 21:12     hash строк #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)?
применение битовых операций никак не может уменьшить/увеличить количество бит в результате.
alexanderwdark
109 / 95 / 1
Регистрация: 19.02.2009
Сообщений: 312
17.08.2010, 10:02     hash строк #22
rot13 в моих тестах показала хорошие результаты, но не лучшие - твердый середнячок (правда с не очень большим отрывом от лидеров по основным тестам). Правда при такой простоте конструкции - это уже более чем хорошие результаты.

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

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

Там же есть и архив с исходниками хэш-функций.
Black Fregat
1362 / 992 / 215
Регистрация: 31.05.2009
Сообщений: 4,151
17.08.2010, 10:18     hash строк #23
А еще есть совершенно простые Флетчер и Адлер (модификация Флетчера).
Адлер есть в Zlib (он там используется, но есть и отдельной функцией).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.08.2010, 10:22     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
17.08.2010, 10:22     hash строк #24
Цитата Сообщение от Black Fregat Посмотреть сообщение
А еще есть совершенно простые Флетчер и Адлер (модификация Флетчера).
Адлер есть в Zlib (он там используется, но есть и отдельной функцией).

У них очень много коллизий на строках (небольших массивах)
Yandex
Объявления
17.08.2010, 10:22     hash строк
Ответ Создать тему
Опции темы

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