Datastructure: hashmap vs linkedhashmap vs treemap

Question

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

• Hashmap: будет более эффективным в целом; O (1) (нормальный случай), O (N) (в худшем случае, только с плохой хэш-алгоритма)
• LinkedHashmap: поддерживает вставки порядок элементов, занимают больше памяти, чем HashMap
• Treemap: сохраняет элементы сортируют, O (журнал (п)) (если сбалансирован)

Мой вопрос: Почему мы должны поддерживать порядок вставки или элементы сортируются, если в конце производительность вставки, поиск .. есть лучше с hashmap?

Answer 1

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

Аналогичным образом для сортировки. Это дает возможность находить «следующий» или «предыдущий» элемент очень дешево, при этом все еще достаточно эффективно для произвольного поиска. Одним из примеров является приблизительный поиск, скажем, вы знаете, что запись, которую вы ищете, начинается с Foo, но вы не знаете, что остальная часть ключа.

Hashmap существует, чтобы сделать вещи быстрее и проще (без концепции порядка), когда вам не нужны какие-либо из этих операций, только точный поиск.

Answer 2

Я использую Treemap и LinkedHashMap, потому что, хотя я могу сортировать HashMap самостоятельно, я сомневаюсь, что мое решение будет таким же быстрым или эффективным с точки зрения памяти, как Java.