Хеш таблицы. Часть 6. Открытая адресация, линейное пробирование, двойное хеширование.

Хеш таблицы. Часть 6. Открытая адресация, линейное пробирование, двойное хеширование.
Хотите начать программировать?
обучение для начинающих - • программирование для н...
питон для начинающих - • python для младенцев
ВЫ МОЖЕТЕ ПОДДЕРЖАТЬ ПРОЕКТ:
Яндекс кошелек:
410014557804280
money.yandex.ru/to/4100145578...
Webmoney:
R348962076583
Z840320799500
E301944634338
QIWI:
[phone]
Ваши пожертвования помогают мне уделять больше времени и сил для создания обучающих материалов.

[@SerhiiZhydel]

Ооо, прям отличное обьяснение! Спасибо большое!)

[@user-yt6vv9vf3x]

Пригодилось. Спасибо)

[@user-sd3dk6xr5z]

Извините, но мне кажеться, что при вычислении индекса хеш-функией, нужно делить на 5, а не на 4, поскольку элементов всего 5, а 4 - это индекс последнего. Если я не ошибаюсь, в хеш-функии даного типа делить надо на общее количество элементов хеш-таблицы.

[@R1d3rrr]

Такой вопрос. У этого метода просто хеш-таблица существует и все? Ну вот в методе цепочек, там каждой ячейке соответствует конкретно двусвязный список. Там мы просто через хеш-функцию h(k) определяем ячейку и добавляем, например в голову списка новое значение v. Таким образом мы сузили длину нашей хеш-таблицы, но как бы увеличили ее вширь. А тут? Здесь просто хеш-таблица, в каждой ячейке которой может лежать лишь одно значение? И если хеш-таблица переполняется, то выбрасывается ошибка? Но тогда же не решается проблема 1. Ну как бы решается конечно, но тупо через костыль "извините, таблица закончилась". Я верно понял?

[@EvgeniyMalov]

как правило в реализациях при полном заполнении таблицы или пересечении какого то процента ее заполненности, создается новая таблица удвоенного размера и происходит полный перенос всех элементов в эту таблицу.

[@R1d3rrr]

Ааа понял. Спасибо))

[@takiekakmi7532]

Капец, такая крутая тема и всего 4к просмотров🤦‍♂️

[@CommandAndConquerGeneralPaulus]

Евгений, в этом примере у Вас длина массива 5, а не 4. Следовательно не 5 mod 4 = 1, а 5 mod 5 = 0, и так далее. В предыдущих видео где Вы вели нумерацию ячеек массива от 1 до n, длина массива действительно была n. В данном случаи n+1. PS спасибо за Ваши видео уроки. Учу Java по Хорстману и Вы его не плохо дополнили по этой теме, ну а он в свою очередь дополнил Вас. Например, если б Вы в предыдущем уроке упомянули о повторном хешировании, когда речь шла о факторе загрузки и определенном его значении, то у товарища global_silence вопросов бы не возникло.

[@yellow-leibl]

Павло, хеш-функция может быть любая, но в плане эффективности, конечно лучше брать mod5, но не обязательно

[@_settgaming]

@@yellow-leibl при чём здесь эффективность, с мод4 последняя ячейка массива останется навечно пустой

[@yellow-leibl]

@@_settgaming сообщению 2 года, но ты решил ответить, и… ты ошибся))) еще раз, функция может быть любая, то что последний элемент не заполнен, это не есть ошибка, тут он рассказывает про разрешение коллизий, потому что на практике ты не знаешь какого размера будет массив, так что это твоя ошибка и полное отсутствие представления доя чего нужна хеш таблица и как ее использовать

[@kromarty]

При линейном пробировании, если у меня саморасширяющаяся хеш таблица, как искать элементы? Тот алгоритм поиска уже не всегда будет работать

[@Epenckorn]

Короче, двойное хеширование - это метод, создающих больше дыр, чем затыкает.

[@user-dx7yy8rm5u]

как получили остаток от деления 5/4 = 1, если вы скажите 1,25, берем единицу, тогда 9/4 откуда 1??

[@webms4177]

Дело в том, что здесь используется не просто деление, а "mod", можете сами попробовать ввести в строку google "5 mod 4" или "9 mod 4" и вы получите ответ "1". Mod - это по сути количество единиц, которых нам не хватает, для того, чтобы числитель разделился нацело на знаменатель.