Java在HashSet中找到最常见的值

Question

好的，这是一个基本问题，但我想知道解决这个问题的最佳方法是什么...

我有一个要向其中添加对象的 HashSet，.add() 方法只会添加一个对象（如果尚未添加）展示。但我想做的是添加所有对象，然后最后得到以下结果..

-唯一（不同）对象的数量
-物体的平均频率

有人能指出我正确的方向吗？

提前致谢

Answer 1

使用哈希映射。使用条目作为键，并将它们映射到整数以保留计数。

编辑：您可能想要包装 HashMap，以确保每次添加或删除对象时，计数器都会被适当修改。
让您开始：

class MapWrapper<Key>
{
    private Map<Key,Integer> map = new HashMap<Key, Integer>();

    void add( Key key )
    {
        Integer n = map.get( key );
        if ( n == null )
        {
            map.put( key, 1 );
        }
        else
        {
            map.put( key, new Integer( n + 1 ));
        }
    }

    int occurrences( Key k )
    {
        Integer n = map.get( k );
        if ( n == null )
        {
            return 0;
        }
        else
        {
            return n;
        }
    }
}

Answer 2

HashSet 并不适合跟踪个人计数，但 HashMap 几乎是完美的。

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

public class Count<K, V> extends HashMap<K, V> {

    // Counts unique objects
    public void add(K o) {
        int count = this.containsKey(o) ? ((Integer)this.get(o)).intValue() + 1 : 1;
        super.put(o, (V) new Integer(count));
    }

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

        Count<Object, Integer> c = new Count<Object, Integer>();

        String one = "one";
        String two = "two";
        String six = "six";

        c.add(one);
        c.add(two);
        c.add(two);
        c.add(six);
        c.add(six);
        c.add(six);

        System.out.println("Number of distinct objects: " + c.size());

        System.out.println("Frequency of different objects: ");

        for (Map.Entry<Object, Integer> entry : c.entrySet()) {
            System.out.println(entry.getKey() + " - " + entry.getValue());
        }
    }
}

运行时，这个独立的代码片段输出

Number of distinct objects - 3
Frequency of different objects:
two - 2
one - 1
six - 3

Answer 3

不同对象的数量将只是之后哈希集的大小。

根据“平均频率”的含义，您可能可以使用 source.size() / set.size()...（可能将其中一个操作数转换为 double 强制浮点运算（如果需要）。如果您可以通过一些示例详细说明您的需求，我们也许可以提供更多帮助。

Answer 4

Guava HashMultiset 是一个方便的工具选择。例如：

HashMultiset<String> multiSet = HashMultiset.create();
multiSet.add("a");
multiSet.add("a");
multiSet.add("b");

Assert.assertEquals(2, multiSet.count("a"));//count "a" 
Assert.assertEquals(3, multiSet.size());//set size
Assert.assertEquals(2, multiSet.elementSet().size());//unique (distinct) size 

Answer 5

您可以只使用 (Hash)Map，而不是将每个不同对象的计数保留为映射中的值，或者您可以继续使用集合，但在某处计算所有要添加的调用。

插入的对象总数要么是您计算的数量，要么是映射中所有值的总和（迭代 EntrySet）。不同对象的数量始终是地图/集合的 size() 和平均值。频率显然是商。

Answer 6

对于这种情况，我使用我自己的 Map 接口实现：

/*
* Providers easily work with maps of lists
* */
public interface ManyValuedMap<K, V> extends Cloneable, Map<K, List<V>>, Serializable{

    public List<V> put(K key, V... values);
    public void clear(K key);
    public ManyValuedMap<K, V> clone();
    public void sort(Comparator<? super V> c);
    public List<V> getAllValues();
    public Collection<List<V>> values(Comparator<? super K> c);
    public void lock();
    public Map<K, List<V>> toMap();

}

和实现：

/**
 * in ManyValuedMap can be stored lists of elements identificated by some key
 * */
public class ManyValuedHashMap<K, V> implements ManyValuedMap<K, V>, Serializable {

    //linked hash map guarantees right key order
    private Map<K, List<V>> map = new LinkedHashMap<K, List<V>>();
    private boolean isNeedToCheckUniqueness;
    private boolean lock = false;

    /**
     * @param needToCheckUniqueness if true then every time when element added uniqueness will be checked
     * */
    public ManyValuedHashMap(boolean needToCheckUniqueness) {
        isNeedToCheckUniqueness = needToCheckUniqueness;
    }

    public ManyValuedHashMap() {
        this(false);
    }

    public ManyValuedHashMap<K, V> put2 (K key, List<V> newValues ) {
        put(key, newValues);
        return this;
    }

    public List<V> put ( K key, List<V> newValues ) {
        if ( newValues == null ) {
            return put(key, (V)null);
        } else if ( newValues.isEmpty() ) {
            return put(key, (V)null);
        } else {
            //noinspection unchecked
            return put(key, (V[])newValues.toArray() );
        }
    }

    public List<V> put(K key, V... newValues) {
        checkLock();
        List<V> curValues = null;
        if (newValues != null && key != null) {
            curValues = this.map.get(key);

            if (curValues == null) {
                //new values  - add
                curValues = new ArrayList<V>();
                curValues.addAll(Arrays.asList(newValues));
                this.map.put(key, curValues);
            } else {
                // for this key values were added
                if (isNeedToCheckUniqueness) {
                    //if is need to check uniqueness - check
                    Integer index;
                    for (V newValue : newValues) {
                        index = null;
                        for (int i = 0; i < curValues.size(); i++) {
                            if (curValues.get(i).equals(newValue)) {
                                index = i;
                                break;
                            }
                        }
                        if (index == null) {
                            curValues.add(newValue);
                        } /*else {
                            //no need to add
                            //this value is already stored in map
                        }*/
                    }
                } else {
                    //otherwise add
                    curValues.addAll(Arrays.asList(newValues));
                }
            }
        } else if (key != null) {
            curValues = this.map.get(key);

            if (curValues == null) {
                curValues = new ArrayList<V>();
                this.map.put(key, curValues);
            }
        }

        return curValues;
    }

    public boolean containsValue(Object value) {
        boolean result = false;
        for (List<V> values : this.map.values()) {
            for (V v : values) {
                if (v.equals(value)) {
                    result = true;
                    break;
                }
            }
            if (result) {
                break;
            }
        }
        return result;
    }

    public List<V> get(Object key) {
        return this.map.get(key);
    }

    public boolean containsKey(Object key) {
        return this.map.containsKey(key);
    }

    public boolean isEmpty() {
        return this.map.isEmpty();
    }

    public int size() {
        int size = 0;
        for (List<V> vs : map.values()) {
            size += vs.size();
        }
        return size;
    }

    public List<V> remove(Object key) {
        checkLock();
        return this.map.remove(key);
    }

    @Override
    public void putAll(Map<? extends K, ? extends List<V>> m) {
        checkLock();
        this.map.putAll(m);
    }

    public void clear() {
        checkLock();
        this.map.clear();
    }

    @Override
    public void clear(K key) {
        checkLock();
        List<V> curValues = this.map.get(key);
        if ( curValues != null ) {
            curValues.clear();
        }
    }

    public Set<K> keySet() {
        return this.map.keySet();
    }

    public Collection<List<V>> values() {
        return this.map.values();
    }

    public Set<Map.Entry<K, List<V>>> entrySet() {
        return this.map.entrySet();
    }

    public Map<K, List<V>> toMap() {
        return new HashMap<K, List<V>>(map);
    }

    @Override
    public ManyValuedHashMap<K, V> clone() {
        ManyValuedHashMap<K, V> clone = null;
        try {
            //noinspection unchecked
            clone = (ManyValuedHashMap<K, V>)super.clone();
            //IMPORTANT: NOT DEEP CLONE
            //noinspection unchecked
            clone.map = new LinkedHashMap<K, List<V>>();
            clone.map.putAll(this.map);
        } catch (CloneNotSupportedException e) {
            Logger.getLogger(this.getClass()).error(e.getMessage(), e);
        }
        return clone;
    }

    @Override
    public void sort(Comparator<? super V> c) {
        for (List<V> list : map.values()) {
            Collections.sort(list, c);
        }
    }

    @Override
    public List<V> getAllValues() {
        final List<V> result = new ArrayList<V>();
        for (List<V> list : map.values()) {
            result.addAll(list);
        }
        return result;
    }

    public Collection<List<V>> values(Comparator<? super K> c) {
        List<Map.Entry<K, List<V>>> entries = new ArrayList<Map.Entry<K, List<V>>>(entrySet());

        Collections.sort(entries, new EntryComparator(c));

        Collection<List<V>> result = new ArrayList<List<V>>();

        for (Map.Entry<K, List<V>> entry : entries) {
            result.add(entry.getValue());
        }

        return result;
    }

    private class EntryComparator implements Comparator<Map.Entry<K, List<V>>>{

        private Comparator<? super K> keyComparator = null;

        private EntryComparator(Comparator<? super K> keyComparator) {
            this.keyComparator = keyComparator;
        }

        @Override
        public int compare(Map.Entry<K, List<V>> o1, Map.Entry<K, List<V>> o2) {
            return keyComparator.compare(o1.getKey(), o2.getKey());
        }
    }

    @Override
    public void lock() {
        this.lock = true;
    }

    private void checkLock () {
        if ( this.lock ) {
            throw new UnsupportedOperationException();
        }
    }
}

行为如下：

1. 列表项
2. 如果您尝试使用地图中未出现的键添加值，则将创建新的列表元素并将其存储在具有指定键（值）的地图中当然会被添加到列表中）
3. 如果键已经在映射中，则：如果 isNeedToCheckUniqueness == false 新值将被添加到列表的末尾，否则（ isNeedToCheckUniqueness == true）值将仅在以下情况下添加到列表中如果列出尚未包含它。

您可以通过获取列表的大小轻松地按键（频率）计算元素的数量。
您可以获取列表的第一个或最后一个元素，以便获取具有指定键的第一个或最后一个添加值。