Набор, который однозначно содержит ключ, но упорядочен по другому полю

Question

Набор, который однозначно содержит ключ, но упорядочен по другому полю

Я ищу коллекцию Java, возможно, в стандартной библиотеке, которая может собирать следующую структуру:

      class Item {
    String key;
    double score;
}

И со следующими свойствами:

Допускается только один элемент с одним и тем же ключом (например, набор)
вставить, удалить, проверить наличие в max O(logn)
обход, упорядоченный по счету, поиск следующего за максимальное время O(logn)

Насколько я понял, стандартный OrderedSet должен иметь сопоставимый интерфейс, согласованный с интерфейсом equals(), но это не мой случай, поскольку два элемента с разными ключами могут иметь одинаковую оценку.

На самом деле я заметил, что TreeSet использует компаратор, возвращающий 0, чтобы проверить, присутствует ли элемент уже.

Любое предложение?

1

java set ordered-set

Источник

user1654526 25 дек '20 в 12:18

5 ответов

Другие вопросы по тегам java set ordered-set

user5221149 25 дек '20 в 13:50 2020-12-25 13:50 · Answer 1 · 2020-12-25 13:50

Теперь, когда вставка уменьшена до O(log n), вы можете сделать это с двойным набором, т.е. реализовать свой собственный набор, который поддерживает 2 набора за кулисами.

Лучше всего было бы, если бы вы могли изменить класс Itemреализовать equals()и использовать только поле. В этом случае ваш класс будет использовать HashSetи . Если hashCode()охватывает не только keyполе, затем используйте два TreeSetобъекты.

      final class ItemSet implements NavigableSet<Item> {

    private final Set<Item> keySet = new HashSet<>();
    //                           or: new TreeSet<>(Comparator.comparing(Item::getKey));
    private final TreeSet<Item> navSet = new TreeSet<>(Comparator.comparingDouble(Item::getScore)
                                                                 .thenComparing(Item::getKey));

    //
    // Methods delegating to keySet for unique key access and for unordered access
    //

    @Override public boolean contains(Object o) { return this.keySet.contains(o); }
    @Override public boolean containsAll(Collection<?> c) { return this.keySet.containsAll(c); }
    @Override public int size() { return this.keySet.size(); }
    @Override public boolean isEmpty() { return this.keySet.isEmpty(); }

    //
    // Methods delegating to navSet for ordered access
    //

    @Override public Comparator<? super Item> comparator() { return this.navSet.comparator(); }
    @Override public Object[] toArray() { return this.navSet.toArray(); }
    @Override public <T> T[] toArray(T[] a) { return this.navSet.toArray(a); }
    @Override public Item first() { return this.navSet.first(); }
    @Override public Item last() { return this.navSet.last(); }
    @Override public Item lower(Item e) { return this.navSet.lower(e); }
    @Override public Item floor(Item e) { return this.navSet.floor(e); }
    @Override public Item ceiling(Item e) { return this.navSet.ceiling(e); }
    @Override public Item higher(Item e) { return this.navSet.higher(e); }

    //
    // Methods delegating to both keySet and navSet for mutation of this set
    //

    private final class ItemSetIterator implements Iterator<Item> {
        private final Iterator<Item> iterator = ItemSet.this.navSet.iterator();
        private Item keyToRemove;
        @Override
        public boolean hasNext() {
            return iterator.hasNext();
        }
        @Override
        public Item next() {
            keyToRemove = iterator.next();
            return keyToRemove;
        }
        @Override
        public void remove() {
            iterator.remove();
            ItemSet.this.keySet.remove(keyToRemove);
            keyToRemove = null;
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new ItemSetIterator();
    }
    @Override
    public void clear() {
        this.keySet.clear();
        this.navSet.clear();
    }
    @Override
    public boolean add(Item e) {
        if (! this.keySet.add(e))
            return false; // item already in set
        if (! this.navSet.add(e))
            throw new IllegalStateException("Internal state is corrupt");
        return true;
    }
    @Override
    public boolean remove(Object o) {
        if (! this.keySet.remove(o))
            return false; // item not in set
        if (! this.navSet.remove(o))
            throw new IllegalStateException("Internal state is corrupt");
        return true;
    }
    @Override
    public boolean addAll(Collection<? extends Item> c) {
        boolean changed = false;
        for (Item item : c)
            if (add(item))
                changed = true;
        return changed;
    }
    @Override
    public boolean removeAll(Collection<?> c) {
        boolean changed = false;
        for (Object o : c)
            if (remove(o))
                changed = true;
        return changed;
    }
    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public Item pollFirst() {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public Item pollLast() {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public NavigableSet<Item> descendingSet() {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public Iterator<Item> descendingIterator() {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public SortedSet<Item> headSet(Item toElement) {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public NavigableSet<Item> headSet(Item toElement, boolean inclusive) {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public SortedSet<Item> tailSet(Item fromElement) {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public NavigableSet<Item> tailSet(Item fromElement, boolean inclusive) {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public SortedSet<Item> subSet(Item fromElement, Item toElement) {
        throw new UnsupportedOperationException("Not yet implemented");
    }
    @Override
    public NavigableSet<Item> subSet(Item fromElement, boolean fromInclusive, Item toElement, boolean toInclusive) {
        throw new UnsupportedOperationException("Not yet implemented");
    }

}

user1654526 25 дек '20 в 13:30 2020-12-25 13:30 · Answer 2 · 2020-12-25 13:30

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

      TreeMap<Double, HashSet<Item>>

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

user1124509 25 дек '20 в 12:30 2020-12-25 12:30 · Answer 3 · 2020-12-25 12:30

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

1

Источник

user1124509 25 дек '20 в 12:30

user14756820 25 дек '20 в 12:40 2020-12-25 12:40 · Answer 4 · 2020-12-25 12:40

HashSet не гарантирует какой-либо порядок своих элементов. Если вам нужна эта гарантия, рассмотрите возможность использования TreeSet для хранения ваших элементов, но для достижения уникальности по ключу и поддержания постоянного переопределения времени. hashCode()а также equals()эффективно то, что вы ищете, как показано ниже:

      class Item {
    String key;
    double score;

    public Item(String key, double score) {
        this.key = key;
        this.score = score;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Item item = (Item) o;
        return key.equals(item.key);
    }

    @Override
    public int hashCode() {
        return Objects.hash(key);
    }

    @Override
    public String toString() {
        return "Item{" +
                "key='" + key + '\'' +
                ", score=" + score +
                '}';
    }
}

// main
public static void main(String[] args) {

        Set<Item> itemSet = new HashSet<>();

        itemSet.add(new Item("1", 1));
        itemSet.add(new Item("1", 2));
        itemSet.add(new Item("2", 1));

        //to get a sorted TreeSet
        //Add all your objects to the TreeSet, you will get a sorted Set.
        //TreeSet myTreeSet = new TreeSet();
        //myTreeSet.addAll(itemSet);
        //System.out.println(myTreeSet);
}

выход :

      Item{key='1', score=1.0}
Item{key='2', score=1.0}

user2345933 25 дек '20 в 12:36 2020-12-25 12:36 · Answer 5 · 2020-12-25 12:36

Допускается только один элемент с одним и тем же ключом (например, набор)

Ваш Itemкласс должен реализовать hashCode() и equals(), используя только keyатрибут.

вставлять, удалять, проверять наличие за постоянное время

add() и remove() равны O(ln N), поэтому они не соответствуют вашим критериям.

add() и remove() обычно равны O(1).

обход упорядочен по счету

Каковы ваши требования к производительности здесь? Как часто вы будете просматривать коллекцию? Если вы будете в основном добавлять и удалять элементы и редко перемещаться по ним, то вы можете сделать копию HashSetк TreeSetво время операции обхода.