Comments 42
Отлично! Продолжайте :)
+4
Вопрос к читателям: на ваш взгляд/опыт, оправдано ли отсутствие методов для уменьшения размера HashMap-а, и случались ли у вас из-за этого проблемы?
0
имхо не нужно — если вы один раз уже достигли предела и получили новый размер, где гарантия что вы снова его не достигните. Двойная работа получиться если резать.
+2
Иногда вобще предсказывают максимальный размер хэшмапы и просто подбирют соотв. capacity сразу, чтобы не делать дурную лишнюю работу.
Теперь по поводу статьи. А как вы итерируете мапу? =)
Я например foreach'em по MapEntry<..>. Удобно и я где то читал что это самый хороший способ.
Теперь по поводу статьи. А как вы итерируете мапу? =)
Я например foreach'em по MapEntry<..>. Удобно и я где то читал что это самый хороший способ.
0
На мой вкус, первый пример из статьи самый удобный и компактный. Внутри хэш-мапа, все его итераторы устроены практически одинаково.
Другой вопрос, если вам нужны только ключи или только значения, то правильнее будет юзать keySet() и values()
Другой вопрос, если вам нужны только ключи или только значения, то правильнее будет юзать keySet() и values()
а то получится что разработчики класса зря старались :)
0
Просто я раньше получал референс на ключи потом итерировался по ним доставал значения. И всё время у меня было ощущение что я жуткий рак, потому что выглядело это дело несколько громоздко и не сильно производительно (каждый раз опять лезть в мапу).
А потом как то наткнулся на такую реализацию. Мне она показалась самой кошерной.
А потом как то наткнулся на такую реализацию. Мне она показалась самой кошерной.
0
Он самый удобный, потому что следует внутреннему представлению структуры данных. Если итерироваться по ключам, то на каждом шаге придется вызывать хэш-функцию, а на это тратится время и вычислительные ресурсы.
0
Пока надобности не возникало, но я не понимаю почему это не реализовано. Вроде не кажется сильно сложным, а может ведь кому — то и пригодится… Вариант
hashmap = new HashMap<>(hashmap)
конечно рабочий, но я уже привык втыкать final везде где только можно, вроде как правильней… Я бы предпочёл иметь trimToSize().0
Спасибо за статью. Я примерно знал, как работает HashMap, но не задумывался как идет раскидывание по спискам хэшей и даже не догадывался о перераспределении при изменении размера
0
Материал изложен изумительно. Спасибо!
Будут ли рассмотрены остальные мапы?
Будут ли рассмотрены остальные мапы?
+1
А вы чем то кроме HashMap еще в жизни пользуетесь? :-)
0
LinkedHashMap :-)
+1
О, да! На деле самая удобная коллекция. Тот факт, что пары ключ-значение идут в предсказуемом порядке, существенно облегчает дебаг. Жаль, что почти никто этой коллекцией не пользуется.
0
Не только для дебага полезно. У нас был пример, что разработчик вычитал форму из XML в HashMap в виде HashMap<String, UIControl>, где ключ — это идентификатор контрола потом много где использовал её для быстрого получения контрола по идентификатору, но не озаботился тем, что порядок контролов не сохранился. Замена HashMap на LinkedHashMap в одном месте позволила исправить проблему, не трогая кучу готового кода.
0
ConcurrentHashMap!
0
на практике еще интересен IdentityHashMap, котором в отличие от HashMap конфликты по другому разрешаются
0
Спасибо и вам!
Думаю да, мапы еще будут, правда в каком виде еще не думал.
Думаю да, мапы еще будут, правда в каком виде еще не думал.
+1
еще хочется дополнить иерархию, вот более полная
+4
Особенно вкусный ConcurentHashMap
+1
<оффтоп>
В чем нарисована диаграмма?
</оффтоп>
В чем нарисована диаграмма?
</оффтоп>
0
не в курсе, позаимствовал отсюда en.wikibooks.org/wiki/Java_Programming/Collection_Classes
0
Метод hash(key) вовсе не для того, что бы «гарантировать ограниченное число коллизий», перечитайте комментарий в исходнике ещё раз. Он просто обеспечивает более равномерное распределение в случае неудачных хэш-функций.
0
Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки
А как на счёт проверки наличия такого ключа?
Не будет ли здесь потери от загруженности так же, как и в
get
?0
Будет, именно проверки наличия ключа даёт проблему, что вставка никогда не будет быстрее 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)
+1
Про размер таблицы и вычисление индекса мне известно — когда-то уже читал исходники.
Смущает то, что везде пишут, что добавление O(1), а выборка O(1 + a).
Хоть по своей сути добавление включает в себя выборку.
Смущает то, что везде пишут, что добавление O(1), а выборка O(1 + a).
Хоть по своей сути добавление включает в себя выборку.
0
Ну пишут далеко не везде, но в части добавления вы правы, сложность у put/get/remove одинаковая.
В статье же содержится ошибка, так как вставка в начало цепочки сама по себе хоть и гарантирует время O(1), но в java перед вставкой сразу проходим по всей длинне цепочки, чтобы удостовериться что такого элемента нету, в результате O(1) у нас только в идеальном случае будет когда отсутвуют коллизии.
В статье же содержится ошибка, так как вставка в начало цепочки сама по себе хоть и гарантирует время O(1), но в java перед вставкой сразу проходим по всей длинне цепочки, чтобы удостовериться что такого элемента нету, в результате O(1) у нас только в идеальном случае будет когда отсутвуют коллизии.
0
Я и говорю, что put содержит в себе get, т.к. помимо того, что добавляет элемент, он ещё и возвращает предыдущее значение ключа (null если такого ключа ещё не было).
0
Сделал небольшой тест — добавляются элементы с ключами от «0» до «1000000», в результате:
1) Самая длинная цепочка — 6 элементов, средняя длинна — 2 элемента
2) 2 раза было зафиксировано время > 0 при обходе цепочек, по ~16мс каждый
Если пренебречь этими двумя проходами, то как раз получится O(1).
Я пробовал добавить большее количество элементов, но памяти не хватило. Однако предварительные данные показали, по п. 2) срабатываний было больше, хотя время на каждый проход так же не превышало ~16мс.
1) Самая длинная цепочка — 6 элементов, средняя длинна — 2 элемента
2) 2 раза было зафиксировано время > 0 при обходе цепочек, по ~16мс каждый
Если пренебречь этими двумя проходами, то как раз получится O(1).
Я пробовал добавить большее количество элементов, но памяти не хватило. Однако предварительные данные показали, по п. 2) срабатываний было больше, хотя время на каждый проход так же не превышало ~16мс.
0
Ну раз этим можно пренебречь и записать просто O(1), то зачем тогда для get писать O(1+a)?
Не совсем понял смысл вашего теста, что вы хотели им показать?
Не совсем понял смысл вашего теста, что вы хотели им показать?
0
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
Я поддержу выше высказывшихся, т.к. О(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))) {
0
Мой плюс за статью. (кармы не хватает)
Как бы ничего нового не узнал, но все-равно впечатление хорошее.
Как бы ничего нового не узнал, но все-равно впечатление хорошее.
0
Спасибо за пост.
0
Скажите, пожалуйста, как это работает?
h & (length — 1) = 14
h & (length — 1) = 14
0
Еще можно добавить одну тонкость — код:
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");
}
}
не бросит исключения ConcurrentModificationException, потому что entry(3,«3») находится в последнем bucket`е и next(), который и генерирует собственно исключение, вызван не будет0
«Все элементы цепочки, привязанные к table[0], поочередно просматриваются в поисках элемента с ключом null. Если такой элемент в цепочке существует, его значение перезаписывается.
Если элемент с ключом null не был найден, будет вызван уже знакомый метод addEntry().»
Это всё в контексте добавления элемента с ключом null. Значит ли это, что в table[0] всегда храниться не больше одного элемента?
Если элемент с ключом null не был найден, будет вызван уже знакомый метод addEntry().»
Это всё в контексте добавления элемента с ключом null. Значит ли это, что в table[0] всегда храниться не больше одного элемента?
0
Sign up to leave a comment.
Структуры данных в картинках. HashMap