Map

[ReyMagos]

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


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

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

Спойлер

А ещё на самом деле я слышал что по хэшу в массиве можно найти элемент за O(1), не перебирая все (вроде это было про Set), но в моей голове это немного не укладывается)

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

примитив

Блин, извините что превращаю тему в какой-то чатик (хотя это оффтоп, но всё же), но вообще какая разница между int и Integer? Почему бы int просто не выпилить? Его нельзя нигде использовать (кроме переменных конечно же), он же не объект.

 

[tox1cozZ]

ещё на самом деле я слышал что по хэшу в массиве можно найти элемент за O(1)

Именно, в этом и прелесть мапы. Поэтому очень важно грамотно определить hashCode чтобы не было коллизий. В самом худшем случае(если у ключа хэшкод будет константным) мапа превратится по сути в список, по которому придется полностью пробегаться)

но вообще какая разница между int и Integer?

int - примитив, занимает 4 байта.
Integer - класс-обертка, занимает 24 байта если мне не изменяет память.
Ну и с примитивами там куча нюансов перфомансных, они куда быстрее чем создания объектов и все такое.

 

[hohserg]

А еще переменные Integer хранится в куче, а int - на стеке(кроме полей)

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

Это просто результат toString