Какая структура данных / решение Java лучше всего соответствует этим требованиям?

Question

Мне нужна структура данных / решение Java, которое отвечает этим требованиям. Что лучше всего подходит для них?

1) Порядок вставки объекта должен соблюдаться

2) Объекты должны быть уникальными (это объекты базы данных, которые уникально идентифицируются UUID).

3) Если добавлен более новый объект с таким же идентификатором, более старая версия объекта должна быть перезаписана / удалена

4) Решение должно быть доступно многим потокам.

5) Когда первый объект, добавленный в Структуру, читается / используется, он должен быть удален из структуры данных

Answer 1

Здесь есть несколько возможностей. Самое простое - начать с LinkedHashSet . Это обеспечит вам уникальность и предсказуемый порядок, который вам требуется. Затем вы можете обернуть полученный набор, чтобы сделать его потокобезопасным:

Set<T> s = Collections.synchronizedSet(new LinkedHashSet<T>(...));

Примечание. Поскольку Set не определяет метод извлечения элементов из него, ваш код должен будет вручную вызывать Set.remove (Object).

В качестве альтернативы, вы можете обернуть LinkedHashMap , который предоставляет хук для семантики удаления при чтении, которая вам необходима:

class DeleteOnReadMap<K, V> implements Map<K, V> {

    private Map<K, V> m = new LinkedHashMap<K, V>();

    // implement Map "read" methods Map with delete-on-read semantics
    public V get(K key) {
        // ...
    }
    // (other read methods here)

    // implement remaining Map methods by forwarding to inner Map
    public V put(K key, V value) {
        return m.put(key, value);
    }
    // (remaining Map methods here)
}

Наконец, оберните экземпляр вашей пользовательской карты, чтобы сделать ее поточно-ориентированной:

Map<K, V> m = Collections.synchronizedMap(new DeleteOnReadMap<K, V>(...));

Answer 2

Решения о LinkedHashSet были бы хорошей отправной точкой.

Однако вам придется переопределить методы equals и hashcode для объектов, которые вы собираетесь поместить в набор, чтобы удовлетворить ваше требование номер 3.

Answer 3

1) Порядок вставки объекта должен быть хранится

Это любая "нормальная" структура данных - массив, arrayList, дерево. Поэтому избегайте самобалансирующихся или самосортирующихся структур данных: кучи, хеш-таблицы или деревья перемещения на передний план (например, splay-деревья). Опять же, вы можете использовать одну из этих структур, но Вы должны отслеживать его порядок вставки в каждом узле.

2) Объект должен быть уникальным (это объекты базы данных, которые уникально идентифицируется UUID).

Сохраняет уникальный идентификатор, связанный с каждым объектом. Если это программа на C, то указатель на этот узел уникален (я полагаю, что это применимо и к Java). Если указатель узла недостаточен для поддержания «уникальности», то вам нужно добавить поле к каждому узлу, который Вы гарантированно имеете уникальную ценность.

3) Если более новый объект с тем же идентификатором добавлена ​​более старая версия объект должен быть переписан / удален

Где вы хотите разместить узел? Вы хотите заменить существующий узел? Или вы хотите удалить старый узел, а затем добавить новый в конец? Это важно, потому что это связано с вашим требованием # 1, где порядок вставки должен быть сохранен.

4) Решение должно быть доступно по многим темам.

Единственный способ, которым я могу придумать, это реализовать какую-то блокировку. Java позволяет заключать структуры и код в блок synchronized.

5) Когда первый объект добавлен в Структура читается / используется, она должна быть удалено из структуры данных

Вроде как операция "dequeue".

Похоже, ArrayList - довольно хороший вариант для этого: просто из-за # 5. Единственная проблема заключается в том, что поиски являются линейными. Но если у вас сравнительно небольшой объем данных, это не такая уж большая проблема.

В противном случае, как говорили другие: HashMap или даже какое-то Дерево будет работать, но это будет зависеть от частоты обращений. (Например, если к «самому последнему» элементу наиболее вероятно получить доступ, я бы использовал линейную структуру. Но если доступ будет иметь «случайные» элементы, я бы использовал HashMap или Tree.)

Answer 4

Моя мысль выглядит примерно так:

 Collections.synchronizedMap(new LinkedHashMap<K, V>());

Я думаю, что обо всем позаботится, кроме требования 5, но вы можете сделать это, используя метод remove() вместо get().

Это будет не так эффективно, как было бы ConcurrentMap - синхронизация блокирует всю карту при каждом доступе, но я думаю, что ConncurrentMap реализации могут использовать блокировки чтения-записи и выборочную блокировку только на части карты чтобы позволить нескольким бесконфликтным доступам продолжаться одновременно. Если бы вы хотели, вы могли бы получить лучшую производительность, написав свой собственный подкласс некоторой существующей реализации Map.

Answer 5

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

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

Вы можете посмотреть на метод «Содержит», как вам понадобится.