Какая реализация Mapя должен использовать, если моя карта должна быть маленькой, а не быстрой? - PullRequest
Новая
       8

Какая реализация Mapя должен использовать, если моя карта должна быть маленькой, а не быстрой?

28 голосов
/ 12 января 2012

Я обычно использую HashMap в своих программах, так как я знаю, что обычно он наиболее эффективен (при правильном использовании) и легко справляется с большими картами. Я знаю о EnumMap, который очень полезен для ключей перечисления, но часто я создаю небольшую карту, которая никогда не станет очень большой, скорее всего, скоро будет отброшена и не будет проблем с параллелизмом.

Является ли HashMap<K,V> слишком сложным для этих небольших, локальных и временных применений? Есть ли другая, простая реализация, которую я могу использовать в этих случаях?

Мне кажется, я ищу реализацию Map, аналогичную ArrayList для List. Это существует?

Добавлено позже после ответов:

Вот сценарий, в котором медленная, но очень простая реализация может быть лучше - когда у меня много, многие из этих Map с. Предположим, например, у меня есть миллион или около того этих крошечных карт, каждая из которых содержит несколько (часто менее трех) записей. У меня низкий референтный уровень - возможно, я на самом деле не ссылаюсь на них, пока они не будут отброшены в большинстве случаев Это все еще тот случай, когда HashMap - лучший выбор для них?

Использование ресурсов - это больше, чем просто скорость. Мне бы хотелось что-то, что не фрагментирует кучу и, к примеру, заставляет GC занимать много времени.

Возможно, HashMap является правильным ответом, но это не случай преждевременной оптимизации (или, по крайней мере, это не так).

Добавлено намного позже, после некоторой мысли:

Я решил написать свой собственный код SmallMap. Это легко сделать с помощью AbstractMap. Я также добавил пару конструкторов, чтобы SmallMap можно было построить из существующего Map.

По пути я должен был решить, как представлять Entry с и реализовать SmallSet для метода entrySet.

Я многому научился благодаря кодированию (и юнит-тестированию) и хочу поделиться этим, если кто-то еще захочет. Это на github здесь .

Ответы [ 9 ]

18 голосов
/ 14 мая 2012

В Java нет стандартной небольшой реализации Map.HashMap - одна из лучших и наиболее гибких реализаций Map, и ее трудно победить.Тем не менее, в очень маленькой области требований - где использование кучи и скорость построения имеют первостепенное значение - можно добиться большего.

Я реализовал SmallCollections на GitHub, чтобы продемонстрировать, как этоможет быть сделано.Я бы полюбил несколько комментариев о том, добился ли я успеха.Я ни в коем случае не уверен, что у меня есть.

Хотя предлагаемые здесь ответы иногда были полезны, они, как правило, неправильно понимали суть.В любом случае, ответ на мой собственный вопрос был, в конце концов, для меня гораздо полезнее, чем когда мне его задавали.

Вопрос здесь послужил своей цели, и именно поэтому я «ответил на него сам».

12 голосов
/ 12 января 2012

Я думаю, что это преждевременная оптимизация.У вас проблемы с памятью?Проблемы с производительностью при создании слишком большого количества карт?Если нет, то я думаю, что с HashMap все в порядке.

Кроме того, глядя на API, я не вижу ничего более простого, чем HashMap.

Если у вас возникли проблемы, вы можете свернуть свою собственную реализацию Map, которая имеет очень простые внутренние компоненты.Но я сомневаюсь, что у вас получится лучше, чем реализации Map по умолчанию, плюс у вас есть дополнительные затраты, чтобы убедиться, что ваш новый класс работает.В этом случае может возникнуть проблема с вашим дизайном.

4 голосов
/ 12 января 2012

HashMap, пожалуй, самая легкая и простая коллекция.

Иногда более эффективным решением является использование POJO.например, если ваши ключи являются именами полей и / или ваши значения являются примитивами.

2 голосов
/ 12 января 2012

HashMap - хороший выбор, потому что он предлагает средний регистр O(1) ставит и получает. Это не гарантирует упорядочение, хотя, как в реализациях SortedMap (т.е. TreeMap O(log n) ставит и получает), но если у вас нет требований к упорядочению, то HashMap лучше.

1 голос
/ 27 июня 2017

Android имеет ArrayMap с целью минимизации памяти. В дополнение к ядру, он находится в библиотеке поддержки v4, которая, теоретически, должна иметь возможность компилировать JRE для Oracle или OpenJDK. Вот ссылка на исходник ArrayMap в ответвлении библиотеки поддержки v4 на github .

1 голос
/ 12 января 2012

HashMap использует больше или меньше памяти (при создании) в зависимости от того, как вы ее инициализируете: чем больше блоков, тем больше использование памяти, но более быстрый доступ для большого количества элементов ;если вам нужно только небольшое количество предметов, вы можете инициализировать его с небольшим значением, что приведет к меньшему количеству ведер, которые все равно будут быстрыми (так как каждый из них получит несколько предметов).Нет никакой потери памяти, если вы установите ее правильно (компромисс - это в основном использование памяти и скорость).

Что касается фрагментации кучи и траты цикла GC, и тому подобное, реализация Map не так уж и хороша.их;все сводится к тому, как вы установите его.Следует понимать, что речь идет не о реализации Java, а о том, что универсальные (как, например, не могут предполагать ничего о ключевых значениях, таких как EnumMap делает) хеш-таблицы (не HashTable s) являются наилучшими возможными реализациями структуры карты.

1 голос
/ 12 января 2012

Я согласен с @hvgotcodes, что это преждевременная оптимизация, но все же хорошо знать все инструменты в наборе инструментов.

Если вы выполняете много итераций над тем, что находится на карте, LinkedHashMap обычно намного быстрее, чем HashMap, если у вас много потоков, работающих с картой одновременно, ConcurrentHashMap часто бывает лучший выбор Я бы не беспокоился о том, что реализация Map неэффективна для небольших наборов данных. Как правило, все наоборот: неправильно построенная карта легко становится неэффективной с большими объемами данных, если у вас неверные значения хеш-функции или что-то заставляет ее иметь слишком мало сегментов для своей загрузки.

Тогда, конечно, бывают случаи, когда HashMap вообще не имеет смысла, например, если у вас есть три значения, которые вы всегда будете индексировать с помощью ключей 0, 1 и 2, но я предполагаю, что вы понимаете, что: -)

0 голосов
/ 29 июня 2018

Мне также было интересно, и только для эксперимента я создал карту, которая хранит ключи и значения только в полях и допускает до 5 записей. Он потребляет в 4 раза меньше памяти и работает в 16 раз быстрее, чем HashMap https://github.com/stokito/jsmallmap

0 голосов
/ 21 марта 2016

Существует альтернатива, называемая AirConcurrentMap, которая более эффективно использует память, чем записи в 1К, чем любая другая карта, которую я нашел, и быстрее, чем ConcurrentSkipListMap для операций на основе ключей, и быстрее, чем любая карта для итераций, и имеет внутренний пул потоков дляпараллельные сканы.Это упорядоченный, т.е. NavigableMap и ConcurrentMap.Это бесплатно для некоммерческого использования без источника, и коммерчески лицензировано с или без источника.Смотрите Boilerbay.com для графиков.Полное раскрытие: я автор.

AirConcurrentMap соответствует стандартам, поэтому он совместим со штекерами везде, даже для обычной карты.

Итераторы уже очень быстрые, особенно для 1К записей.При сканировании на более высокой скорости используется модель «посетитель» с обратным вызовом с одним посещением (k, v), который достигает скорости параллельных потоков Java 8.Параллельное сканирование AirConcurrentMap превышает параллельные потоки Java 8 примерно в 4 раза.Многопоточный посетитель добавляет методы split () и merge () к однопоточному посетителю, которые напоминают один из map / lower: 

static class ThreadedSummingVisitor<K> extends ThreadedMapVisitor<K, Long> {
    private long sum;
    // This is idiomatic
    long getSum(VisitableMap<K, Long> map) {
        sum = 0;
        map.getVisitable().visit(this);
        return sum;
    }

    @Override
    public void visit(Object k, Long v) {
        sum += ((Long)v).longValue();
    }

    @Override
    public ThreadedMapVisitor<K, Long> split() {
        return new ThreadedSummingVisitor<K>();
    }

    @Override
    public void merge(ThreadedMapVisitor<K, Long> visitor) {
        sum += ((ThreadedSummingVisitor<K>)visitor).sum;
    }
}
...
// The threaded summer can be re-used in one line now.
long sum = new ThreadedSummingVisitor().getSum((VisitableMap)map);
...