Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 43
Отлично! Продолжайте :)
Вопрос к читателям: на ваш взгляд/опыт, оправдано ли отсутствие методов для уменьшения размера HashMap-а, и случались ли у вас из-за этого проблемы?
имхо не нужно — если вы один раз уже достигли предела и получили новый размер, где гарантия что вы снова его не достигните. Двойная работа получиться если резать.
Иногда вобще предсказывают максимальный размер хэшмапы и просто подбирют соотв. capacity сразу, чтобы не делать дурную лишнюю работу.
Теперь по поводу статьи. А как вы итерируете мапу? =)
Я например foreach'em по MapEntry<..>. Удобно и я где то читал что это самый хороший способ.
Теперь по поводу статьи. А как вы итерируете мапу? =)
Я например foreach'em по MapEntry<..>. Удобно и я где то читал что это самый хороший способ.
На мой вкус, первый пример из статьи самый удобный и компактный. Внутри хэш-мапа, все его итераторы устроены практически одинаково.
Другой вопрос, если вам нужны только ключи или только значения, то правильнее будет юзать keySet() и values()
Другой вопрос, если вам нужны только ключи или только значения, то правильнее будет юзать keySet() и values()
а то получится что разработчики класса зря старались :)Просто я раньше получал референс на ключи потом итерировался по ним доставал значения. И всё время у меня было ощущение что я жуткий рак, потому что выглядело это дело несколько громоздко и не сильно производительно (каждый раз опять лезть в мапу).
А потом как то наткнулся на такую реализацию. Мне она показалась самой кошерной.
А потом как то наткнулся на такую реализацию. Мне она показалась самой кошерной.
Он самый удобный, потому что следует внутреннему представлению структуры данных. Если итерироваться по ключам, то на каждом шаге придется вызывать хэш-функцию, а на это тратится время и вычислительные ресурсы.
Пока надобности не возникало, но я не понимаю почему это не реализовано. Вроде не кажется сильно сложным, а может ведь кому — то и пригодится… Вариант
hashmap = new HashMap<>(hashmap) конечно рабочий, но я уже привык втыкать final везде где только можно, вроде как правильней… Я бы предпочёл иметь trimToSize().
Спасибо за статью. Я примерно знал, как работает HashMap, но не задумывался как идет раскидывание по спискам хэшей и даже не догадывался о перераспределении при изменении размера
Материал изложен изумительно. Спасибо!
Будут ли рассмотрены остальные мапы?
Будут ли рассмотрены остальные мапы?
А вы чем то кроме HashMap еще в жизни пользуетесь? :-)
LinkedHashMap :-)
О, да! На деле самая удобная коллекция. Тот факт, что пары ключ-значение идут в предсказуемом порядке, существенно облегчает дебаг. Жаль, что почти никто этой коллекцией не пользуется.
Не только для дебага полезно. У нас был пример, что разработчик вычитал форму из XML в HashMap в виде HashMap<String, UIControl>, где ключ — это идентификатор контрола потом много где использовал её для быстрого получения контрола по идентификатору, но не озаботился тем, что порядок контролов не сохранился. Замена HashMap на LinkedHashMap в одном месте позволила исправить проблему, не трогая кучу готового кода.
ConcurrentHashMap!
на практике еще интересен IdentityHashMap, котором в отличие от HashMap конфликты по другому разрешаются
Спасибо и вам!
Думаю да, мапы еще будут, правда в каком виде еще не думал.
Думаю да, мапы еще будут, правда в каком виде еще не думал.
еще хочется дополнить иерархию, вот более полная
Особенно вкусный ConcurentHashMap
<оффтоп>
В чем нарисована диаграмма?
</оффтоп>
В чем нарисована диаграмма?
</оффтоп>
не в курсе, позаимствовал отсюда en.wikibooks.org/wiki/Java_Programming/Collection_Classes
Метод hash(key) вовсе не для того, что бы «гарантировать ограниченное число коллизий», перечитайте комментарий в исходнике ещё раз. Он просто обеспечивает более равномерное распределение в случае неудачных хэш-функций.
Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки
А как на счёт проверки наличия такого ключа?
Не будет ли здесь потери от загруженности так же, как и в
get?
Будет, именно проверки наличия ключа даёт проблему, что вставка никогда не будет быстрее get.
Другой вопрос что в теории длинна цепочки не может быть больше (int)(capacity * loadFactor), и для небольших мэпов это проходит. Проблемы могут случиться когда вы заполнили хеш, он разросся и это значение стало достаточно большим, потом удалили большинство и опять заполняете, может оказаться так, что все данные попадают в одну ооооочень длинную цепочку, вероятность конечно низкая, но всё может случится в этом мире.
Отдельно хотелось бы заметить нюанс, что размер таблицы для кранения цепочек всегда кратен степени двойки и при расширении удваивается, на этапе инициализации любое ваше значение округляется до ближайшей степени в большую сторону:
Данное условие следует из оптимизации при получении текущего индекса в таблице цепочек:
Вот такой вот оригинальный способ получения остатка от деления =) (код эквивалентен: h % length)
Другой вопрос что в теории длинна цепочки не может быть больше (int)(capacity * loadFactor), и для небольших мэпов это проходит. Проблемы могут случиться когда вы заполнили хеш, он разросся и это значение стало достаточно большим, потом удалили большинство и опять заполняете, может оказаться так, что все данные попадают в одну ооооочень длинную цепочку, вероятность конечно низкая, но всё может случится в этом мире.
Отдельно хотелось бы заметить нюанс, что размер таблицы для кранения цепочек всегда кратен степени двойки и при расширении удваивается, на этапе инициализации любое ваше значение округляется до ближайшей степени в большую сторону:
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity) capacity <<= 1;
Данное условие следует из оптимизации при получении текущего индекса в таблице цепочек:
static int indexFor(int h, int length) {
return h & (length-1);
}
Вот такой вот оригинальный способ получения остатка от деления =) (код эквивалентен: h % length)
Про размер таблицы и вычисление индекса мне известно — когда-то уже читал исходники.
Смущает то, что везде пишут, что добавление O(1), а выборка O(1 + a).
Хоть по своей сути добавление включает в себя выборку.
Смущает то, что везде пишут, что добавление O(1), а выборка O(1 + a).
Хоть по своей сути добавление включает в себя выборку.
Ну пишут далеко не везде, но в части добавления вы правы, сложность у put/get/remove одинаковая.
В статье же содержится ошибка, так как вставка в начало цепочки сама по себе хоть и гарантирует время O(1), но в java перед вставкой сразу проходим по всей длинне цепочки, чтобы удостовериться что такого элемента нету, в результате O(1) у нас только в идеальном случае будет когда отсутвуют коллизии.
В статье же содержится ошибка, так как вставка в начало цепочки сама по себе хоть и гарантирует время O(1), но в java перед вставкой сразу проходим по всей длинне цепочки, чтобы удостовериться что такого элемента нету, в результате O(1) у нас только в идеальном случае будет когда отсутвуют коллизии.
Я и говорю, что put содержит в себе get, т.к. помимо того, что добавляет элемент, он ещё и возвращает предыдущее значение ключа (null если такого ключа ещё не было).
Сделал небольшой тест — добавляются элементы с ключами от «0» до «1000000», в результате:
1) Самая длинная цепочка — 6 элементов, средняя длинна — 2 элемента
2) 2 раза было зафиксировано время > 0 при обходе цепочек, по ~16мс каждый
Если пренебречь этими двумя проходами, то как раз получится O(1).
Я пробовал добавить большее количество элементов, но памяти не хватило. Однако предварительные данные показали, по п. 2) срабатываний было больше, хотя время на каждый проход так же не превышало ~16мс.
1) Самая длинная цепочка — 6 элементов, средняя длинна — 2 элемента
2) 2 раза было зафиксировано время > 0 при обходе цепочек, по ~16мс каждый
Если пренебречь этими двумя проходами, то как раз получится O(1).
Я пробовал добавить большее количество элементов, но памяти не хватило. Однако предварительные данные показали, по п. 2) срабатываний было больше, хотя время на каждый проход так же не превышало ~16мс.
Ну раз этим можно пренебречь и записать просто O(1), то зачем тогда для get писать O(1+a)?
Не совсем понял смысл вашего теста, что вы хотели им показать?
Не совсем понял смысл вашего теста, что вы хотели им показать?
pastebin.com/u8B5vbuk
size entry table: 65536
null: 65535
not null: 1
имею одну большую цепочку из 30к элементов
Вопрос: какая скорость работы получится?
p.s. да я знаю что это придуманный пример, но он наглядно илюстрирует падение якобы O(1), можете поставить 1кк и идти курить
size entry table: 65536
null: 65535
not null: 1
имею одну большую цепочку из 30к элементов
Вопрос: какая скорость работы получится?
p.s. да я знаю что это придуманный пример, но он наглядно илюстрирует падение якобы O(1), можете поставить 1кк и идти курить
Я поддержу выше высказывшихся, т.к. О(1) — не правда при вставке. Поиск на уже существующий элемент все же присутствует. Поэтому операция get() мало чем отличается от операции put()
318 for (Entry<K,V> e = table[indexFor(hash, table.length)];
319 e != null;
320 e = e.next) {
391 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392 Object k;
393 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
Мой плюс за статью. (кармы не хватает)
Как бы ничего нового не узнал, но все-равно впечатление хорошее.
Как бы ничего нового не узнал, но все-равно впечатление хорошее.
Спасибо за пост.
Скажите, пожалуйста, как это работает?
h & (length — 1) = 14
h & (length — 1) = 14
Еще можно добавить одну тонкость — код:
HashMap<Integer, String> hm = new HashMap<>();
hm.put(1, "1");
hm.put(2, "2");
hm.put(3, "3");
Set<Integer> s = hm.keySet();
for (Integer nextInt: s){
if (nextInt == 3){
hm.put(4, "4");
}
}
«Все элементы цепочки, привязанные к table[0], поочередно просматриваются в поисках элемента с ключом null. Если такой элемент в цепочке существует, его значение перезаписывается.
Если элемент с ключом null не был найден, будет вызван уже знакомый метод addEntry().»
Это всё в контексте добавления элемента с ключом null. Значит ли это, что в table[0] всегда храниться не больше одного элемента?
Если элемент с ключом null не был найден, будет вызван уже знакомый метод addEntry().»
Это всё в контексте добавления элемента с ключом null. Значит ли это, что в table[0] всегда храниться не больше одного элемента?
в Java 8 элемент добавляется в конец цепочки в бакете
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
при коллизиях добавление произойдет в начало цепочки
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Структуры данных в картинках. HashMap