2-D（并发）HashMap：2-属性键类型？ 哈希图的哈希图？ [更新]

Question

所以我需要一个二维的ConcurrentHashMap。

它必须尽可能快，因为我将非常频繁地添加和更新其值。 它位于多线程应用程序中，因此选择使用 ConcurrentHashMap 而不仅仅是 HashMap。

“x”和“y”索引都是具有已知范围（0 到 40,000,000）的整数。

我需要知道的是：实现这一点的最有效方法是什么，以便尽可能快？ 最明显的途径是创建一个文字二维哈希图：

ConcurrentHashMap>> 或者我可以创建一个具有两个属性 x 和 y的

私有类“IntPair”，并将其用作键...但如果我这样做，最有效的方法是什么 equals( ) 和 hashcode()？ 我最终会分配太多新的 IntPair 吗？ 我可以为我分配的每个 x/y 保留一组 IntPair，然后使用纯粹自反的 eq​​uals() 以便我只检查完全相同的对象实例吗？

---

更新：

现在我已经仔细研究了 Integer.valueOf(int)，它使用的特定缓存模型在这里没有意义，因为我正在处理一个具有不可预测条目的非常稀疏的矩阵。 我确实需要缓存所有使用的 IntPair，而不是预先指定的子集。

直观上，在我看来，在大地图中查找 IntPair 来查看我是否已经创建了它，实际上与在大“2-D”中查找它或多或少相同无论如何，ConcurrentHashMap 不是吗？ 所以看来这里的解决方案实际上是每次查找密钥时都使用 new IntPair(x,y) 。 是的？

Answer 1

这取决于 40,000,000 x 40,000,000 矩阵中 (x,y) 点的稀疏程度。 我的猜测是，无论如何，矩阵都会非常稀疏，因此创建大量 ConcurrentHashMap 的成本将会很高。

相比之下，您的（不可变的）IntPair 建议似乎更具吸引力。 正如您所建议的，您甚至可以缓存其中一些对以提高性能（请参阅 Integer.valueOf(int) 查看如何使用静态嵌套类和静态工厂方法来实现）。 由于哈希码始终是必需的，因此您可以在构造函数中预先计算它并将其保存为最终字段。 要计算相等，您可以使用缓存中对象的身份相等性，否则您需要单独比较 x 和 y。

编辑：这是 源代码 (OpenJDK) Integer.valueOf( int)。

Answer 2

ConcurrentHashMap 非常大，因此您可能不需要它们的集合。

生命周期短的对象实际上分配起来非常快。 无论如何，您是否必须创建Integers？

您可以实习坐标对象，但仅查找的成本可能与创建它们相当。 Integer 的真正优势在于，当您保留大量实例一段时间后，相同的实例会被共享。

如果性能确实是一个大问题，您可以编写（或使用）一个将长整型映射到引用的映射类型对象。 如果看到自定义地图也具有与坐标系相关的功能（例如查找最近的或在某个范围内），我不会感到惊讶。

Answer 3

回应扎克，是的，矩阵将非常稀疏。

我查看了您链接的页面，毫无疑问 Integer.valueOf(int) 的功能是理想的。 如果我在 IntPair 类中开发了类似的静态方法，我是否可以假设我可以定义 equals() 来仅检查严格的自反相等？

也就是说，我在该页面中没有看到它解释如何使用静态嵌套类和静态工厂方法来实现该功能......我是否只是错过了它？ 我怎么做？

谢谢！

Answer 4

我基于标准 Java HashMap 制作了一个 Int2DMap 实现。 我发现它比使用 IntPair 作为密钥更快。 但是，它需要同步。

import java.io.*;
import java.util.*;

public class Int2DMap implements Map, Serializable {
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    protected Entry[] table;
    protected int size;
    protected int threshold;
    protected float loadFactor;
    protected transient volatile int modCount;

    public Int2DMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity) {
            capacity <<= 1;
        }
        this.loadFactor = loadFactor;
        this.threshold = (int) (capacity * loadFactor);
        this.table = new Entry[capacity];
    }

    public Int2DMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public Int2DMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public boolean containsKey(Object key) {
        int[] xy = (int[]) key;
        return containsKey(xy[0], xy[1]);
    }

    public Object get(Object key) {
        int[] xy = (int[]) key;
        return get(xy[0], xy[1]);
    }

    public Object put(Object key, Object value) {
        int[] xy = (int[]) key;
        return put(xy[0], xy[1], value);
    }

    public Object remove(Object key) {
        int[] xy = (int[]) key;
        return remove(xy[0], xy[1]);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    protected static final int indexFor(int x, int y, int length) {
        return (x * 31 + y) & (length - 1);
    }

    public Object get(int x, int y) {
        for (Entry e = table[indexFor(x, y, table.length)]; e != null; e = e.next) {
            if (e.x == x && e.y == y) {
                return e.value;
            }
        }
        return null;
    }

    public boolean containsKey(int x, int y) {
        return getEntry(x, y) != null;
    }

    protected Entry getEntry(int x, int y) {
        for (Entry e = table[indexFor(x, y, table.length)]; e != null; e = e.next) {
            if (e.x == x && e.y == y) {
                return e;
            }
        }
        return null;
    }

    public Object put(int x, int y, Object value) {
        int i = indexFor(x, y, table.length);
        for (Entry e = table[i]; e != null; e = e.next) {
            if (e.x == x && e.y == y) {
                Object oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(x, y, value, i);
        return null;
    }

    protected void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int) (newCapacity * loadFactor);
    }

    protected void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry next = e.next;
                    int i = indexFor(e.x, e.y, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

    public void putAll(Map m) {
        int numKeysToBeAdded = m.size();
        if (numKeysToBeAdded == 0) {
            return;
        }
        if (numKeysToBeAdded > threshold) {
            int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
            if (targetCapacity > MAXIMUM_CAPACITY)
                targetCapacity = MAXIMUM_CAPACITY;
            int newCapacity = table.length;
            while (newCapacity < targetCapacity)
                newCapacity <<= 1;
            if (newCapacity > table.length)
                resize(newCapacity);
        }
        for (Iterator i = m.entrySet().iterator(); i.hasNext();) {
            Map.Entry e = (Map.Entry) i.next();
            put(e.getKey(), e.getValue());
        }
    }

    public Object remove(int x, int y) {
        Entry e = removeEntryForKey(x, y);
        return (e == null ? null : e.value);
    }

    protected Entry removeEntryForKey(int x, int y) {
        int i = indexFor(x, y, table.length);
        Entry prev = table[i];
        Entry e = prev;
        while (e != null) {
            Entry next = e.next;
            Object k;
            if (e.x == x && e.y == y) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }

    protected Entry removeMapping(Object o) {
        if (!(o instanceof Entry))
            return null;
        Entry entry = (Entry) o;
        int x = entry.x;
        int y = entry.y;
        int i = indexFor(x, y, table.length);
        Entry prev = table[i];
        Entry e = prev;
        while (e != null) {
            Entry next = e.next;
            if (e.x == x && e.y == y) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }

    public void clear() {
        modCount++;
        Entry[] tab = table;
        for (int i = 0; i < tab.length; i++)
            tab[i] = null;
        size = 0;
    }

    public boolean containsValue(Object value) {
        Entry[] tab = table;
        for (int i = 0; i < tab.length; i++)
            for (Entry e = tab[i]; e != null; e = e.next)
                if (value.equals(e.value))
                    return true;
        return false;
    }

    static class Entry implements Map.Entry {
        final int x;
        final int y;
        Object value;
        Entry next;

        Entry(int x, int y, Object value, Entry next) {
            this.x = x;
            this.y = y;
            this.value = value;
            this.next = next;
        }

        public final Object getKey() {
            return new int[] { x, y };
        }

        public final Object getValue() {
            return value;
        }

        public final Object setValue(Object newValue) {
            Object oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry) o;
            int[] xy = (int[])e.getKey();
            if (x == xy[0] && y == xy[1]) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return ((31 + x) * 31 + y);
        }

        public final String toString() {
            return "[" + x + ", " + y + "]=" + value;
        }

        /**
         * This method is invoked whenever the value in an entry is overwritten by
         * an invocation of put(k,v) for a key k that's already in the HashMap.
         */
        void recordAccess(Int2DMap m) {
        }

        /**
         * This method is invoked whenever the entry is removed from the table.
         */
        void recordRemoval(Int2DMap m) {
        }
    }

    void addEntry(int x, int y, Object value, int bucketIndex) {
        Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry(x, y, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }


    private abstract class HashIterator implements Iterator {
        Entry next; // next entry to return
        int expectedModCount; // For fast-fail
        int index; // current slot
        Entry current; // current entry

        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        final Entry nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry e = current = next;
            if (e == null)
                throw new NoSuchElementException();
            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
            return e;
        }

        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int x = current.x;
            int y = current.y;
            current = null;
            Int2DMap.this.removeEntryForKey(x, y);
            expectedModCount = modCount;
        }
    }

    private final class ValueIterator extends HashIterator {
        public Object next() {
            return nextEntry().value;
        }
    }

    private final class KeyIterator extends HashIterator {
        public Object next() {
            return nextEntry().getKey();
        }
    }

    private final class EntryIterator extends HashIterator {
        public Map.Entry next() {
            return nextEntry();
        }
    }

    // Subclass overrides these to alter behavior of views' iterator() method
    Iterator newKeyIterator() {
        return new KeyIterator();
    }

    Iterator newValueIterator() {
        return new ValueIterator();
    }

    Iterator newEntryIterator() {
        return new EntryIterator();
    }

    public Set keySet() {
        return new KeySet();
    }

    private final class KeySet extends AbstractSet {
        public Iterator iterator() {
            return newKeyIterator();
        }

        public int size() {
            return size;
        }

        public boolean contains(Object o) {
            return containsKey(o);
        }

        public boolean remove(Object o) {
            int[] xy = (int[]) o;
            return Int2DMap.this.removeEntryForKey(xy[0], xy[1]) != null;
        }

        public void clear() {
            Int2DMap.this.clear();
        }
    }

    public Collection values() {
        return new Values();
    }

    private final class Values extends AbstractCollection {
        public Iterator iterator() {
            return newValueIterator();
        }

        public int size() {
            return size;
        }

        public boolean contains(Object o) {
            return containsValue(o);
        }

        public void clear() {
            Int2DMap.this.clear();
        }
    }

    public Set entrySet() {
        return new EntrySet();
    }

    private final class EntrySet extends AbstractSet {

        public Iterator iterator() {
            return newEntryIterator();
        }

        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Entry e = (Entry) o;
            Entry candidate = getEntry(e.x, e.y);
            return candidate != null && candidate.equals(e);
        }

        public boolean remove(Object o) {
            return removeMapping(o) != null;
        }

        public int size() {
            return size;
        }

        public void clear() {
            Int2DMap.this.clear();
        }
    }

    public static void main(String[] args) {                
        try {

            Int2DMap map = new Int2DMap();

            map.put(20, 6000, "Test");
            System.out.println(map.size() == 1);

            System.out.println(map.get(20, 6000) != null);

            System.out.println("Test".equals(map.get(20, 6000)));

            for (Iterator iter = map.values().iterator(); iter.hasNext();) {
                System.out.println("Test".equals(iter.next()));
            }

            for (Iterator iter = map.keySet().iterator(); iter.hasNext();) {
                int[] key = (int[])iter.next();
                System.out.println(key[0] == 20 && key[1] == 6000);
            }

            for (Iterator iter = map.entrySet().iterator(); iter.hasNext();) {
                Map.Entry e = (Map.Entry)iter.next();
                System.out.println(e.toString().equals("[20, 6000]=Test"));
            }

            map.remove(20, 6000);
            System.out.println(map.size() == 0 && map.get(20, 6000) == null);


            long start = System.nanoTime();
            int max = 40000000;
            for (int i = 0; i < 500000; i++) {
                int x = (int)(Math.random() * max);
                int y = (int)(Math.random() * max);
                map.put(x, y, "");

                int x2 = (int)(Math.random() * max);
                int y2 = (int)(Math.random() * max);
                Object o = map.get(x2, y2);

            }
            System.out.println(map.size());
            System.out.println((System.nanoTime() - start) / 1000000);


            Map map2 = new HashMap();
            start = System.nanoTime();

            for (int i = 0; i < 500000; i++) {
                String key = "" + (int)(Math.random() * max) + "," + (int)(Math.random() * max);
                map2.put(key, "");

                String key2 = "" + (int)(Math.random() * max) + "," + (int)(Math.random() * max);
                Object o = map2.get(key2);

            }
            System.out.println(map2.size());
            System.out.println((System.nanoTime() - start) / 1000000);


        } catch (Throwable t) {
            t.printStackTrace();
        }
    }
}