按值实时排序、自动丢弃、有界集合 ?

Question

我花了一些时间尝试制作一个集合：
1) 按值排序（而不是按键排序）
2) 每次添加或修改元素时都会排序
3）是固定大小并根据排序方式自动丢弃最小/最大元素
4）是安全线程

所以3）和4）我认为这是相当好的。对于 1) 和 2) 来说有点棘手。我在这个线程上花了很长时间< /a>，尝试不同的示例，但一个大问题是插入对象时集合仅排序一次。

不管怎样，我尝试实现我自己的集合，它正在工作（不应该用于大量数据，因为它经常排序），但我对设计不太满意。特别是事实上，我的值对象被限制为可观察的（这很好）但不可比较，所以我不得不为此使用一个脏的实例+异常。

有什么建议可以改进这个吗？

这是代码：

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Observable;
    import java.util.Observer;

    public class SortedDiscardingSyncArray<K, V extends Observable> implements Observer {

        // Comparison way (ascendent or descendant)
        public static enum ComparisonWay
        {
            DESC,
            ASC;
        }

        // this is backed by a List (and ArrayList impl)
        private List<ArrayElement> array;

        // Capacity, configurable, over this limit, an item will be discarded
        private int MAX_CAPACITY = 200;

        // default is descending comparison
        private ComparisonWay compareWay = ComparisonWay.DESC;

        public SortedDiscardingSyncArray(ComparisonWay compareWay, int mAX_CAPACITY) {
            super();
            this.compareWay = compareWay;
            MAX_CAPACITY = mAX_CAPACITY;
            array = new ArrayList <ArrayElement>(MAX_CAPACITY);
        }

        public SortedDiscardingSyncArray(int mAX_CAPACITY) {
            super();
            MAX_CAPACITY = mAX_CAPACITY;
            array = new ArrayList<ArrayElement>(MAX_CAPACITY);
        }

        public SortedDiscardingSyncArray() {
            super();
            array = new ArrayList <ArrayElement>(MAX_CAPACITY);
        }

        public boolean put(K key, V value)
        {
            try {
                return put (new ArrayElement(key, value, this));
            } catch (Exception e) {
                e.printStackTrace();
                return false;
            } 
            finally
            {
                sortArray();
            }

        }

        private synchronized boolean put(ArrayElement ae)
        {
            if (array.size() < MAX_CAPACITY)
            {
                return array.add(ae);
            }
            // check if last one is greater/smaller than current value to insert
            else if (ae.compareTo(array.get(MAX_CAPACITY-1)) < 0)
            {
                array.remove(MAX_CAPACITY - 1);
                return array.add(ae);
            }
            // else we don't insert
            return false;
        }

        public V getValue (int index)
        {
            return array.get(index).getValue();
        }

        public V getValue (K key)
        {
            for (ArrayElement ae : array)
            {
                if (ae.getKey().equals(key)) return ae.getValue();
            }
            return null;
        }

        public K getKey (int index)
        {
            return array.get(index).getKey();
        }

        private void sortArray()
        {
            Collections.sort(array);
        }

        public synchronized void setValue(K key, V newValue) {
            for (ArrayElement ae : array)
            {
                if (ae.getKey().equals(key)) 
                {
                    ae.setValue(newValue);
                    return;
                }
            }
        }
        public int size() {
            return array.size();
        }

        @Override
        public void update(java.util.Observable arg0, Object arg1) {
            sortArray();        
        }

        public static void main(String[] args) {

            //  some test on the class
            SortedDiscardingSyncArray<String, ObservableSample> myData = new SortedDiscardingSyncArray<String, ObservableSample>(ComparisonWay.DESC, 20);

            String Ka = "Ka";
            String Kb = "Kb";
            String Kc = "Kc";
            String Kd = "Kd";
            myData.put(Ka, new ObservableSample(0));
            myData.put(Kb, new ObservableSample(3));
            myData.put(Kc, new ObservableSample(1));
            myData.put(Kd, new ObservableSample(2));


            for (int i=0; i < myData.size(); i++)
            {
                System.out.println(myData.getKey(i).toString() + " - " + myData.getValue(i).toString());
            }
            System.out.println("Modifying data...");
            myData.getValue(Kb).setValue(12);
            myData.getValue(Ka).setValue(34);
            myData.getValue(Kd).setValue(9);
            myData.getValue(Kc).setValue(19);
            for (int i=0; i < myData.size(); i++)
            {
                System.out.println(myData.getKey(i).toString() + " - " + myData.getValue(i).toString());
            }
        }

        private class ArrayElement implements Comparable <ArrayElement> {

            public ArrayElement(K key, V value, Observer obs) throws Exception {
                super();
                // don't know how to handle that case
                // maybe multiple inheritance would have helped here ?
                if (! (value instanceof Comparable)) throw new Exception("Object must be 'Comparable'");
                this.key = key;
                this.value = value;
                value.addObserver(obs);
            }

            public String toString()
            {
                StringBuffer sb = new StringBuffer();
                sb.append(key);
                sb.append(" - ");
                sb.append(value);
                return sb.toString();
            }

            private K key;
            private V value;

            public K getKey() {
                return key;
            }

            public V getValue() {
                return value;
            }

            public synchronized void setValue(V value) {
                this.value = value;
            }

            @SuppressWarnings("unchecked")
            @Override
            public int compareTo(ArrayElement o) {

                int c;
                if (compareWay == ComparisonWay.DESC) c = ((Comparable<V>) o.getValue()).compareTo(this.getValue());
                else c = ((Comparable<V>) this.getValue()).compareTo(o.getValue());
                if (c != 0) {
                    return c;
                }
                Integer hashCode1 = o.getValue().hashCode();
                Integer hashCode2 = this.getValue().hashCode();
                // we don't check the compare way for hash code (useless ?)
                return hashCode1.compareTo(hashCode2);
            }

        }
    }

另一个用于测试目的的类：

    import java.util.Observable;

    public class ObservableSample extends Observable implements Comparable <ObservableSample>
    {
        private Integer value = 0;

        public ObservableSample(int value) {
            this.value = value;
            setChanged();   
            notifyObservers();
        }

        public String toString()
        {
            return String.valueOf(this.value);
        }

        public void setValue(Integer value) {
            this.value = value;
            setChanged();   
            notifyObservers();
        }

        public Integer getValue() {
            return value;
        }

        @Override
        public int compareTo(ObservableSample o) {
            int c;
            c = (this.getValue()).compareTo(o.getValue());
            if (c != 0) {
                return c;
            }
            Integer hashCode1 = o.getValue().hashCode();
            Integer hashCode2 = this.getValue().hashCode();
            // we don't check the compare way for hash code (useless ?)
            return hashCode1.compareTo(hashCode2);
        }
    }

Answer 1

集合很难编写，也许您应该寻找现有的实现。

尝试查看 ImmutableSortedSet番石榴。

Answer 2

您可以有一个标记接口

public interface ComparableObservable extends Observable, Comparable {
}

，然后更改

SortedDiscardingSyncArray<K, V extends Observable>

为

SortedDiscardingSyncArray<K, V extends ComparableObservable>

避免显式强制转换。

除此之外，代码非常冗长，我没有完全遵循它。我还建议您查看 guava 或（apache）commons-collections 库来探索是否可以找到可重用的东西。

Answer 3

您可以编写具有多个边界的通用通配符。因此，将 声明更改为 > 然后您可以将 V 视为实现了两个接口，而没有空且无用的接口。

另外几件事：选择一个命名约定，并坚持下去。我使用的名称是诸如 MAX_CAPACITY 之类的名称，该名称将用于静态最终字段（即常量，例如默认值），并且等效的实例字段将用于maxCapacity 诸如 max_CAPACITY 之类的名称是不可能的。

请参阅：Oracle 的 Java 命名约定

而不是使用 ComparisonWay 枚举，我会采用自定义的Comparator。更加灵活，并且不会复制已经存在的东西。

请参阅：比较器 API 文档

您的代码，正如所写，不是线程安全的。特别是，调用不同步的 update 方法的被观察元素可能因此调用 sortArray 而没有获得正确的锁。 FindBugs 是一个很棒的工具，可以捕获很多这样的问题。

您的 ObservableSample 在如何实现 Comparable 方面并未真正遵循良好实践，因为它并不真正比较数据值，而是比较 hashCode。 hashCode 本质上是任意的，并且很可能发生冲突。此外，Comparable 接口通常要求您应该“与 Equals 一致”，为此您可能还需要查看 Object 类的 equals 方法的文档

是的，这听起来像很多工作，但如果您仔细阅读并正确执行，您将在以后节省大量的调试工作。如果您没有正确执行这些操作并符合规范，您会发现当您将其放入 Set 或 Map 中时，您的键或值会奇怪地消失、重新出现或被重创。这可能取决于您运行的 Java 版本！

Answer 4

这是更新的版本。仍然不完全确定它是安全线程，但 findbugs 工具没有给出如此有用的提示。另外对于比较方式，我不想限制用户开发自己的比较器，我想让事情保持简单。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Observable;
import java.util.Observer;

public class SortedDiscardingSyncArray<K, V extends Observable & Comparable<V>> implements Observer {

    // Comparison way (ascendent or descendant)
    public static enum ComparisonWay { DESC, ASC; }

    // this is backed by a List (and ArrayList)
    private List<ArrayElement> array;

    // Capacity, configurable, over this limit, an item will be discarded
    private int maxCapacity = 200;

    // default is descending comparison
    private ComparisonWay compareWay = ComparisonWay.DESC;

    public SortedDiscardingSyncArray(ComparisonWay compareWay, int maxCapacity) {
        super();
        this.compareWay = compareWay;
        this.maxCapacity = maxCapacity;
        array = new ArrayList <ArrayElement>(maxCapacity);
    }

    public SortedDiscardingSyncArray(int maxCapacity) {
        super();
        this.maxCapacity = maxCapacity;
        array = new ArrayList<ArrayElement>(maxCapacity);
    }

    public SortedDiscardingSyncArray() {
        super();
        array = new ArrayList <ArrayElement>(maxCapacity);
    }

    // not synchronized, but calling internal sync put command
    public boolean put(K key, V value)
    {
        try {
            return put (new ArrayElement(key, value, this));
        } catch (Exception e) {
            e.printStackTrace();
            return false;
        } 
        finally
        {
            sortArray();
        }
    }

    private synchronized boolean put(ArrayElement ae)
    {
        if (array.size() < maxCapacity) return array.add(ae);
        // check if last one is greater/smaller than current value to insert
        else if (ae.compareTo(array.get(maxCapacity-1)) < 0)
        {
            array.remove(maxCapacity - 1);
            return array.add(ae);
        }
        // else we don't insert and return false
        return false;
    }

    public V getValue (int index)
    {
        return array.get(index).getValue();
    }

    public V getValue (K key)
    {
        for (ArrayElement ae : array)
        {
            if (ae.getKey().equals(key)) return ae.getValue();
        }
        return null;
    }

    public K getKey (int index)
    {
        return array.get(index).getKey();
    }

    private synchronized void sortArray()
    {
        Collections.sort(array);
    }

    public synchronized void setValue(K key, V newValue) {
        for (ArrayElement ae : array)
        {
            if (ae.getKey().equals(key)) 
            {
                ae.setValue(newValue);
                return;
            }
        }
    }

    public int size() {
        return array.size();
    }

    @Override
    public void update(java.util.Observable arg0, Object arg1) {
        sortArray();        
    }

    public static void main(String[] args) {
        //  some test on the class
        SortedDiscardingSyncArray<String, ObservableSample> myData = new SortedDiscardingSyncArray<String, ObservableSample>(ComparisonWay.DESC, 20);

        String Ka = "Ka";
        String Kb = "Kb";
        String Kc = "Kc";
        String Kd = "Kd";
        myData.put(Ka, new ObservableSample(0));
        myData.put(Kb, new ObservableSample(3));
        myData.put(Kc, new ObservableSample(1));
        myData.put(Kd, new ObservableSample(2));


        for (int i=0; i < myData.size(); i++)
        {
            System.out.println(myData.getKey(i).toString() + " - " + myData.getValue(i).toString());
        }
        System.out.println("Modifying data...");
        myData.getValue(Kb).setValue(12);
        myData.getValue(Ka).setValue(34);
        myData.getValue(Kd).setValue(9);
        myData.getValue(Kc).setValue(19);
        for (int i=0; i < myData.size(); i++)
        {
            System.out.println(myData.getKey(i).toString() + " - " + myData.getValue(i).toString());
        }
    }

    private class ArrayElement implements Comparable <ArrayElement> {

        public ArrayElement(K key, V value, Observer obs) throws Exception {
            super();
            this.key = key;
            this.value = value;
            value.addObserver(obs);
        }

        public String toString()
        {
            StringBuffer sb = new StringBuffer();
            sb.append(key);
            sb.append(" - ");
            sb.append(value);
            return sb.toString();
        }

        private K key;
        private V value;

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public synchronized void setValue(V value) {
            this.value = value;
        }

        @Override
        public int compareTo(ArrayElement o) {

            int c;
            if (compareWay == ComparisonWay.DESC) c = o.getValue().compareTo(this.getValue());
            else c = this.getValue().compareTo(o.getValue());
            if (c != 0) {
                return c;
            }
            Integer hashCode1 = o.getValue().hashCode();
            Integer hashCode2 = this.getValue().hashCode();
            // we don't check the compare way for hash code (useless ?)
            return hashCode1.compareTo(hashCode2);
        }

    }
}