Map

[ReyMagos]

Добрый день!
Я вот уже несколько лет знаком с джавой и вроде бы знаю большинство нужных вещей, но очень сильно давит мешает некоторых (ведь возможно код можно сделать лучше с этими штуками). Я про Map. Несколько раз мне приходилось их использовать, но я как-то не задумывался о них, просто брал HashMap и вперёд. Но как-то понадобилось отсортировать словарь (привет питонистам) по значениям, и в StackOverFlow я нашёл тему, где про это говорилось, и было указание, о том, что надо использовать именно LinkedHashMap. Я такой, что? Решил посмотреть документацию, а там целая книга, комментов больше, чем кода (нет, серьёзно страниц 6 текста, да ещё на английском!). Посмотрел гайды на habr и тому подобное, но не понял ничего, хотя бы потому что брать хэш от строки (и тому подобное) я научился месяца 2 назад). И вот моя просьба: может кто-то объяснить разницу, принципиальное отличие HashMap, LinkedHashMap, TreeMap от друг друга. Буду очень благодарен!

 

[tox1cozZ]

Если вкратце:
Линкед позволяет хранито данные в том порядке, в котором их добавили в мапу. То есть если ты добавить три записи и потом пробежишься циклом - далеко не факт что они буду в том порядке, в котором добавили. Линкед же это гарантирует.
Три мап - это всегда отсортированная мапа по ключу.

 

[hohserg]

LinkedHashMap ведь еще может изменять порядок, если обращаться к произвольным ключам, то они как бы поползут вверх в плане порядка?

 

[ReyMagos]

поползут вверх

То есть расположение зависит от используемости объекта? Если так, то прикольно, ведь его быстрее будет находить при запросе.

 

[hohserg]

Я не уверен на счет этого, просто видел LRU-кэш на основе этой мапы

 

[Might]

то они как бы поползут вверх в плане порядка?

Ничего такого вроде там нету, в исходниках посмотрел. Да и какой смысл в этом?

То есть если ты добавить три записи и потом пробежишься циклом - далеко не факт что они буду в том порядке, в котором добавили. Линкед же это гарантирует.

Они ссылаются друг на друга, не больше. А вот в памяти они могут быть расположены далеко не по порядку. Т.е. это по сути та же хэш-мапа ,в ней элементы храняться по индексу в зависимости от хеша, и ссылаются друг на друга.

 

[tox1cozZ]

Ссылаются, тем самым идут по порядку. По крайней мере если пробегаться циклом:

Map<String, Integer> map = Maps.newLinkedHashMap(); //Maps.newHashMap();
map.put("Hello", 2);
map.put("Forum", 4);
map.put("Map test", 8);
map.forEach((k, v) -> System.out.println(k + "=" + v));

Можешь протестировать. В случае линкеда все выводится в том порядке, в котором ты добавил. В случае обычной мапы: Hello, Map test, Forum.

 

[Might]

Это да, но в участке памяти, которое выделено приложению они не по порядку, я про это. Поэтому при переборе больших коллекций могут быть некоторые проблемы с производительностью по сравнению с перебором обычных элементов того же ArrayList.

 

[tox1cozZ]

Чтобы не было проблем с производительностью, нужно идти читать более подробно как работает та или иная структура данных.

 

[hohserg]

Ничего такого вроде там нету, в исходниках посмотрел. Да и какой смысл в этом?

Вот этот простой тест показывает, что линкед мапа так работает: Scastie - An interactive playground for Scala

test1
{K1=test, K2=test, K3=test}
{K2=test, K3=test, K4=test}
test2
{K1=test, K2=test, K3=test}
{K3=test, K1=test, K4=test}

 

[tox1cozZ]

При создании объекта последний булев в конструкторе поставь фолс и не будет такого))

 

[hohserg]

Так это типо требуемое поведение. Для кэшей можно применять

 

[tox1cozZ]

А зачем? Если хэшкод у ключа реализован без коллизий, то доступ по ключу за константное время при любом размере мапы. Мы ж не занимаемся тут перебором

 

[hohserg]

Для кэша. Представь, что есть некая функция, которую дорого вычислять и ты хочешь ее мемоизировать, чтобы однажды вычисленные значения не пришлось вычислять заново. При этом не хочешь тратить на это больше 10мб, например.
Допустим, первый раз было запрошено значение с аргументом K1. Потом еще для каких-то аргументов на 9мб и иногда опять K1. Потом еще для новых аргументов на 1мб. И значению по ключу K1 выгрузилось, хотя оно часто используется и нужно больше чем какое-то другое.
Кэш не изменяет порядка при обращении к нему и какие-то часто используемые значения могут выгрузиться, а какие-то менее используемые значения могут остаться.
Для решения этого и был придуман LRU-кэш

 

[tox1cozZ]

Понял, спасибо)
Я всегда юзал Cache из guava, там все эти моменты можно указать как раз)
Например, элемент удаляется через какое-то время, либо если к нему не обращались некоторое время.

 

[ReyMagos]

этот простой тест

А почему во втором тесте первый элемент K3? Ведь чаще использовали К1.

То бишь если мне надо просто переслать какие-то данные (entitydata допустим), то можно не парится и пользоваться HashMap. Но если нужно использовать заранее вычисленные значения, то подойдёт Linked. Верно?

А вообще, вам спасибо огромное!) Лучше всяких учебников, всё понятно объяснили.

 

[tox1cozZ]

Если нужно чтобы элементы были в порядке добавления - Linked. Но это нужно крайне редко, например когда нужно отсортировать мапу по значению, например.
В 95% случаев юзается HashMap.
Нужна сортировка по ключам - TreeMap.
Если в мапе ключ или значение - это примитив, то юзаешь TMap из библиотеки trove для соответствующих типов, она по дефолту есть в майне.

 

[hohserg]

Если нужна сортировка по ключам, имеет смысл посмотреть в сторону дерева ван Эмде Боаса

А почему во втором тесте первый элемент K3? Ведь чаще использовали К1.

Справа - те к которым обращались последними

 

[tox1cozZ]

Если нужна сортировка по ключам, имеет смысл посмотреть в сторону дерева ван Эмде Боаса

Зачем? TreeMap отлично справляется с задачей, сомневаюсь что его будет недостаточно.

Класс TreeMap, его устройство и способ применения.

В статье рассмотрено класс TreeMap, пример использования TreeMap, изменение порядка сортировки, синхронизация, устройство и структура данных в основе TreeMap.

www.quizful.net

 

[CumingSoon]

Я тему особо не читал, но хотелось бы сказать, что такие ситуации, когда нужны специфичные мапы случаются примерно 1 раз в 1млн лет. Однако они вообще особо не эффективно по кэш миссам ЦПУ. Поэтому желательно аллоцировать сразу большой кусок памяти(вроде б, есть параметр на приблизительный размер мапы) + использовать HashMap, так как внутри там вроде бы массив