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

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

Войти
Регистрация
Восстановить пароль
 
 
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
#1

растолкуйте про хэш плиз - C++

23.08.2011, 13:33. Просмотров 915. Ответов 22
Метки нет (Все метки)

на картинке реализация поиска в "hash_map" от Страуструпа. И все бы хорошо если бы не один момент.
b и v это векторы. И доступ по индексу в векторе [] ассоциируется у меня с чем то упорядоченным, например [0], [5] и тд. а строка
C++
1
set_type i = hash(K)%b.size()
- какое значение дает i? можно ли гарантировать применив остаток от деления hash(k) на размер вектора, в качестве индекса, что мы не выйдем за пределы вектора в какую либо сторону?
0
Миниатюры
растолкуйте про хэш плиз  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2011, 13:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос растолкуйте про хэш плиз (C++):

Описать класс "хэш-таблица", используя unordered_set и заданную хэш-функцию - C++
Здравствуйте. Есть класс объектов и ключ сравнения: #pragma once #include <iostream> #include <vector> #include <list> #include...

Растолкуйте new с адресацией! - C++
Я так понимаю что это для избегания повторного выделения памяти? но до конца так и не понял. Спасибо откликнувшимся. Вот я...

Растолкуйте код - C++
Помогите с кодом cout << (i == 0 || j == 0 || i == N + 1 || j == M + 1 ? '#' : a) << (j <= M ? "" : "\n"); что делает cout << ( ? : ); я...

Растолкуйте почему выводится единица - C++
Почему выводит 1?? #include int main(int argc, char** argv) { int x = 0; int y = 0; if (x++ && y++) ...

Case в switch и вообще растолкуйте за код - C++
Объясните пожалуйста что имеет в виду Стаус 1)case'(':case')': 2) curr_tok=Token_Value(ch) это приведение к Token_Value? 3)чем по...

Растолкуйте строчку из вики о фабричном методе - C++
Слово "специфицировались" никак понять не могу. Также, не могу понять как это так, чтоб на создаваемые классом объекты влияли...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
23.08.2011, 14:28 #16
Цитата Сообщение от ForEveR Посмотреть сообщение
Функцию hash в студию!
Ну а зачем? Переменная i имеет тип size_type и он беззнаковый. Следовательно:
Код
-105 % 100 = 5
1
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:30  [ТС] #17
fasked, а черт. три раза спасибо. Вот уж невнимательность.
Т.е. в данном конкретном случае гарантия уже есть. это тип переменной.
Но в общем случае полагаться на остаток от деления нельзя.
ТАК?
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.08.2011, 14:34 #18
Можно abs'ом подстраховаться...
C++
1
abs( -2 % 100 );
1
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
23.08.2011, 14:34 #19
fasked, gcc с тобой не согласен...

C++
1
2
3
4
5
6
int main()
{
    std::size_t size = 100;
    std::size_t i = -105 % size;
    std::cout << i << '\n';
}
Но я дико подозреваю, что hash возвращает size_t (или что-то в этом роде) => выйти за предел нереально.
0
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:35  [ТС] #20
ForEveR, 91 вышло. студия 10. виндовс соответственно.
0
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
23.08.2011, 14:36 #21
Цитата Сообщение от AzaKendler Посмотреть сообщение
Т.е. в данном конкретном случае гарантия уже есть. это тип переменной.
Но в общем случае полагаться на остаток от деления нельзя.
ТАК?
Представим такой случай:
C++
1
vec[hash % v.size()] = 0;
Если переменная hash имеет беззнаковый тип, то гарантия есть. Если знаковый, то придется вставить дополнительную проверку. И, например, сделать вот так:
C++
1
vec[abs(hash) % v.size()] = 0;
Но, к слову говоря, хэш это как правило положительное число и хранить хэш в знаковом типе уже неправильно.
1
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:41  [ТС] #22
fasked, а в чем лучше хранить хэш, понимаю что про это надо отдельно читать и есть много инфы. но раз уж...

Добавлено через 1 минуту
Цитата Сообщение от AzaKendler Посмотреть сообщение
set_type
во блин написал.
0
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
23.08.2011, 14:43 #23
ForEveR, ну и пусть не соглашается, за пределы все равно не выйдет
а в чем лучше хранить хэш, понимаю что про это надо отдельно читать и есть много инфы. но раз уж...
Все зависит от функции, которая вычисляет хэш. Чаще всего хэш - это 32-битное значение, то есть подойдет unsigned int.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2011, 14:43
Привет! Вот еще темы с ответами:

На Дваче анон поднял хитрый пример на тему ++i, растолкуйте мне, гики, а то я так ничего и не понял - C++
Цитирую...

Про линковку библиотек и про архитектуру иерархии классов - C++
Добрый день! Возникла такая вот проблема. Я использую MinGW Developer Studio. Это довольно старая IDE, поддержка которой завершилась в 2005...

Помогите студенту плиз - C++
Было дано задание-&quot;Подобрать несколько примеров тем программных продуктов&quot;. Задание корявое, в следствии- на ум ничего вообще не приходит. ...

Списки (Помогите плиз) - C++
1)Линейный упорядоченный список с удалением,нахождением и вставкой элемента. 2)Список списков(список состоит из заголовков списков) ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.08.2011, 14:43
Ответ Создать тему
Опции темы

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