Immutable集合作为Guava提供的集合类型,并没有脱离集合的接口,例如ImmutableList依然实现List接口。但接下来几章要分析的Multi Collections则几乎脱离了JAVA原本所带的集合(这也是为什么Multixxx,代表集合数据结构的单词为小写),作为了JAVA集合的一个补充。
对于Map<T,Integer>这样的Map结构,会经常被使用到,而我们统计T出现的次数的时候,大多时候进行的操作遍历统计,代码如下所示:
Map<String, Integer> counts = new HashMap<String, Integer>(); for (String word : words) { Integer count = counts.get(word); if (count == null) { counts.put(word, 1); } else { counts.put(word, count + 1); } }
而使用MultiSet实现,代码则变为:
Multiset<String> sets = HashMultiset.create();
for (String word : words) { sets.add(word); } int count = sets.count("word");
简单使用就介绍到这,具体的API使用可以去参照API文档,接下来,来说说Multiset的实现,UML图如下所示:
在UML图,加入了HashSet的继承体系来说明,Multiset是一种新的集合,并不是AbsTractSet的子类(不是一种Set),MultiSet接口,在Collection的基础上扩展出对重复元素处理的方法,例如:int count(Object element)、int add(@Nullable E element, int occurrences)方法(见名知意,就不多说了)。
HashMultiset是最常用的,起实现是以Map<T,Count>为存储结构,其中的add和remove方法是对Count进行的操作( Count并不是线程安全的 ),Multiset与Map<T,Integer>最大的不同是,Multiset遍历时可以遍历出Map.keySize * count个元素,而map却不可以,最大的区别就在于其itertator和Entry<T,Count>的iterator实现代码如下:
private class MapBasedMultisetIterator implements Iterator<E> { final Iterator<Map.Entry<E, Count>> entryIterator; Map.Entry<E, Count> currentEntry; int occurrencesLeft;//元素个数的剩余,用来判断是够移动迭代器指针 boolean canRemove; MapBasedMultisetIterator() { this.entryIterator = backingMap.entrySet().iterator(); } @Override public boolean hasNext() { return occurrencesLeft > 0 || entryIterator.hasNext(); } @Override public E next() { if (occurrencesLeft == 0) {//如果为0,则移动迭代器指针 currentEntry = entryIterator.next(); occurrencesLeft = currentEntry.getValue().get(); } occurrencesLeft--; canRemove = true; return currentEntry.getKey(); } @Override public void remove() { checkRemove(canRemove); int frequency = currentEntry.getValue().get(); if (frequency <= 0) { throw new ConcurrentModificationException(); } if (currentEntry.getValue().addAndGet(-1) == 0) { entryIterator.remove(); } size--; canRemove = false; } }
而Multiset.Entry<E>,实现被map的entryset代理的同时,加入了getCount()操作,并且支持remove和clear,代码如下:
Iterator<Entry<E>> entryIterator() { final Iterator<Map.Entry<E, Count>> backingEntries = backingMap.entrySet().iterator();//被map代理 return new Iterator<Multiset.Entry<E>>() { Map.Entry<E, Count> toRemove; @Override public boolean hasNext() { return backingEntries.hasNext(); } @Override public Multiset.Entry<E> next() { final Map.Entry<E, Count> mapEntry = backingEntries.next(); toRemove = mapEntry; return new Multisets.AbstractEntry<E>() { @Override public E getElement() { return mapEntry.getKey(); } //getcount操作 @Override public int getCount() { Count count = mapEntry.getValue(); if (count == null || count.get() == 0) { Count frequency = backingMap.get(getElement()); if (frequency != null) { return frequency.get(); } } return (count == null) ? 0 : count.get(); } }; } @Override public void remove() { checkRemove(toRemove != null);//在next的时候记录元素,可以被remove size -= toRemove.getValue().getAndSet(0); backingEntries.remove(); toRemove = null; } }; }
Multiset整体来说是个很好用的集合,而且实现巧妙,一种元素并没有被存多分,而且巧妙的利用iterator指针来模拟多分数据。