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

PERFECT HASH FUNCTION - C++

Восстановить пароль Регистрация
 
Warezovvv
 Аватар для Warezovvv
9 / 9 / 2
Регистрация: 09.12.2012
Сообщений: 219
28.10.2013, 00:56     PERFECT HASH FUNCTION #1
Вопрос таков, подскажите хэш функцию:
формат AcccAA- где A-заглавные буквы,c-цифры.
всего 1500 сегментов.
Мин сумма символов 339 и макс 441.
Т.Е. если мы будем складывать в тупую аски коды каждого из символов то получится что все они лягут в 339<ТУТ<441?
что означает что коллизий будет OVER9000.
C++
1
2
3
4
5
int HashFunc(string key){
        int    Adress = (key[0] + key[1] + key[2] + key[3] + key[4] + key[5]);
 
        return Adress;
    }
Пока она такая ,но хочется что бы элементы ложились от 0<ТУТ<1499

Добавлено через 1 час 41 минуту
UPPPPP
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
28.10.2013, 01:21     PERFECT HASH FUNCTION #2
Цитата Сообщение от Warezovvv Посмотреть сообщение
но хочется что бы элементы ложились от 0<ТУТ<1499
Непонятная фраза.

Без коллизий -- умножением.
Если у вас латинский алфавит, то у вас 26 вариантов заглавной буквы и 10 вариантов цифр.
Итого 26 * 10 * 10 * 10 * 26 * 26 = 17576000.
В четыре байта влезет.
Warezovvv
 Аватар для Warezovvv
9 / 9 / 2
Регистрация: 09.12.2012
Сообщений: 219
28.10.2013, 01:50  [ТС]     PERFECT HASH FUNCTION #3
C++
1
2
3
4
5
6
7
int address = key[0] + 
              31 * key[1] + 
              137 * key[2] + 
              1571 * key[3] + 
              11047 * key[4] + 
              77813 * key[5];
return address % kNumBuckets;
Лично я сделал так. может кому поможет
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
28.10.2013, 10:31     PERFECT HASH FUNCTION #4
Ваша функция явно предполагает, что int состоит из четырех байт, потому что в два байта число 77813 уже не лезет. Почему-б тогда не сделать хэширующую функцию без коллизий!?

А кто такой kNumBuckets? Если это "количество корзин" в каком-либо хранилище, использующем хэши, то ему не место в хэширующей функции.
Yandex
Объявления
28.10.2013, 10:31     PERFECT HASH FUNCTION
Ответ Создать тему
Опции темы

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