Кто-нибудь знает о реализации java.util.Map, оптимизированной для нехватки памяти?

Question

Я посмотрел в обычных местах (Apache Commons, Google) и не смог найти один ...

Это должно быть с открытым исходным кодом.

В значительной степени ищет один на основе связанного списка. Вариант использования - это 10 000 карт, в которых необязательно много значений. Не нужно увеличивать масштаб, поскольку я могу преобразовать его, когда он становится слишком большим.

Некоторые числа, размеры, использующие некоторые вычисленные значения jvm (8 байтов / java.lang.Object, 4 байта / ссылка), HashMap составляет около 100 + 32n байтов, теоретическое лучшее - 12 + 20 * n. <- Я хочу это, для малых п. </p>

Answer 1

Оберните ArrayList интерфейсом Map. ArrayList использует только несколько байтов. Каждому узлу нужны два указателя, один для ключа и один для значения. Используйте последовательный поиск для поиска значений. Пока есть только несколько записей, производительность будет в порядке [*]. Это даст вам возможность использовать реальные карты для нескольких ваз, в которых у вас большое количество значений.

*: допустим, средний размер карты равен 10. Сегодня компьютеры могут сравнивать примерно 100 миллионов ключей в секунду, поэтому каждый поиск занимает в среднем менее пяти микросекунд.

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

Answer 2

Ладно, сам реализовал в конце. Я сделал сравнение скорости и обнаружил, что по сравнению с HashMap он все еще был немного быстрее с 4 записями, но медленнее с 5 или более. Я выполнил тесты с длинным списком клавиш, которые я пытался создать аналогично списку случайных английских слов.

import java.util.*;

// PUBLIC DOMAIN
public class SmallMap extends AbstractMap {

    private Entry entry = null;

    public void clear() { entry = null; }
    public boolean isEmpty() { return entry==null; }    
    public int size() {
        int r = 0;
        for(Entry e = entry; e!=null; e = e.next) r++;
        return r;
    }

    public boolean containsKey(Object key) {
        for(Entry e = entry; e!=null; e = e.next){
            if(e.key.equals(key)){
                return true;
            }
        }
        return false;
    }

    public boolean containsValue(Object value) {
        for(Entry e = entry; e!=null; e = e.next){
            if(e.value==null){
                if(value==null) return true;
            }else if(e.value.equals(value)){
                return true;
            }
        }
        return false;
    }

    public Object get(Object key) {
        for(Entry e = entry; e!=null; e = e.next){
            if(e.key.equals(key)){
                return e.value;
            }
        }
        return null;
    }

    public Object put(Object key, Object value) {
        for(Entry e = entry; e!=null; e = e.next){
            if(e.key.equals(key)){
                Object r = e.value;
                e.value = value;
                return r;
            }
        }
        entry = new Entry(key, value, entry);
        return null;
    }

    public Object remove(Object key) {
        if(entry!=null){
            if(entry.key.equals(key)){
                Object r = entry.value;
                entry = entry.next;
                return r;
            }
            for(Entry e = entry; e.next!=null; e = e.next){
                if(key.equals(e.next.key)){
                    Object r = e.next.value;
                    e.next = e.next.next;
                    return r;
                }
            }
        }
        return null;
    }

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

    class EntrySet extends AbstractSet{
        public Iterator iterator() {
            return new Iterator(){

                Entry last = null;
                Entry e = entry;
                public boolean hasNext() { return e!=null; }

                public Object next() { 
                    last = e;
                    e = e.next;
                    return last;
                }

                public void remove() { 
                    if(last == null) throw new IllegalStateException();
                    SmallMap.this.remove(last.key);
                }
            };
        }

        public int size() { return SmallMap.this.size();}
    }

    static private class Entry implements java.util.Map.Entry {
        final Object key;
        Object value;
        Entry next; 
        Entry(Object key, Object value, Entry next){
            if(key==null) throw new NullPointerException();
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public Object getKey() { return key; }
        public Object getValue() { return value; }
        public Object setValue(Object value) { 
            Object r = this.value;
            this.value = value;
            return r;
        }
        public int hashCode() {
            return (key   == null ? 0 :   key.hashCode()) ^
               (value == null ? 0 : value.hashCode());
        }
    }
}

Answer 3

Можно взглянуть на общие коллекции Flat3Map , он оптимизирован для хранения 3 значений в 3 полях и переполняется на другую карту в 4.

Я не смотрел на реализацию, но, возможно, стоит подумать. Единственная проблема в том, что, поскольку commons-collection совместим с 1.3, нет универсальных.

Answer 4

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

Если вы знаете, что в данный момент существует проблема, то, извините, я не знаю ни одной. Однако слишком часто люди сталкиваются с «идеей» о том, что код будет медленным / как будто много памяти / и т.д.… и начинают пытаться оптимизировать его заранее, вместо того, чтобы делать код правильным.

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

Кроме того, вы уверены, что карты необходимы, если значение "n" мало? Возможно, список достаточно быстрый? Также вы пытались настроить существующую карту, чтобы она использовала меньше памяти?

Answer 5

LinkedHashMap использует связанный список, я думаю, но я сомневаюсь, что он оптимизирован для нехватки памяти. Обычно весь смысл карты в том, чтобы ускорить поиск от ключа к значению, что объясняет, почему вы не находите то, что вам нужно, в общих местах. Возможно, проще всего написать собственную реализацию Map, и, возможно, вы могли бы даже выпустить код на тот случай, если кому-то еще понадобится то же самое.

Answer 6

Просто я рекомендую использовать один из HashMap, Hashtable и ConcurrentHashMap JDK в зависимости от требований синхронизации или параллелизма. Если вы решите использовать их, правильная установка initialCapacity и loadFactor в конструкторе может помочь.

Коллекции Google и коллекции Apache Commons предоставляют больше возможностей: LRUMap, ReferenceMap, MultikeyMap и так далее. Но я не думаю, что есть не только для небольшого размера.

Answer 7

Я знаю, что это старый вопрос, но, возможно, кто-то может добавить дополнительные идеи.

Примечание: следующее действительно имеет смысл только для определенного подмножества вариантов использования:

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

Реализация не должна зависеть «структурно» от коэффициента перекрытия, но моя производительность работает тем лучше, чем больше перекрытия ключей. Как и следовало ожидать.

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

Скажите, что ключи для всех таких карт находятся на отдельной карте, сопоставленной с числами. Тогда нужно иметь возможность связать числа и индексы массивов.

Извините, если это не достаточно конкретно, но я подумал, что идея интересна и проста в то же время, и может быть использована в качестве альтернативного направления при разработке карты с эффективным использованием памяти.

Опять же, он по своей природе подходит для случаев использования с высоким перекрытием клавиш, но сам по себе является общим. Может сильно страдать от проблем с производительностью, если перекрытие слишком мало, в зависимости от деталей реализации.

Answer 8

Если вы храните только String s, взгляните на http://code.google.com/p/flatmap

edit Ой, извините, я вижу, вы ищете маленькие не большие карты, тогда забудьте о моем совете.

Answer 9

Возможно, этот ответ немного запоздал, но взгляните на проект Javolution . Он содержит реализации многих структур данных, предназначенных для встроенных сред и сред реального времени. Конкретно, существует класс FastMap , который может просто делать то, что вы хотите.

Answer 10

Это во многом зависит от того, как вы собираетесь использовать эти карты, можете ли вы заполнить их одним кадром, а затем просто выполнить поиск (вам нужны эти поиски, чтобы они были быстрыми )?

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

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

Или, может быть, вы могли бы использовать TreeMap, если разрешаете медленное время вставки ...