Структура данных с быстрым indexOf?

Question

Мне нужна упорядоченная структура данных с операцией O (1) indexOf. Я храню указатели объектов в структуре данных. Есть идеи? Какой-то LinkedHashMap?

Посмотрите, что означает "indexOf": List.indexOf(Object)

Answer 1

Этот вопрос для начала неоднозначен.

1. Было бы неплохо, если бы вы могли определить, что вы подразумеваете под быстрой indexOf(..) операцией.
2. Какие объекты вы собираетесь хранить в коллекции?
3. Находит indexOf(..) единственная ответственность коллекции.

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

HashMap<Object, List<Integer>>

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

Answer 2

Звучит так, будто вы хотите, чтобы SortedMap, TreeMap являлось эталонной реализацией.Производительность составляет log(n), и это, вероятно, лучшее, что вы получите, используя поиск в упорядоченной структуре (по крайней мере, в стандартных библиотеках).

Answer 3

Если вы используете список пропусков или сбалансированное дерево, вы можете получить O (log n) для insert и indexOf.

Если вы сохраняете отсортированный List<Object> для хранения элементов, которые вы хотите отслеживать, вместе с HashMap<Object, Integer> для хранения начальной позиции каждого элемента, вы можете получить O (1) indexOf в обмен на O ( n) insert.

Я не задумывался об этом глубоко, но я не думаю, что возможно получить O (1) вставку и O (log n) indexOf.

Answer 4

Сохранить объект как ключ и значение в HashMap. Я предполагаю, что вы хотите получить объект в конце концов.

Answer 5

вместо этого попробуйте использовать PriorityQueue, чтобы сделать его более упорядоченным