12

我有一个 ArrayList 填充有属性名称和时间的对象。我想根据名称删除重复项并仅保留最新时间的记录。所以我在我的对象中覆盖了equals和hashcodefor name 并使用了这样的代码。

private List<ChangedRecentlyTO> groupRecords(List<ChangedRecentlyTO> toList) {
    changedRecentlyList.clear(); //static list
    for(ChangedRecentlyTO to : toList) {
        if(!changedRecentlyList.contains(to)) {
            changedRecentlyList.add(to);
        } else {
            if(changedRecentlyList.get(changedRecentlyList.lastIndexOf(to)).getTimeChanged().before(to.getTimeChanged())) {
                changedRecentlyList.remove(to);
                changedRecentlyList.add(to);
            }
        }
    }
    return changedRecentlyList;
}

但我想知道，有没有更好的解决方案？我正在考虑使用 Set 但我无法弄清楚我应该如何将时间标准放在那里。

4

7 回答 7

5

仅当新对象比现有对象更新时，扩展HashMap和覆盖方法才放置。put

或者，您可以创建自己的专用容器，该容器将由 a 支持HashMap，就像 的某些实现Stack由LinkedList

这是一个模拟代码：

import java.util.HashMap;
import java.util.Map;

public class TimeMap<K, V> {

    private Map<K, V> timeMap;

    public TimeMap() {
        this.timeMap = new HashMap<K, V>();
    }

    public void put(K key, V value) {
        if (isNewer(key, value)) {
            this.timeMap.put(key, value);
        }
    }

}
于 2012-07-12T08:57:33.817 回答
5

你有两种方法，一种需要了解集合是如何工作的，另一种对于对 Java 集合了解较少的人来说更容易理解：

如果你想让它简单，你可以简单地阅读Set的Javadoc，http: //docs.oracle.com/javase/6/docs/api/java/util/Set.html#add(E ) . 它明确指出，如果一个元素已经在其中，则不会再次添加它。

  • 您仅使用名称来实现您的等号和哈希码
  • 您按时间对项目进行排序，然后将它们添加到集合中。

这样，第一次将项目添加到 Set 时，您将添加具有最新时间的元素。当您添加其他人时，它们将被忽略，因为它们已经包含在内。

如果不确切知道 java.util.Set 契约的其他人的行为，您可能希望扩展 Set 以使您的意图更清晰。但是，由于不应该访问 Set 以“在删除后取回元素”，因此您需要使用 HashMap 支持您的集合：

interface TimeChangeable {
   long getTimeChanged();
}
public class TimeChangeableSet<E extends TimeCheangeable> implements Set<E> {

    private final HashMap<Integer,E> hashMap = new HashMap<Integer,E>();

    @Override
    public boolean add(E e) {
        E existingValue = hashMap.remove(e.hashCode());
        if(existingValue==null){
            hashMap.put(e.hashCode(),e);
            return true;
        }
        else{
            E toAdd = e.getTimeChanged() > existingValue.getTimeChanged() ? e : existingValue;
            boolean newAdded = e.getTimeChanged() > existingValue.getTimeChanged() ? true : false;
            hashMap.put(e.hashCode(),e);
            return newAdded;
        }

    }

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

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

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

    @Override
    public Iterator<E> iterator() {
        return hashMap.values().iterator();
    }

    @Override
    public Object[] toArray() {
        return hashMap.values().toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return hashMap.values().toArray(a);
    }

    @Override
    public boolean remove(Object o) {
        return removeAndGet(o)!=null ? true : false;
    }

    public E removeAndGet (Object o) {
        return hashMap.remove(o.hashCode());
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        boolean containsAll = true;
        for(Object object:c){
            E objectInMap = removeAndGet(object);
            if(objectInMap==null || !objectInMap.equals(object))
                containsAll=false;
        }
        return containsAll;
    }

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

    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean setChanged=false;
        for(E e: hashMap.values()){
            if(!c.contains(e)){
                hashMap.remove(e.hashCode());
                setChanged=true;
            }
        }
        return setChanged;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException("Please do not use type-unsafe methods in 2012");
    }

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




}
于 2012-07-12T09:28:26.853 回答
2

为什么不使用Set及更高版本：

new ArrayList(set);
于 2012-07-12T08:53:54.103 回答
2

一个非常快速的实现我的想法。

假设ChangedRecentlyTO对象有一个name属性。

private List<ChangedRecentlyTO> groupRecords(List<ChangedRecentlyTO> toList) {

    Map<String, ChangedRecentlyTO> uniqueMap = new HashMap<String, ChangedRecentlyTO>();

    for(ChangedRecentlyTO to : toList) {
        if (uniqueMap.containsKey(to.getName())) {
            if (uniqueMap.get(to.getName()).getTimeChanged().before(to.getTimeChanged())) {
                uniqueMap.put(to.getName(), to);
            }
        } else {
            uniqueMap.put(to.getName(), to);
        }
    }
    return (List<ChangedRecentlyTO>) uniqueMap.values();
}

毕竟，它似乎与您的原始实现没有什么不同，除了不需要覆盖hashcode和equals.

于 2012-07-12T10:17:59.307 回答
1

我的建议是，Comparable通过实现Comparable 接口来创建你的类。comparetTo()然后根据名称和时间比较它们，如果对象时间是最近的，则返回 1，否则 0（如果相等）或 -1。一旦你有了这个功能，你就可以扩展HashMap类和覆盖put方法之类的。

o1.compareTo(o2) > 0 then simply overwrite the object with latest one.

向@Lopina 代码添加逻辑，例如 

public class MyHashMap extends HashMap<String, MyClass>{
private Map<String, MyClass> timeMap;

public MyHashMap() {
    this.timeMap = new HashMap<String, MyClass>();
}

public MyClass put(String key, MyClass value) {

    MyClass obj;
    if (isNewer(key, value)) {
        System.out.println("count");
        obj=this.timeMap.put(key, value);
    }else{
        obj=value;
    }
    return obj;
}

private boolean isNewer(String key, MyClass value) {

    if(this.timeMap.get(key)==null ||( key.equals(value.getName()))&& (this.timeMap.get(key).compareTo(value))<0)
        return true;
    else
        return false;
}

@Override
public int size() {

    return this.timeMap.size();
}

@Override
public MyClass get(Object key) {

    return this.timeMap.get(key);
}
}

在 MyClass 中实现类似的接口和覆盖compareTo方法，如下所示。

@Override
public int compareTo(MyClass o) {

    return this.getTime().compareTo(o.getTime());
}
于 2012-07-12T09:11:21.713 回答
1

您可以让您的类实现Comparable接口并比较检查您感兴趣的时间戳。如果您然后对其进行排序（例如将所有元素放在 a 中TreeSet）然后将它们一一取出，前提是它们尚不存在. 像这样的东西：

public void removeDuplicates(List<MyObject> list){
    SortedSet<MyObject> sortedSet = new TreeSet<MyObject>();
    sortedSet.addAll(list);

    //Now clear the list, and start adding them again
    list.clear();
    for(MyObject obj : sortedSet){
        if(!list.contains(obj) {
             list.add(obj);
        } 
    }
    return list;
}

但是，这仅在具有不同时间戳的两个对象不相等时才有效！（在equals()这个词的意义上

于 2012-07-12T09:16:16.347 回答
1

我编写了一个UniqueList扩展 ArrayList 以支持其数据并利用 aHashSet有效拒绝重复的类。这为手动扫描数据集提供了 O(1) 随机访问时间和许多其他速度改进。

https://gist.github.com/hopesenddreams/80730eaafdfe816ddbb1

public class UniqueList<T> extends ArrayList<T> implements Set<T>
{
    HashMap<T,Integer> hash; // T -> int

    public UniqueList()
    {
        hash = new HashMap<>();
    }

    /*
    * O(n)
    * */
    @Override
    public void add(int location, T object)
    {
        super.add(location, object);
        for( int i = location ; i < size() ; i++ )
        {
            hash.put(get(i),i);
        }
    }

    /*
    * O(1) amortized.
    * */
    @Override
    public boolean add(T object) {
        if( hash.containsKey(object) ) return false;

        hash.put(object, size());
        super.add(object);

        return true;
    }

    /*
    * O(MAX(collection.size(),n)) because of the hash-value-shift afterwards.
    * */
    @Override
    public boolean addAll(int location, Collection<? extends T> collection) {
        boolean bChanged = false;
        for( T t : collection)
        {
            if( ! hash.containsKey( t ) )
            {
                hash.put(t, size());
                super.add(t);
                bChanged = true;
            }
        }

        for( int i = location + collection.size() ; i < size() ; i ++ )
        {
            hash.put( get(i) , i );
        }

        return bChanged;
    }

    /*
    * O(collection.size())
    * */
    @Override
    public boolean addAll(Collection<? extends T> collection) {
        boolean bChanged = false;
        for( T t : collection)
        {
            if( ! hash.containsKey( t ) )
            {
                hash.put( t , size() );
                super.add(t);
                bChanged = true;
            }
        }
        return bChanged;
    }

    /*
    * O(n)
    * */
    @Override
    public void clear() {
        hash.clear();
        super.clear();
    }

    /*
    * O(1)
    * */
    @Override
    public boolean contains(Object object) {
        return hash.containsKey(object);
    }

    /*
    * O(collection.size())
    * */
    @Override
    public boolean containsAll(Collection<?> collection) {
        boolean bContainsAll = true;
        for( Object c : collection ) bContainsAll &= hash.containsKey(c);
        return bContainsAll;
    }

    /*
    * O(1)
    * */
    @Override
    public int indexOf(Object object) {
        //noinspection SuspiciousMethodCalls
        Integer index = hash.get(object);
        return index!=null?index:-1;
    }

    /*
    * O(1)
    * */
    @Override
    public int lastIndexOf(Object object)
    {
        return hash.get(object);
    }

    /*
    * O(n) because of the ArrayList.remove and hash adjustment
    * */
    @Override
    public T remove(int location) {
        T t = super.remove(location);
        hash.remove( t );
        for( int i = size() - 1 ; i >= location  ; i -- )
        {
            hash.put( get(i) , i );
        }
        return t;
    }

    /*
    * O(n) because of the ArrayList.remove and hash adjustment
    * */
    @Override
    public boolean remove(Object object) {
        Integer i = hash.get( object );
        if( i == null ) return false;
        remove( i.intValue() );
        return true;
    }



  /*
    * O( MAX( collection.size() , ArrayList.removeAll(collection) ) )
    * */
    @Override
    public boolean removeAll(@NonNull Collection<?> collection) {
        for( Object c : collection )
        {
            hash.remove( c );
        }
        return super.removeAll( collection );
    }
}
于 2015-10-02T11:50:34.797 回答