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

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

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

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

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

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

Хэш функции C++
C++ хэш-функция
C++ Списки (Помогите плиз)
Помогите студенту плиз C++
подкоректируйте прогу плиз) C++
C++ Хэш таблица
C++ Растолкуйте new с адресацией!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
23.08.2011, 13:43     растолкуйте про хэш плиз #2
AzaKendler, Да. Можно. Почему нет то?
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 13:51  [ТС]     растолкуйте про хэш плиз #3
ForEveR, просто не улавливаю. остаток от деления ЛЮБОГО числа на размер вектора - даст индекс не выходящий за размер?
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
23.08.2011, 14:02     растолкуйте про хэш плиз #4
AzaKendler, Размер вектора 100.
Найдите мне такое число, которое при остатке от деления на 100 даст больше 99 или же отрицательный результат
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:13  [ТС]     растолкуйте про хэш плиз #5
да. пока не удалось подобрать такое число. прошелся парой циклов . ну а что делать. если так не дошло.
Спасибо!
fasked
23.08.2011, 14:14
  #6

Не по теме:

Цитата Сообщение от AzaKendler Посмотреть сообщение
да. пока не удалось подобрать такое число. прошелся парой циклов. ну а что делать. если так не дошло.
Главное, что в итоге дошло

AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:15  [ТС]     растолкуйте про хэш плиз #7
fasked,
diagon
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.08.2011, 14:18     растолкуйте про хэш плиз #8
Цитата Сообщение от ForEveR Посмотреть сообщение
Найдите мне такое число, которое при остатке от деления на 100 даст больше 99 или же отрицательный результат
C
1
2
3
4
5
6
7
diagon@shadeware:~$ cat test.cpp && gcc test.cpp && ./a.out
#include <cstdio>
main(){
    printf("%d\n", (-2) % 100);
}
-2
diagon@shadeware:~$
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
23.08.2011, 14:19     растолкуйте про хэш плиз #9
diagon, Браво) Забыл упомянуть, что неотрицательное)
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:20  [ТС]     растолкуйте про хэш плиз #10
это так и это биг мак.
Так что в итоге то? Можно выскочить за вектор?
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
23.08.2011, 14:20     растолкуйте про хэш плиз #11
Цитата Сообщение от ForEveR Посмотреть сообщение
AzaKendler, Размер вектора 100.
Найдите мне такое число, которое при остатке от деления на 100 даст больше 99 или же отрицательный результат
Если строго математически, то остаток НИКОГДА не может быть отрицательным. Поэтому все остатки при делении на 100 лежат во множестве {0,1,...,99}
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
23.08.2011, 14:22     растолкуйте про хэш плиз #12
Функцию hash в студию!
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:25  [ТС]     растолкуйте про хэш плиз #13
Olga_, а ето что? printf("%d\n", (-2) % 100);

Добавлено через 21 секунду
ForEveR, ок. дочитаю да места где он ее расписывает, что то пока нету ее.
Т.е. вся надежда на нее, получается.
остатком от деления не защитится, это я и хотел узнать

Добавлено через 1 минуту
diagon, спасибо 2 раза.
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
23.08.2011, 14:26     растолкуйте про хэш плиз #14
Цитата Сообщение от AzaKendler Посмотреть сообщение
Olga_, а ето что? printf("%d\n", (-2) % 100);
Сказано же "строго математически", в математике нет отрицательных остатков, это гарантирует единственное разложение числа по модулю другого.
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:27  [ТС]     растолкуйте про хэш плиз #15
Olga_, да, Ольга. спасибо. Просто я не понял сразу
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
23.08.2011, 14:28     растолкуйте про хэш плиз #16
Цитата Сообщение от ForEveR Посмотреть сообщение
Функцию hash в студию!
Ну а зачем? Переменная i имеет тип size_type и он беззнаковый. Следовательно:
Код
-105 % 100 = 5
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:30  [ТС]     растолкуйте про хэш плиз #17
fasked, а черт. три раза спасибо. Вот уж невнимательность.
Т.е. в данном конкретном случае гарантия уже есть. это тип переменной.
Но в общем случае полагаться на остаток от деления нельзя.
ТАК?
diagon
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.08.2011, 14:34     растолкуйте про хэш плиз #18
Можно abs'ом подстраховаться...
C++
1
abs( -2 % 100 );
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 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 (или что-то в этом роде) => выйти за предел нереально.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2011, 14:35     растолкуйте про хэш плиз
Еще ссылки по теме:

C++ Растолкуйте код
C++ На Дваче анон поднял хитрый пример на тему ++i, растолкуйте мне, гики, а то я так ничего и не понял
C++ Case в switch и вообще растолкуйте за код
Растолкуйте почему выводится единица C++
Растолкуйте строчку из вики о фабричном методе C++

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

Или воспользуйтесь поиском по форуму:
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:35  [ТС]     растолкуйте про хэш плиз #20
ForEveR, 91 вышло. студия 10. виндовс соответственно.
Yandex
Объявления
23.08.2011, 14:35     растолкуйте про хэш плиз
Ответ Создать тему
Опции темы

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