java - Java ListSet 某处？

Question

寻找一个插入顺序集合，该集合还允许高效查询和位置子集视图（如子列表）。似乎最直接的选择是采用 List 的链表方法，将节点嵌入为映射值，并在类上公开部分或全部列表接口。

有人会为此向甲骨文抱怨吗？为排序的地图和集合添加了 NavigableMap/Set 并且没有更常见的插入顺序等价物......

编辑：请不要建议 LinkedHashSet - 它没有任何方法可以查询位置或做一个相对子集。

Answer 1

你的意思是像java.util.LinkedHashSet：

Set 接口的哈希表和链表实现，具有可预测的迭代顺序。此实现与 HashSet 的不同之处在于它维护一个双向链表，该列表贯穿其所有条目。该链表定义了迭代顺序，即元素插入集合的顺序（插入顺序）。请注意，如果将元素重新插入集合中，则插入顺序不受影响。（如果 s.add(e) 被调用，而 s.contains(e) 将在调用之前立即返回 true，则元素 e 被重新插入到集合 s 中。）

Answer 2

编辑2：新的最终版本这是一个仅适用于功能稍有调整的集合的版本（分为两部分，不再接受 null 作为“地图的开始”），可能有更少的错误

public class LinkedSet<E> implements Set<E> {

private LinkedHashMap<E, Integer> m = new LinkedHashMap<E, Integer>();
private int monoticallyIncreasing;

/**
 * Returns true if the value target was added before (exclusive)
 * limitElem in insertion order.
 *
 * If target or limit are not present on the set this method returns false
 *
 * @param limitElem a E that may be a element of the set or not.
 * @return if target was added before limit (can be reset by removing and
 * re-adding the target, that changes iteration order).
 */
public boolean containsBefore(E target, E limitElem) {
    if (isEmpty()) {
        return false;
    }

    Integer targetN = m.get(target);
    if (targetN == null) {
        return false;
    }

    Integer highN = m.get(limitElem);
    if (highN == null) {
        return false;
    }
    return targetN < highN;
}

/**
 * Returns true if the value target was added after (exclusive)
 * previousElem in insertion order.
 *
 * If target or previous are not present on the set this method returns false
 *
 * @param previousElem a E that may be a element of the set or not.
 * @return if target was added before previous (can be reset by removing and
 * re-adding the target, that changes iteration order).
 */
public boolean containsAfter(E target, E previousElem) {
    if (isEmpty()) {
        return false;
    }

    Integer targetN = m.get(target);
    if (targetN == null) {
        return false;
    }

    Integer low = m.get(previousElem);
    if (low == null) {
        return false;
    }
    return low < targetN;
}

@Override
public boolean add(E e) {
    Integer pos = m.get(e);
    if (pos == null) {
        m.put(e, monoticallyIncreasing++);
        return true;
    }
    return false;
}

@Override
public int size() {
    return m.size();
}

@Override
public boolean isEmpty() {
    return m.isEmpty();
}

@Override
public boolean contains(Object o) {
    return m.containsKey(o);
}

@Override
public Object[] toArray() {
    Object[] result = new Object[size()];
    int i = 0;
    for (E e : this) {
        result[i++] = e;
    }
    return result;
}

@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    int size = size();
    if (a.length < size) {
        a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
    }
    int i = 0;
    Object[] result = a;
    for (E e : this) {
        result[i++] = e;
    }
    if (a.length > size) {
        //peculiar toArray contract where it doesn't care about the rest
        a[size] = null;
    }
    return a;
}

@Override
public boolean remove(Object o) {
    return m.remove(o) != null;
}

@Override
public boolean addAll(Collection<? extends E> c) {
    boolean changed = false;
    for (E e : c) {
        changed |= add(e);
    }
    return changed;
}

@Override
public boolean containsAll(Collection<?> c) {
    return m.keySet().containsAll(c);
}

@Override
public boolean retainAll(Collection<?> c) {
    return m.keySet().retainAll(c);
}

@Override
public boolean removeAll(Collection<?> c) {
    return m.keySet().removeAll(c);
}

@Override
public void clear() {
    m.clear();
}

@Override
public Iterator<E> iterator() {
    return m.keySet().iterator();
}
}