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

@AzaKendler · Регистрация: 30.05.2011

Студворк — интернет-сервис помощи студентам

на картинке реализация поиска в "hash_map" от Страуструпа. И все бы хорошо если бы не один момент.
b и v это векторы. И доступ по индексу в векторе [] ассоциируется у меня с чем то упорядоченным, например [0], [5] и тд. а строка

C++
1
set_type i = hash(K)%b.size()

- какое значение дает i? можно ли гарантировать применив остаток от деления hash(k) на размер вектора, в качестве индекса, что мы не выйдем за пределы вектора в какую либо сторону?

@ForEveR · 23.08.2011, 13:43

AzaKendler, Да. Можно. Почему нет то?

@AzaKendler · 23.08.2011, 13:51 **[ТС]**

ForEveR, просто не улавливаю. остаток от деления ЛЮБОГО числа на размер вектора - даст индекс не выходящий за размер?

@ForEveR · 23.08.2011, 14:02

AzaKendler, Размер вектора 100.
Найдите мне такое число, которое при остатке от деления на 100 даст больше 99 или же отрицательный результат

@AzaKendler · 23.08.2011, 14:13 **[ТС]**

да. пока не удалось подобрать такое число. прошелся парой циклов . ну а что делать. если так не дошло.
Спасибо!

@fasked · 23.08.2011, 14:14

Не по теме:

Сообщение от AzaKendler

да. пока не удалось подобрать такое число. прошелся парой циклов. ну а что делать. если так не дошло.

Главное, что в итоге дошло :)

@AzaKendler · 23.08.2011, 14:15 **[ТС]**

fasked,

@diagon · 23.08.2011, 14:18

Сообщение от 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 · 23.08.2011, 14:19

diagon, Браво) Забыл упомянуть, что неотрицательное)

@AzaKendler · 23.08.2011, 14:20 **[ТС]**

это так и это биг мак.
Так что в итоге то? Можно выскочить за вектор?

@Olga_ · 23.08.2011, 14:20

Сообщение от ForEveR

AzaKendler, Размер вектора 100.
Найдите мне такое число, которое при остатке от деления на 100 даст больше 99 или же отрицательный результат

Если строго математически, то остаток НИКОГДА не может быть отрицательным. Поэтому все остатки при делении на 100 лежат во множестве {0,1,...,99}

@ForEveR · 23.08.2011, 14:22

Функцию hash в студию!

@AzaKendler · 23.08.2011, 14:25 **[ТС]**

Olga_, а ето что? printf("%d\n", (-2) % 100);

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

Добавлено через 1 минуту
diagon, спасибо 2 раза.

@Olga_ · 23.08.2011, 14:26

Сообщение от AzaKendler

Olga_, а ето что? printf("%d\n", (-2) % 100);

Сказано же "строго математически", в математике нет отрицательных остатков, это гарантирует единственное разложение числа по модулю другого.

@AzaKendler · 23.08.2011, 14:27 **[ТС]**

Olga_, да, Ольга. спасибо. Просто я не понял сразу

@fasked · 23.08.2011, 14:28

Сообщение от ForEveR

Функцию hash в студию!

Ну а зачем? Переменная i имеет тип size_type и он беззнаковый. Следовательно:

Code
1
-105 % 100 = 5

@AzaKendler · 23.08.2011, 14:30 **[ТС]**

fasked,

а черт. три раза спасибо. Вот уж невнимательность.
Т.е. в данном конкретном случае гарантия уже есть. это тип переменной.
Но в общем случае полагаться на остаток от деления нельзя.
ТАК?

@diagon · 23.08.2011, 14:34

Можно abs'ом подстраховаться...

C++
1
abs( -2 % 100 );

@ForEveR · 23.08.2011, 14:34

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 (или что-то в этом роде) => выйти за предел нереально.

@AzaKendler · 23.08.2011, 14:35 **[ТС]**

ForEveR, 91 вышло. студия 10. виндовс соответственно.

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	23.08.2011, 13:43
	AzaKendler, Да. Можно. Почему нет то? 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	23.08.2011, 13:51 [ТС]
	ForEveR, просто не улавливаю. остаток от деления ЛЮБОГО числа на размер вектора - даст индекс не выходящий за размер? 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	23.08.2011, 14:02
	AzaKendler, Размер вектора 100. Найдите мне такое число, которое при остатке от деления на 100 даст больше 99 или же отрицательный результат 2

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	23.08.2011, 14:13 [ТС]
	да. пока не удалось подобрать такое число. прошелся парой циклов . ну а что делать. если так не дошло. Спасибо! 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	23.08.2011, 14:15 [ТС]
	fasked, 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	23.08.2011, 14:19
	diagon, Браво) Забыл упомянуть, что неотрицательное) 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	23.08.2011, 14:20 [ТС]
	это так и это биг мак. Так что в итоге то? Можно выскочить за вектор? 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	23.08.2011, 14:22
	Функцию hash в студию! 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	23.08.2011, 14:25 [ТС]
	Olga_, а ето что? printf("%d\n", (-2) % 100); Добавлено через 21 секунду ForEveR, ок. дочитаю да места где он ее расписывает, что то пока нету ее. Т.е. вся надежда на нее, получается. остатком от деления не защитится, это я и хотел узнать Добавлено через 1 минуту diagon, спасибо 2 раза. 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	23.08.2011, 14:27 [ТС]
	Olga_, да, Ольга. спасибо. Просто я не понял сразу 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	23.08.2011, 14:30 [ТС]
	fasked, а черт. три раза спасибо. Вот уж невнимательность. Т.е. в данном конкретном случае гарантия уже есть. это тип переменной. Но в общем случае полагаться на остаток от деления нельзя. ТАК? 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	23.08.2011, 14:35 [ТС]
	ForEveR, 91 вышло. студия 10. виндовс соответственно. 0