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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Warezovvv
 Аватар для Warezovvv
9 / 9 / 2
Регистрация: 09.12.2012
Сообщений: 219
#1

PERFECT HASH FUNCTION - C++

28.10.2013, 00:56. Просмотров 427. Ответов 3
Метки нет (Все метки)

Вопрос таков, подскажите хэш функцию:
формат 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.10.2013, 00:56     PERFECT HASH FUNCTION
Посмотрите здесь:

C++ C:\Dev-Cpp\lib\vector.h `ostream' is neither function nor member function; cannot be declared friend
C++ Что такое hash-таблицы, и зачем они нужны?
C++ Перегрузить операторы = и [] для hash
C++ списки, вектора, map, Hash
C++ multi-hash -массив с несколькими индексами
C++ Hash - таблица
Hash+++ C++
C++ function
Std::hash<.> C++
Консольный HASH под *nix C++
C++ Оптимизируется ли компилятором конструкция switch-case? Работа со строками через ID объекта или hash
Error C2338: The C++ Standard doesn't provide a hash for this type C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2915 / 1344 / 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
2915 / 1344 / 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
Ответ Создать тему
Опции темы

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