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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Sick2
14 / 14 / 1
Регистрация: 26.11.2010
Сообщений: 235
10.05.2011, 22:54     Хэш-таблица, ошибка #1
Всем добрый день. Нужна помощь. За основу взять ПРИМЕР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++ Хэш таблица
Хэш-таблица C++
C++ Хэш-таблица
Телефонная книжка и хэш-таблица C++
Хэш-таблица C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
10.05.2011, 22:58     Хэш-таблица, ошибка #2
Цитата Сообщение от Sick2 Посмотреть сообщение
Так, конечно бред, но хоть запускается, но когда я ввожу элементы, они видимо не записываются, короче ничего не происходит.
С такой функцией хэш всегда равен либо нулю, либо единице. Думаю это причина (или как минимум одна из них), по которой не происходит ничего.
Sick2
14 / 14 / 1
Регистрация: 26.11.2010
Сообщений: 235
10.05.2011, 23:18  [ТС]     Хэш-таблица, ошибка #3
Ну это понятно, я же перевожу в инт. Так что неправильно написано? Ну, если смотреть на условие. Сказано же ведь просто изменить хэш-функцию =\
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
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
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
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++ Хэш таблица
Хэш - таблица методом цепочек C++
Высокопроизводительная хэш-таблица C++

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

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

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