170 похожих чатов

Перехеширование? Это зачем?

15 ответов

31 просмотр

Ну при большом числе коллизий же мапы перехэшируются, верно?

Alex- Автор вопроса

Я, конечно, глубоко в исходники не лазил, но давай подумаем логически, что такое коллизия?

Получение одинаковых хэшей при разных ключах. Из за чего данные попадают в одну и ту же корзину, что приводит со временем к обращению к ним за O(n)

Alex- Автор вопроса
Павлик Ливаткин
Получение одинаковых хэшей при разных ключах. Из з...

вот, какой смысл брать еще раз хеш от этих значений, если оно всё равно выдаст тот же результат? :)

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

Хэш это же общее название. Понятно что он начинает браться по другому алгоритму или с другим сидом или с другой солью. Или как там назвать. Это и называется перехэширование

Alex- Автор вопроса
Павлик Ливаткин
Хэш это же общее название. Понятно что он начинает...

вам, кажется, надо перечитать работу хмапа (ну или мне) 😁

Павлик Ливаткин
Хэш это же общее название. Понятно что он начинает...

Нет такого, алгоритм не меняется, соль не добавляется.

Alex
вам, кажется, надо перечитать работу хмапа (ну или...

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

Pavel
Нет такого, алгоритм не меняется, соль не добавляе...

А если коллизий много... Работа мапы в го будет замедляться вплоть до О(n)? Я правильно понимаю? Или с этим как то борятся?

Павлик Ливаткин
Ну замечание законное, я на го относительно не дав...

А в каких языках предусмотрен алгоритм "перехэширования"?

Alex- Автор вопроса
Павлик Ливаткин
Ну замечание законное, я на го относительно не дав...

ну я в принципе не могу представить себе поведение, чтобы это могло понадобиться

Павлик Ливаткин
А если коллизий много... Работа мапы в го будет за...

Ну если у тебя абсолютно все хэши в мапе одинаковые, то будет O(n), если не ошибаюсь, но сам представь шанс всего этого. К тому же хэшфункция оптимизирована под каждый тип данных, чтобы максимально избегать коллизии

Pavel
Ну если у тебя абсолютно все хэши в мапе одинаковы...

Ну я щас попробую на вопросы ответить по очереди А на счёт шансов что много совпадений будет - так это отчасти вопрос сколько я туда запихаю На счёт того что оптимизация под стандартные типы данных - у меня тип мой собственный, из трёх int и bool. Подозреваю что это внутри превращается в []byte и дальше уже идёт хэш

Павлик Ливаткин
Ну я щас попробую на вопросы ответить по очереди ...

Ну я не знаю сколько должно быть значений в мапе, чтобы получить кучу коллизий до такой степени, чтобы взятие линейное стало. Если интересно как углублено мапа работает, то советую посмотреть видео Николая Тузова на эту тему

Alex
Я, конечно, глубоко в исходники не лазил, но давай...

очевидно в данном контексте это когда для разных значений ключа получается одно значение хэша. на практике коллизий избежать невозможно например если у вас хэш имеет размер 32бита, а ключ - 64бита. так что это разговор ни о чем...

Похожие вопросы

Обсуждают сегодня

30500 за редактор? )
Владимир
47
Недавно Google Project Zero нашёл багу в SQLite с помощью LLM, о чём достаточно было шумно в определённых интернетах, которые сопровождались рассказами, что скоро всех "ибешни...
Alex Sherbakov
5
вы делали что-то подобное и как? может есть либы готовые? увидел картинку нокода, где всё линиями соединено и стало интересно попробовать то же в ddl на lua сделать. решил с ч...
Victor
8
Подскажите пожалуйста, как в CustomDrawCell(Sender: TcxCustomGridTableView; ACanvas: TcxCanvas; AViewInfo: TcxGridTableDataCellViewInfo; var ADone: Boolean); получить наз...
A Z
7
Ребят в СИ можно реализовать ООП?
Николай
33
https://github.com/erlang/otp/blob/OTP-27.1/lib/kernel/src/logger_h_common.erl#L174 https://github.com/erlang/otp/blob/OTP-27.1/lib/kernel/src/logger_olp.erl#L76 15 лет назад...
Maksim Lapshin
20
Как передать управляющий символ в открытую через CreateProcess консоль? Собсна, есть процедура: procedure TRedirectThread.WriteData(Data: OEMString); var Written: Cardinal;...
Serjone
1
Он в одиночку это дело запилил или была какая-то команда?
Aquinary
12
~ 2m21s  nix shell github:nixos/nixpkgs#stack ~  stack ghc -- --version error: … while calling the 'derivationStrict' builtin at /builtin/derivation.nix:...
Rebuild your mind.
6
Всем привет, нужна как никогда, нужна помощь с IO в загрузчике. Пишу в code16 после установки сегментных регистров, пишу вывод символа. Пробовал 2 варианта: # 1 mov $0x0E, %a...
Shadow Akira
14
Карта сайта