MB
Да, ты прав.
Size: a a a
2021 June 27
CD
а пункт (1) всегда можно перевести в среднее, если хеш адекватный (с плохим ничего не сделаешь, вроде логично)
CD
грубо говоря, можно запомнить случайное невырожденное преобразование хеша как вектора над (Z/2Z)^n, вроде после этого нельзя подделать входные данные
MB
Ну а если нам не повезло и хэш от всех входных строк тупо 0?
Может надо не хэши преобразовывать, а именно входные данные?
Может надо не хэши преобразовывать, а именно входные данные?
CD
для строк можно тоже случайную хеш-функцию синтезировать, если проблема возможна на этом уровне
CD
ну или криптографические, с ними понятно
CD
это вроде общая закономерность - особенный худший случай почему-то всегда можно сделать случайным :)
K
хэш на то и хэш, чтобы быть разным от разных строк.
CD
только либо он криптографический, либо можно подделать множество строк на коллизию :)
K
в хэш мапу конечно передаётся хэш, который потом примерно hash%size_buffer
MB
Хэш принимает конечный набор значений, а строк бесконечное множество.
K
если в мапе слишком много вещей в одну и ту же ячейку попадают, то мапа производит рехеш, чтобы более равномерно положить элементы
K
они равномерно распределяться по этому набору значений. А значений там ого го
MB
Я не пытаюсь утверждать, что такие сильные коллизии встречаются хоть сколько-нибудь частно (там явно какая-то экспоненциально затухающая вероятность будет).
Но этого факта вроде достаточно, чтобы решение вышеописанной задачи через хэш-таблицу не работало за линию в худшем случае.
Но этого факта вроде достаточно, чтобы решение вышеописанной задачи через хэш-таблицу не работало за линию в худшем случае.
K
если тебе нужно ещё больше значений - придумываешь хэш с большим диапазоном значений
ГР
типа вставка n пользователей типа (userN, emailN) будет проходит за линейное время от n?
K
я уж не знаю как в джаве, а в С++ есть такой метод reserve у хэш мапы, который тебе гарантирует что реаллокаций не будет и ты вставишь всё за линейное время
MB
Не вдаваясь в частности, да.
K
если ты конечно знаешь количество элементов
ГР
проверил линейно добавляет.
а в общем случае с n пользователей m элементов
"Запихни email в мапу, где ключ - email а значение - юзер. В конце просто переложи это в мапу, где ключ - юзер, а значение - список адресов."
не понял,
1. если email повториться то в первой мапе пользователь просто перезапишется,
2. как их "просто" переложить
а в общем случае с n пользователей m элементов
"Запихни email в мапу, где ключ - email а значение - юзер. В конце просто переложи это в мапу, где ключ - юзер, а значение - список адресов."
не понял,
1. если email повториться то в первой мапе пользователь просто перезапишется,
2. как их "просто" переложить