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

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

Восстановить пароль Регистрация
 
 
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 13:33     растолкуйте про хэш плиз #1
на картинке реализация поиска в "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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.08.2011, 13:43     растолкуйте про хэш плиз #2
AzaKendler, Да. Можно. Почему нет то?
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 13:51  [ТС]     растолкуйте про хэш плиз #3
ForEveR, просто не улавливаю. остаток от деления ЛЮБОГО числа на размер вектора - даст индекс не выходящий за размер?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.08.2011, 14:02     растолкуйте про хэш плиз #4
AzaKendler, Размер вектора 100.
Найдите мне такое число, которое при остатке от деления на 100 даст больше 99 или же отрицательный результат
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:13  [ТС]     растолкуйте про хэш плиз #5
да. пока не удалось подобрать такое число. прошелся парой циклов . ну а что делать. если так не дошло.
Спасибо!
fasked
23.08.2011, 14:14
  #6

Не по теме:

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

AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:15  [ТС]     растолкуйте про хэш плиз #7
fasked,
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.08.2011, 14:19     растолкуйте про хэш плиз #9
diagon, Браво) Забыл упомянуть, что неотрицательное)
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:20  [ТС]     растолкуйте про хэш плиз #10
это так и это биг мак.
Так что в итоге то? Можно выскочить за вектор?
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
23.08.2011, 14:20     растолкуйте про хэш плиз #11
Цитата Сообщение от ForEveR Посмотреть сообщение
AzaKendler, Размер вектора 100.
Найдите мне такое число, которое при остатке от деления на 100 даст больше 99 или же отрицательный результат
Если строго математически, то остаток НИКОГДА не может быть отрицательным. Поэтому все остатки при делении на 100 лежат во множестве {0,1,...,99}
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.08.2011, 14:22     растолкуйте про хэш плиз #12
Функцию hash в студию!
AzaKendler
 Аватар для 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_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
23.08.2011, 14:26     растолкуйте про хэш плиз #14
Цитата Сообщение от AzaKendler Посмотреть сообщение
Olga_, а ето что? printf("%d\n", (-2) % 100);
Сказано же "строго математически", в математике нет отрицательных остатков, это гарантирует единственное разложение числа по модулю другого.
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:27  [ТС]     растолкуйте про хэш плиз #15
Olga_, да, Ольга. спасибо. Просто я не понял сразу
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
23.08.2011, 14:28     растолкуйте про хэш плиз #16
Цитата Сообщение от ForEveR Посмотреть сообщение
Функцию hash в студию!
Ну а зачем? Переменная i имеет тип size_type и он беззнаковый. Следовательно:
Код
-105 % 100 = 5
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
23.08.2011, 14:30  [ТС]     растолкуйте про хэш плиз #17
fasked, а черт. три раза спасибо. Вот уж невнимательность.
Т.е. в данном конкретном случае гарантия уже есть. это тип переменной.
Но в общем случае полагаться на остаток от деления нельзя.
ТАК?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.08.2011, 14:34     растолкуйте про хэш плиз #18
Можно abs'ом подстраховаться...
C++
1
abs( -2 % 100 );
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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++ Растолкуйте new с адресацией!
C++ Растолкуйте код

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

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

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