2-D (одновременный) HashMap: тип ключа с 2 свойствами? hashmap из hashmaps? [Обновить]

Question

Так что мне нужно 2-х мерное ConcurrentHashMap.

Это должно быть как можно быстрее, так как я собираюсь добавлять и обновлять его значения очень часто. Он находится в многопоточном приложении, поэтому вместо использования HashMap можно использовать ConcurrentHashMap.

И индексы "x", и "y" являются целыми числами с известным диапазоном (от 0 до 40 000 000).

Что мне нужно знать: каков наиболее эффективный способ реализовать это, чтобы он был максимально быстрым? Самый очевидный путь - создать буквально 2-D хэш-карту:

ConcurrentHashMap<Integer, ConcurrentHashMap<Integer, ValueObj>> foo;

Или я мог бы создать закрытый класс IntPair с двумя свойствами x и y и использовать его в качестве ключа ... хотя, если я это сделаю, какой самый эффективный способ сделать equals() и hashcode()? и буду ли я выделять слишком много новых IntPair с? Могу ли я сохранить набор IntPair s для каждого назначенного мною х / у, а затем использовать чисто рефлексивный метод equals (), чтобы я просто проверял точно такой же экземпляр объекта?

---

Обновление:

Теперь, когда я более внимательно посмотрел на Integer.valueOf (int), конкретная модель кэширования, которую он использует, здесь не имеет смысла, поскольку я имею дело с очень разреженной матрицей с непредсказуемыми записями. Мне действительно нужно кэшировать все те IntPairs, которые используются, а не заранее заданное подмножество.

Интуитивно, мне кажется, что поиск IntPair на большой карте, чтобы увидеть, если я уже создал его, на самом деле будет более или менее похож на простой поиск в большом "2 -D "ConcurrentHashMap в любом случае, не так ли? Таким образом, похоже, что решение на самом деле заключается в том, чтобы просто использовать new IntPair(x,y) каждый раз, когда я ищу ключ. Да?

Answer 1

Это зависит от того, насколько редки ваши (x, y) точки в матрице 40 000 000 x 40 000 000. Я предполагаю, что матрица все равно будет довольно разреженной, поэтому создание большого количества ConcurrentHashMap s будет дорогостоящим.

Ваше (неизменное) IntPair предложение кажется более привлекательным по сравнению. Как вы предлагали, вы можете даже кэшировать некоторые из этих пар для повышения производительности (см. Integer.valueOf(int), чтобы увидеть, как это можно реализовать с помощью статического вложенного класса и статического метода фабрики). Поскольку хеш-код всегда будет требоваться, вы можете предварительно вычислить его в конструкторе и сохранить как окончательное поле. Чтобы вычислить equals, вы можете использовать равенство тождественности для объектов в кэше, в противном случае вам нужно будет сравнивать x и y по отдельности.

РЕДАКТИРОВАТЬ: Вот исходный код (OpenJDK) для Integer.valueOf(int).

Answer 2

ConcurrentHashMap довольно большой, поэтому вам, вероятно, не нужна их коллекция.

Краткосрочные объекты на самом деле очень быстро распределяются. Вам все равно придется создать Integers?

Вы можете интернировать объекты координат, но стоимость простого поиска, вероятно, будет сопоставима с их созданием в любом случае. Реальная победа с Integer заключается в том, что одни и те же экземпляры становятся общими, если вы некоторое время держите их рядом.

Если производительность действительно огромная проблема, вы можете написать (или использовать) объект типа карты, который сопоставляет long со ссылками. Я не удивлюсь, увидев там пользовательские карты, которые также имеют функции, связанные с системами координат (например, поиск ближайшего или в пределах диапазона).

Answer 3

Я сделал реализацию Int2DMap на основе стандартного Java HashMap. Я считаю, что это быстрее, чем использовать 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();
        }
    }
}

Answer 4

В ответ на Зак, да, матрица будет очень разреженной.

Я посмотрел на страницу, на которую вы ссылались, и, без сомнения, функциональность Integer.valueOf (int) была бы идеальной. Если бы я разработал аналогичный статический метод в своем классе IntPair, могу ли я предположить, что могу определить equals() только для проверки строгого рефлексивного равенства?

Тем не менее, я не вижу на этой странице, где объясняется, как реализовать эту функциональность, используя статический вложенный класс и статический метод фабрики ... я просто как-то упускаю это? Как мне это сделать?

Спасибо!