MF
спасибо
но он не стандартный
https://docs.rs/linked-hash-map/0.5.2/linked_hash_map/struct.LinkedHashMap.html
Size: a a a
2020 March 04
M
можно навернуть сверху стандартной мапы хранилище из нод, ссылающихся друг на друга
M
во, кто-то уже по факту уже сделал такое
P
во, кто-то уже по факту уже сделал такое
ну, это ж стандартное решение мапы с порядком
p
Чёт я не понимаю, какой там принцип хеширования юзается. Видимо я ещё мало про хеш-мапы знаю...
P
Чёт я не понимаю, какой там принцип хеширования юзается. Видимо я ещё мало про хеш-мапы знаю...
там передаётся хешер, вроде
P
а под капотом может юзать просто какой-то свой и пробегаться по структуре
P
Просто вот где-то недавно буквально читал о какой-то хешмапе на реддите, которая иначе хранит данные, что позволяет гарантировать порядок
ну и BTreeMap тоже гарантирует порядок, но не сохраняет порядок добавления
P
тоесть она сортированная
M
а под капотом может юзать просто какой-то свой и пробегаться по структуре
вряд ли можно придумать хэшер H(key, pos), который будет упорядочен по pos
P
вряд ли можно придумать хэшер H(key, pos), который будет упорядочен по pos
при чём тут хешер?
P
вот кусок из доки по реализации в джаве, например — список поверх мапы
https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/LinkedHashMap.java#L30-L39
https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/LinkedHashMap.java#L30-L39
M
Если у тебя ключ будет находится во множестве меньшем по мощности, чем мапа может размещать ключи в себе, то можно придумать схему хранения, когда бакеты будут располагаться в возрастающем порядке в зависимости от позиции вставки. Самый простой вырожденный случай - это массив.
P
Если у тебя ключ будет находится во множестве меньшем по мощности, чем мапа может размещать ключи в себе, то можно придумать схему хранения, когда бакеты будут располагаться в возрастающем порядке в зависимости от позиции вставки. Самый простой вырожденный случай - это массив.
и потерять весь перформанс хешмапы?
M
а, ну да, тогда каждая вставка - это коллизия
P
хешмапа на то и рассчитана, что у тебя множество ключей может быть больше, чем множество бакетов, чем ближе они, тем ниже перформанс
P
не, наоборот
P
перформанс выше, но память всю жрёт
мало бакетов — больше коллизий
много бакетов — больше памяти требуется
мало бакетов — больше коллизий
много бакетов — больше памяти требуется
M
можно еще использовать принцип хранения, который использует ImmutableMap из guava, в которой гарантируется такой же порядок итерирования, как при вставке в ImmutableMap.Builder