java - 通过 EntrySet() 进行迭代不会创建太多 Map.Entry 实例吗？

Question

我不确定 HashMap 或 TreeMap 本身是否存储 Map.Entry 。也就是说，当调用 entrySet().iterator().next() 时，它可能会返回动态创建的 Map.Entry 实例。

我个人认为这种形式可能会更好:

class Entry {
    Object key;
    Object value;
}

interface InplaceIterator {
    boolean next();
}

Entry entryBuf = new Entry();
InplaceIterator it = map.entrySet().inplaceIterator(entryBuf);
while (it.next()) {
    // do with entryBuf...
}

因此，避免了 Entry 的创建。

我不知道Java编译器是如何工作的，Java编译器会通过分析数据流来优化Map.Entry的创建并了解Map.Entry可以安全地重用吗？

或者，有人已经编写了另一个集合框架来启用就地迭代吗？

Answer 1

您所描述的(具有迭代器本地 Map.Entry 对象并将其重用于所有 next() 返回值)是一种可能的 Map 实现，我认为一些特殊用途的 map 正在使用它。

例如执行EnumMap.entrySet().iterator() (这里是 OpenJDK 的版本，1.6.0_20)简单地使用迭代器对象本身作为 next() 返回的 Entry 对象。方法:

/**
 * Since we don't use Entry objects, we use the Iterator itself as entry.
 */
private class EntryIterator extends EnumMapIterator<Map.Entry<K,V>>
    implements Map.Entry<K,V>
{
    public Map.Entry<K,V> next() {
        if (!hasNext())
            throw new NoSuchElementException();
        lastReturnedIndex = index++;
        return this;
    }

    public K getKey() {
        checkLastReturnedIndexForEntryUse();
        return keyUniverse[lastReturnedIndex];
    }

    public V getValue() {
        checkLastReturnedIndexForEntryUse();
        return unmaskNull(vals[lastReturnedIndex]);
    }

    public V setValue(V value) {
        checkLastReturnedIndexForEntryUse();
        V oldValue = unmaskNull(vals[lastReturnedIndex]);
        vals[lastReturnedIndex] = maskNull(value);
        return oldValue;
    }

    // equals, hashCode, toString

    private void checkLastReturnedIndexForEntryUse() {
        if (lastReturnedIndex < 0)
            throw new IllegalStateException("Entry was removed");
    }
}

这是可能的，因为 Map.Entry specification状态(由我强调):

A map entry (key-value pair). The Map.entrySet method returns a collection-view of the map, whose elements are of this class. The only way to obtain a reference to a map entry is from the iterator of this collection-view. These Map.Entry objects are valid only for the duration of the iteration; more formally, the behavior of a map entry is undefined if the backing map has been modified after the entry was returned by the iterator, except through the setValue operation on the map entry.

如果您想一次获取所有条目，则必须使用 map.entrySet().toArray() ，这可能会创建条目的不可变副本。

<小时/>

这里有一些关于默认映射的更多观察(全部在 OpenJDK 1.6.0_20 中，可以在 Ubuntu 的 openjdk6-source 包中找到):

• 通用 map HashMap和TreeMap (以及遗留的 Hashtable )已经在使用一些有点Entry对象作为其内部结构(表或树)的一部分，因此它们简单地让这些对象实现 Map.Entry 并返回它们。它们不是由迭代器动态创建的。

  这同样适用于 WeakHashMap (强引用中有 Entry 对象并不能避免如果我理解正确的话，它是垃圾收集的关键 - 但只要你不打电话 next()于迭代器，迭代器保存当前条目中的键)。

• IdentityHashMap在内部使用一个简单的Object[] ,使用交替的键和值，因此这里也没有条目对象，因此也重用了迭代器作为条目。

• ConcurrentSkipListMap使用没有实现任何东西的 Node 对象，因此它的迭代器返回 new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v); 。这意味着您不能使用他们的 setValue()方法，正如类文档中所解释的:

  All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method. (Note however that it is possible to change mappings in the associated map using put, putIfAbsent, or replace, depending on exactly which effect you need.)

• ConcurrentHashMap内部使用HashEntry类似于 HashMap 的类，但这并不实现任何事情。此外，还有一个内部类 WriteThroughEntry (延伸 AbstractMap.SimpleEntry )，其setValue()方法委托(delegate)给 put map 的方法。迭代器返回此 WriteThroughEntry 的新对象类。