Как сохранить порядок элементов в хеш-таблице

Question

У меня есть хеш-таблица. Метод values ​​() возвращает значения в некотором порядке, отличном от порядка, в котором я вставлен. Как я могу получить значения в том же порядке, в котором я вставил? Использование LinkedHashmap является альтернативой, но не синхронизировано.

Answer 1

Используйте LinkedHashMap.

Хеш-таблица и связанный список реализация интерфейса Map, с предсказуемым порядком итераций. это реализация отличается от HashMap в что он поддерживает двусвязный список пробегая все его записи. Этот связанный список определяет итерацию заказ, который обычно заказ в котором ключи были вставлены в карта ( порядок вставки ). Обратите внимание, что порядок вставки не изменяется, если ключ повторно вставлен в карту. (A ключ k вставляется в карту m, если m.put(k, v) вызывается, когда m.containsKey(k) вернется true непосредственно перед вызовом.)

в сочетании с Collections.synchronizedMap().

Так, например:

Map<String, String> map = Collections.synchronizedMap(
  new LinkedHashMap<String, String>());

Answer 2

Вы можете либо обернуть LinkedHashMap и синхронизировать, либо использовать утилиту Collections.synchronizedMap для создания синхронизированного LinkedHashMap:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

Из JavaDoc:

Если несколько потоков обращаются к связанной хэш-карте одновременно, и хотя бы один из потоков структурно изменяет карту, она должна быть синхронизирована извне. Обычно это достигается путем синхронизации с некоторым объектом, который естественным образом инкапсулирует карту. Если такого объекта не существует, карту следует «обернуть» с помощью метода Collections.synchronizedMap. Это лучше всего делать во время создания, чтобы предотвратить случайный несинхронизированный доступ к карте

Answer 3

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

Answer 4

Если jdk1.6, у вас есть только два типа упорядоченной карты EnumMap и LinkedHashMap. Оба они не синхронизированы. Если вам просто нужно запомнить заказ, используйте

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

если вы хотите отсортировать, используйте ConcurrentSkipListMap

Answer 5

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