任何人知道为低内存使用优化的java.util.Map实现？ [英] Anyone know of a java.util.Map implementation optimized for low memory use?

问题描述

我在常用的地方（apache commons，google）找不到一个...

I've looked in the usual places (apache commons, google) and not been able to find one ...

它应该是开源的。

相当寻找一个基于链表的。用例是10000年的地图，不一定有很多值。它不需要放大，因为我可以转换它，当它变得太大。

Pretty much looking for one based on a linked list. The use case is 10'000's of maps, with not necessarily many values in. It does not need to scale up, as i can convert it when it gets too big.

一些数字，大小使用一些计算的jvm值（8bytes / java.lang.Object，4bytes / ref）HashMap约100 + 32n字节，理论最好是12 + 20 * n。 < - 我想要的，对于小n。

Some numbers, sizes using some calculated jvm values (8bytes/java.lang.Object, 4bytes/ref) the HashMap is about 100+32n bytes, the theoretical best is 12+20*n. <-- I want that, for small n.

推荐答案

我做了一个速度比较，并发现，当与一个HashMap相比，它仍然稍快与4条目，但较慢与5或更多。我用一个长的密钥列表做了测试，我试图给出一个类似的化妆作为一个随机的英语单词列表。

Ok, implemented it myself in the end. I did a speed comparison, and found when compared to a HashMap that it was still slightly faster with 4 entries, but slower with 5 or more. I did the tests with a longish list of keys that I tried to give a similar makeup as a list of random english words.

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());
        }
    }
}

这篇关于任何人知道为低内存使用优化的java.util.Map实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！