这不是通过 entrySet() 迭代创建太多 Map.Entry 实例吗? [英] Doesn't that iterate thru entrySet() create too many Map.Entry instances?

问题描述

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

I'm not sure if HashMap or TreeMap store Map.Entry in itself. That is, it's likely to return Map.Entry instance created on the fly when entrySet().iterator().next() is called.

就我个人而言，我认为这种形式可能会更好:

Personally, I think it may be better in this form:

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 的创建.

Thus, the creation of Entry is avoided.

我不知道 Java Compiler 是如何工作的，Java Compiler 会不会通过分析数据流来优化 Map.Entry 的创建并获得 Map.Entry 可以安全重用的知识?

I don't know how Java Compiler works, will Java Compiler optimize the creation of Map.Entry away, by analyzing the dataflow and get the knowledge that Map.Entry can be safely reused?

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

Or, is someone there have already written another collection framework to enable inplace iteration?

推荐答案

你所描述的(有一个迭代器本地 Map.Entry 对象并为所有 next() 返回值重用它)是一个可能的 Map 实现，我认为一些特殊用途的地图正在使用它.

What you describe (having an iterator-local Map.Entry object and reusing it for all next() return values) is one possible Map implementation, and I think some special-purpose maps are using this.

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

For example, the implementation of EnumMap.entrySet().iterator() (here the version from OpenJDK, 1.6.0_20) simply uses the iterator object itself as the Entry object returned by the next() method:

/**
 * 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 规范 状态(我强调):

This is possible, since the Map.Entry specification states (emphasis by me):

一个映射条目(键值对).Map.entrySet 方法返回地图的集合视图，其元素属于此类.获得对地图条目的引用的唯一方法是从此集合视图的迭代器.这些 Map.Entry 对象仅在持续时间内有效迭代；更正式地说，如果支持映射具有，则映射条目的行为是未定义的在迭代器返回条目后被修改，除了通过 setValue 操作在地图条目上.

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()，这可能会创建条目的不可变副本.

If you want all entries at once, you'll have to use map.entrySet().toArray(), which may create immutable copies of the entries.

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

Here some more observations about the default maps (all in OpenJDK 1.6.0_20 as found in Ubuntu's openjdk6-source package):

• 通用映射HashMap 和TreeMap(以及遗留的Hashtable)已经在使用一些一种 Entry 对象作为其内部结构(表或树)的一部分，所以他们简单地让这些对象实现 Map.Entry 并返回它们.它们不是由迭代器即时创建的.

• The general purpose maps HashMap and TreeMap (as well as the legacy Hashtable) are already using some kind of Entry objects as part of their internal structure (the table or tree), so they simple let these objects implement Map.Entry and return them. They are not created on the fly by the Iterator.

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

The same is valid for WeakHashMap (where having an Entry object in a strong reference does not avoid its key to get garbage-collected, if I understand right - but as long as you don't call next() on the iterator, the iterator holds the key in the current entry).

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

IdentityHashMap is internally using a simple Object[], with alternating key and value, so no entry objects here, too, and thus also a reusing of the iterator as entry.

ConcurrentSkipListMap 正在使用没有实现任何东西的 Node 对象，所以它的迭代器返回new AbstractMap.SimpleImmutableEntry(n.key, v);.这意味着你不能使用他们的 setValue() 方法，如类文档中所述:

ConcurrentSkipListMap is using Node objects which do not implement anything, so its iterators return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);. This implies you can't use their setValue() method, as explained in the class documentation:

由此类中的方法及其视图返回的所有 Map.Entry 对表示映射的快照在它们被生产的时候.它们不支持 Entry.setValue 方法.(但请注意，它可以使用 put、putIfAbsent 或 replace 更改关联映射中的映射，具体取决于正是您需要的效果.)

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 在内部使用了一个类似于 HashMap 的 HashEntry 类，但这并没有实施任何事情.此外，还有一个内部类 WriteThroughEntry(扩展AbstractMap.SimpleEntry)，其 setValue() 方法委托给地图的 put 方法.迭代器返回此 WriteThroughEntry 类的新对象.

ConcurrentHashMap internally uses a HashEntry class analogously to the HashMap, but this does not implement anything. Additionally, there is an internal class WriteThroughEntry (extending AbstractMap.SimpleEntry), whose setValue() method delegates to the put method of the map. The iterator returns new objects of this WriteThroughEntry class.

这篇关于这不是通过 entrySet() 迭代创建太多 Map.Entry 实例吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！