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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Sick2
14 / 14 / 1
Регистрация: 26.11.2010
Сообщений: 235
#1

Хэш-таблица, ошибка - C++

10.05.2011, 22:54. Просмотров 1417. Ответов 7
Метки нет (Все метки)

Всем добрый день. Нужна помощь. За основу взять ПРИМЕР1 хэш-таблицы с прямой адресацией (разобраться с примером). Изменить функцию вычисления хэш на мультипликативный - H(key)=[hashTableSize(key*A mod 1)] , где key*A mod 1 –дробная часть key*A , A=(sqrt(5) - 1)/2 = 0.6180339887499
Вот пример:
C++
1
2
3
4
int HashFunction(int key,int size,int p)  //хэш-функция
{
return (p+key)%size;
}
Я изменил на то, что сказано:
C++
1
2
3
4
5
6
7
int HashFunction(int key)
{
    long double A;
    double m=5;
    A=(sqrt(m) - 1)/2;
    return (A*key)%1;
}
Но так оно выдаёт ошибку.
C++
1
2
3
4
5
6
7
int HashFunction(int key)
{
    long double A;
    double m=5;
    A=(sqrt(m) - 1)/2;
    return (int)(A*key)%1;
}
Так, конечно бред, но хоть запускается, но когда я ввожу элементы, они видимо не записываются, короче ничего не происходит.
Просьба помочь.

Добавлено через 6 часов 59 минут
помогите пожалуйста!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2011, 22:54     Хэш-таблица, ошибка
Посмотрите здесь:

Хэш-таблица - C++
Ребят, помогите, пожалуйста, решить задачу: Хэш-функция определена как h(k) = k mod 11. Вводится последовательность N натуральных...

Хэш таблица - C++
Подскажите, пожалуйста, как сделать хэш-таблицу в которой у каждого элемента есть шесть полей.(например Имя фамилия возраст...). Что бы...

Хэш-таблица - C++
Задание реализовать динамическую хеш-таблицу с открытой адресацией для хранения строк (операции вставки и поиска). Таблица должна...

Хэш таблица - C++
Как работает метод цепочек, для разрешения коллизий в хэш таблице?

Хэш-таблица - C++
Дана строка произвольного размера. Необходимо найти все повторяющиеся фрагменты максимальной длины. Для начала нужно создать хэш-таблицу...

Высокопроизводительная хэш-таблица - C++
Кто-нибудь знает проверенную в бою готовую реализацию высокопроизводительной хэш-таблицы или хотя бы материалы какие? Требования: ...

Хэш-таблица раздельные цепочки - C++
Итак, ключ 10 должен располагаться в списке по адресу 0, ключ 11 – по адресу 1,… ключ 20 – по адресу 0. Ситуация, когда для разных ключей...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
10.05.2011, 22:58     Хэш-таблица, ошибка #2
Цитата Сообщение от Sick2 Посмотреть сообщение
Так, конечно бред, но хоть запускается, но когда я ввожу элементы, они видимо не записываются, короче ничего не происходит.
С такой функцией хэш всегда равен либо нулю, либо единице. Думаю это причина (или как минимум одна из них), по которой не происходит ничего.
Sick2
14 / 14 / 1
Регистрация: 26.11.2010
Сообщений: 235
10.05.2011, 23:18  [ТС]     Хэш-таблица, ошибка #3
Ну это понятно, я же перевожу в инт. Так что неправильно написано? Ну, если смотреть на условие. Сказано же ведь просто изменить хэш-функцию =\
ValeryLaptev
Эксперт С++
1039 / 818 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
10.05.2011, 23:21     Хэш-таблица, ошибка #4
Цитата Сообщение от Sick2 Посмотреть сообщение
Всем добрый день. Нужна помощь. За основу взять ПРИМЕР1 хэш-таблицы с прямой адресацией (разобраться с примером). Изменить функцию вычисления хэш на мультипликативный - H(key)=[hashTableSize(key*A mod 1)] , где key*A mod 1 –дробная часть key*A , A=(sqrt(5) - 1)/2 = 0.6180339887499
Вот пример:
C++
1
2
3
4
int HashFunction(int key,int size,int p)  //хэш-функция
{
return (p+key)%size;
}
Эта штука хорошо работает, если size - простое число.
Я изменил на то, что сказано:
C++
1
2
3
4
5
6
7
int HashFunction(int key)
{
    long double A;
    double m=5;
    A=(sqrt(m) - 1)/2;
    return (A*key)%1;
}
Но так оно выдаёт ошибку.
Естественно!
1. А - вещественное, поэтому A*key - вещественное. Операция % - остаток от деления - применима только к целым.
2. Как ты себе представляешь остаток от деления на 1?
C++
1
2
3
4
5
6
7
int HashFunction(int key)
{
    long double A;
    double m=5;
    A=(sqrt(m) - 1)/2;
    return (int)(A*key)%1;
}
Так, конечно бред, но хоть запускается, но когда я ввожу элементы, они видимо не записываются, короче ничего не происходит.
Что-то нафигачил ты совсем не то, что написано.
H(key)=[hashTableSize(key*A mod 1)] , где key*A mod 1 –дробная часть key*A
Это совсем не то, что у тебя написано!
Надо умножить размер таблицы size на дробную часть (A*key) и взять целую часть от произведения.
Sick2
14 / 14 / 1
Регистрация: 26.11.2010
Сообщений: 235
11.05.2011, 00:29  [ТС]     Хэш-таблица, ошибка #5
Спасибо, но как тогда взять дробную часть от (A*key)?
ValeryLaptev
Эксперт С++
1039 / 818 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
11.05.2011, 00:38     Хэш-таблица, ошибка #6
C++
1
A*key - floor(A*key)
Sick2
14 / 14 / 1
Регистрация: 26.11.2010
Сообщений: 235
11.05.2011, 00:43  [ТС]     Хэш-таблица, ошибка #7
C++
1
2
3
4
5
6
7
8
9
int HashFunction(int key,int size,int p) 
{
    double m=5;
    double A=(sqrt(m) - 1)/2;
    double z=A*key;
    z-=(int)z;
 
return (int)(size*z);
}
?!
Спасибо. А так, как у меня правильно? Или геморно слишком?
Всё работает, и так, и так как у меня. Спасибо за помощь. Я почему-то даже не подумал, что hashTableSize - это и есть size таблицы Ещё раз огромное спасибо)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.05.2011, 00:50     Хэш-таблица, ошибка
Еще ссылки по теме:

Хэш-таблица (метод цепочек) - C++
Пишу частотный словарь текста: Массив списков узлов. В узле значение и частота слова. При написании функции void add столкнулся с...

Телефонная книжка и хэш-таблица - C++
Ребят, помогите кто может! Мне нужно реализовать телефонную книжку в виде хэш-таблицы. ХТ реализую через классы(сначала класс односвязного...

Хэш-таблица. Метод цепочек. C++ - C++
Уважаемые, программисты, задание звучит так: "Таблица строится по методу цепочек с использованием хеш-функции, возвращающей сумму двух...

Хэш - таблица методом цепочек - C++
Всем привет! Есть задание реализовать хеш-таблицу методом цепочек + с хэш - функциями: деление и умножение. Я не до конца понимаю, что...

Что такое Хэш таблица с открытой адресацией - C++
Здраствуйте у меня такой вопрос то такое Хэш таблица с открытой адресацией хеш функция что должно храниться в структуре как осуществляется...


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

Или воспользуйтесь поиском по форуму:
ValeryLaptev
Эксперт С++
1039 / 818 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
11.05.2011, 00:50     Хэш-таблица, ошибка #8
Так тоже работает. Но более корректно вместо преобразования типа вызвать floor()
Yandex
Объявления
11.05.2011, 00:50     Хэш-таблица, ошибка
Ответ Создать тему
Опции темы

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