Set that uniquely contains a key but ordered on different field

I'm looking for a Java collection, possibly in standard library, which is able to collect the following structure:

class Item {
    String key;
    double score;
}

And with the following properties:

• Only one Item with the same key is allowed (like a set)
• insert, remove, check existance in max O(logn)
• traversal ordered by score, finding next in max O(logn)

As far as I understood standard OrderedSet must have comparable interface coherent with equals() interface, but that is not my case as two items with different key may have the same score.

In fact I've notice that TreeSet uses the comparator returning 0 to check if the item is already present.

Any suggestion?

Now that insert has been relaxed to O(log n), you can do this with a double-set, i.e. implement your own set that maintains 2 sets behind the scenes.

Best would be if you can modify class Item to implement equals() and hashCode() to only use the key field. In that case your class would use a HashSet and a TreeSet. If hashCode() covers more than just the key field, then use two TreeSet objects.

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");
    }

}