Java Случайный доступ к карте

Question

Я ищу библиотеку с открытым исходным кодом, которая имеет реализацию карты произвольного доступа. Мне нужна карта, которая поддерживает свой хэш-индекс, но также индексирует значения в порядке вставки, например LinkedHashmap, за исключением того, что вам не нужно проходить через нее, чтобы найти, например. Элемент 2. Что-то вроде этого:

Map m = new ArrayMap(); 
m.put("0", "v0"); 
m.put("1", "v1"); 
m.put("2", "v2"); 
m.put("3", "v3"); 

тогда:

assertEquals("v2", m.get("2")); 
assertEquals("v2", m.getAtIndex(2)); 

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

Быстрый google ничего не нашел, я не видел его в коллекциях Guava или commons (возможно, я пропустил это). У меня действительно нет времени для его правильного использования прямо сейчас.

Answer 1

Если ваша карта является статической или если он только что обновили ocasionally можно использовать values() метод LinkedHashMap который предоставляет список значений отображения как Collection<T>. Затем вы можете преобразовать набор в массив с toArray(T[] a), и у вас будет постоянный доступ к элементам, конечно, это избавит некоторую память от хранения дополнительных ссылок, но вы зададите две конкретные хорошие сложности, поэтому необходим компромисс между памятью. Это будет хорошо, если вам не нужно получать значения, пока вы добавляете их смешанным способом.

Единственным способом было бы реализовать LinkedHashMap самостоятельно, используя массив вместо этого, чтобы связанный список сохранял порядок вставки, но вам нужно будет заботиться о удвоении емкости arraylist, когда это необходимо, чтобы поддерживать производительность достаточно хорошо ,

Answer 2

Я думаю, что LinkedHashMap - это именно то, что вам нужно.

Вы можете использовать его в качестве карты:

map.get("v2"); 

и в список:

new ArrayList(map.values().values()).get(2); 

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

Answer 3

Если Map может быть неизменны, вы можете сделать это:

ImmutableMap<String, String> map = ... 
String v2 = map.entrySet().asList().get(2).getValue(); 

asList() на entrySet() для обычного ImmutableMap просто использует собственный массив карты записей непосредственно, так что случайный доступ и быстро.

Answer 4

Вы хотите найти значения двумя разными способами. Самый простой/быстрый способ сделать это - сохранить две коллекции, одну карту и один ArrayList.

private final Map<String, String> map; 
private final List<String> list; 

public void put(String key, String value) { 
    map.put(key,value); 
    list.add(value); 
} 

public String get(String key) { 
    return map.get(key); 
} 

public String get(int index) { 
    return list.get(index); 
}