dm
В корзине, например, ещё связный список, и элементы ищутся по ключу через их реализацию equals
Я то понимаю, но мне интересно, какой длинны этот список и в чем опасность вообще самой коллизии?
Size: a a a
2021 March 19
E
Я то понимаю, но мне интересно, какой длинны этот список и в чем опасность вообще самой коллизии?
Коллизия это когда два ключа указывают на одну и ту же корзину. Хэш это как адрес дома и подъезд, при этом есть частные дома-коттеджи, где живет только один человек, и есть высотки, чтобы найти конкретного человека, тебе нужно ещё каждую квартиру обойти.
Длина списка зависит от эффективности хэш-функции и количества корзин
Длина списка зависит от эффективности хэш-функции и количества корзин
C
Я то понимаю, но мне интересно, какой длинны этот список и в чем опасность вообще самой коллизии?
Теоретически все твои ключи могут хэшкодиться одинаково, тогда все элементы попадут в одну корзину.
Коллизии ухудшают производительность, так как вместо супер быстрого выбора по ключу придётся перебирать по одному элементы в корзине.
Коллизии ухудшают производительность, так как вместо супер быстрого выбора по ключу придётся перебирать по одному элементы в корзине.
dm
Коллизия это когда два ключа указывают на одну и ту же корзину. Хэш это как адрес дома и подъезд, при этом есть частные дома-коттеджи, где живет только один человек, и есть высотки, чтобы найти конкретного человека, тебе нужно ещё каждую квартиру обойти.
Длина списка зависит от эффективности хэш-функции и количества корзин
Длина списка зависит от эффективности хэш-функции и количества корзин
Кажется начинает проясняться, стандартное количество корзин 16, но я хочу уточнить, когда кол-во корзин увеличивается? Когда в каждой из корзине хотяб по одному объекту? И что значит "длинна списка зависит от эффективности хэш-функции", я знаю что хеш Мара увеличивается и потом идёт перераспределение объектов через новый перерасчёт хэша объектов, но не до конца понял это, пояснить можно?
dm
Теоретически все твои ключи могут хэшкодиться одинаково, тогда все элементы попадут в одну корзину.
Коллизии ухудшают производительность, так как вместо супер быстрого выбора по ключу придётся перебирать по одному элементы в корзине.
Коллизии ухудшают производительность, так как вместо супер быстрого выбора по ключу придётся перебирать по одному элементы в корзине.
И все? ток из-за производительности? Я почему-то считал что есть опасности типо потери этих обьектов
C
Кажется начинает проясняться, стандартное количество корзин 16, но я хочу уточнить, когда кол-во корзин увеличивается? Когда в каждой из корзине хотяб по одному объекту? И что значит "длинна списка зависит от эффективности хэш-функции", я знаю что хеш Мара увеличивается и потом идёт перераспределение объектов через новый перерасчёт хэша объектов, но не до конца понял это, пояснить можно?
Доки не пробовал почитать? У HashMap есть параметры конструктора - начальное количество корзин и порог увеличения.
dm
SD
Читал, я все это и статьи на Хабре, я просто решил спросить и все уточнить чтоб у меня больше не возникало вопросов
https://youtu.be/kk_9md24Ttk
Вот, посмотри, тут нормально объясняют мне кажется
Вот, посмотри, тут нормально объясняют мне кажется
II
Есть две HashMap как можно быстро проверить на совпадение ключей и получить только совпадающие ключи. Ключи хранятся в виде строк. Map большая.
E
Есть две HashMap как можно быстро проверить на совпадение ключей и получить только совпадающие ключи. Ключи хранятся в виде строк. Map большая.
Берёшь мапу с наименьшим количеством элементов и для каждого ключа проверяешь, есть ли такой же в другой мапе. Если есть - пихаешь в список
RS
Если есть Guava, то можно:
Sets.intersection(smallerMap.keySet(), biggerMap.keySet())
он возвращает Set, который будет live view, у которого итератор выполнен как раз по алгоритму из сообщения выше.
Sets.intersection(smallerMap.keySet(), biggerMap.keySet())
он возвращает Set, который будет live view, у которого итератор выполнен как раз по алгоритму из сообщения выше.
AE
Есть две HashMap как можно быстро проверить на совпадение ключей и получить только совпадающие ключи. Ключи хранятся в виде строк. Map большая.
var intersection = map1.keySet().retainAll(map2.keySet())AE
Ruslan Stelmachenko
Если есть Guava, то можно:
Sets.intersection(smallerMap.keySet(), biggerMap.keySet())
он возвращает Set, который будет live view, у которого итератор выполнен как раз по алгоритму из сообщения выше.
Sets.intersection(smallerMap.keySet(), biggerMap.keySet())
он возвращает Set, который будет live view, у которого итератор выполнен как раз по алгоритму из сообщения выше.
Для таких простых операций тащить гуаву... Когда есть метод в jdk
DS
Для таких простых операций тащить гуаву... Когда есть метод в jdk
А для разности есть?
RS
что значит "тащить"? я же сказал "если ЕСТЬ". смысл не использовать возможности либы и изобретать постоянно велосипеды, если либа УЖЕ подключена. А если нет, то да, оверхед. Но retainAll уж точно не лучший способ, когда в условиях задачи написано, что мапы БОЛЬШИЕ.
AE
А для разности есть?
removeAll()
DS
Спасибо!
AE
Ruslan Stelmachenko
что значит "тащить"? я же сказал "если ЕСТЬ". смысл не использовать возможности либы и изобретать постоянно велосипеды, если либа УЖЕ подключена. А если нет, то да, оверхед. Но retainAll уж точно не лучший способ, когда в условиях задачи написано, что мапы БОЛЬШИЕ.
Так гуава быстрее сделает? Сомневаюсь
RS
Я же сказал, что гуава реализована по алогритму, который описал человек сообщением выше.
А для того, чтобы сделать retainAll, нужно сначала map.keySet() добавить в новый HashSet. Если не добавить, то испортишь оригинальную мапу.
А для того, чтобы сделать retainAll, нужно сначала map.keySet() добавить в новый HashSet. Если не добавить, то испортишь оригинальную мапу.
RS
Ну т.е. если 2 мапы по миллиону элементов, и 3 совпадающих, то гуава будет намного эффективнее. Особенно по памяти.