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

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

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

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

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

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

Ок, в итоге реализовал сам. Я провел сравнение скорости и обнаружил, что по сравнению с 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());
        }
    }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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