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

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

15 ответов

46 просмотров

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Господа, а что сейчас вообще с рынком труда на делфи происходит? Какова ситуация?
Rꙮman Yankꙮvsky
29
А вообще, что может смущать в самой Julia - бы сказал, что нет единого стандартного подхода по многим моментам, поэтому многое выглядит как "хаки" и произвол. Короче говоря, с...
Viktor G.
2
30500 за редактор? )
Владимир
47
а через ESC-код ?
Alexey Kulakov
29
Чёт не понял, я ж правильной функцией воспользовался чтобы вывести отладочную информацию? но что-то она не ловится
notme
18
У меня есть функция где происходит это: write_bit(buffer, 1); write_bit(buffer, 0); write_bit(buffer, 1); write_bit(buffer, 1); write_bit(buffer, 1); w...
~
14
Добрый день! Скажите пожалуйста, а какие программы вы бы рекомендовали написать для того, чтобы научиться управлять памятью? Можно написать динамический массив, можно связный ...
Филипп
7
Недавно Google Project Zero нашёл багу в SQLite с помощью LLM, о чём достаточно было шумно в определённых интернетах, которые сопровождались рассказами, что скоро всех "ибешни...
Alex Sherbakov
5
Ребят в СИ можно реализовать ООП?
Николай
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
Карта сайта