Как реализация LinkedHashMap отличается от HashMap?
Если временная сложность LinkedHashMap - то же как сложность HashMap, почему нам нужен HashMap? То, каков весь дополнительный служебный LinkedHashMap, имеет по сравнению с HashMap в Java?
4 ответа
LinkedHashMap займет больше памяти. Каждая запись в обычном HashMap содержит только ключ и значение. Каждая запись LinkedHashMap имеет эти ссылки и ссылки на следующую и предыдущую записи. Также нужно немного поработать, хотя обычно это не имеет значения.
- LinkedHashMap дополнительно поддерживает дважды связанный список, проходящий через все его записи, что обеспечивает воспроизводимый порядок. Этот связный список определяет порядок итераций, который обычно является порядком, в котором ключи были вставлены в карту (insertion-order).
- HashMap не имеет этих дополнительных затрат (время выполнения, пространство) и должен быть предпочтительнее LinkedHashMap, когда вам не важен порядок вставки.
LinkedHashMap - полезная структура данных, когда вам нужно знать порядок вставки. ключей к карте. Один подходящий вариант использования - реализация кеша LRU. Из-за порядка обслуживания LinkedHashMap структура данных требует дополнительной памяти по сравнению с HashMap. Если порядок вставки не является обязательным, вы всегда должны использовать HashMap.
Если временная сложность LinkedHashMap такая же, как сложность HashMap, зачем нам нужен HashMap?
Не следует путать сложность с производительностью. Два алгоритма могут иметь одинаковую сложность, но один из них может постоянно работать лучше другого.
Помните, что f(N) - O(N) означает, что:
C1*N <= limit(f(N), N -> infinity) <= C2*N
где C1 и C2 - строго положительные константы. Сложность ничего не говорит о том, насколько малы или велики значения C. Для двух разных алгоритмов константы, скорее всего, будут разными.
(И помните, что сложность big-O говорит о поведении / производительности, когда N становится очень большим. Она ничего не говорит вам о поведении / производительности для малых значений N.)
Сказав это, различие в производительности между операциями HashMap и LinkedHashMap в эквивалентных случаях использования относительно невелико. Зачастую более значимыми являются дополнительные накладные расходы памяти.