¿Alguien sabe de una implementación de java.util.Map optimizada para el uso de poca memoria?

Question

He buscado en los lugares habituales (apache commons, google) y no he podido encontrar ninguno ...

Debe ser de código abierto.

Bastante buscando uno basado en una lista vinculada. El caso de uso es de 10 000 de mapas, no necesariamente con muchos valores. No es necesario ampliarlo, ya que puedo convertirlo cuando sea demasiado grande.

Algunos números, tamaños que usan algunos valores jvm calculados (8bytes/java.lang.Object, 4bytes/ref) el HashMap tiene aproximadamente 100 + 32n bytes, el mejor teórico es 12 + 20 * n. < - Quiero eso, para n pequeño.

Answer 1

Ok, implementado por mí mismo al final. Hice una comparación de velocidad, y encontré en comparación con un HashMap que aún era un poco más rápido con 4 entradas, pero más lento con 5 o más. Hice las pruebas con una larga lista de claves que traté de dar un maquillaje similar a una lista de palabras aleatorias en inglés.

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 2

Simplemente, recomiendo usar uno de HashMap, Hashtable y ConcurrentHashMap de JDK según los requisitos de sincronización o concurrencia. Si decide usarlos, puede ser útil establecer initialCapacity y loadFactor de manera adecuada en el constructor.

Las colecciones de Google y las colecciones de Apache commons proporcionan más funciones: LRUMap, ReferenceMap, MultikeyMap, etc. Pero no creo que no sea solo por el tamaño pequeño.

Answer 3

LinkedHashMap usa una lista vinculada, creo, pero dudo que esté optimizada para el uso de poca memoria. Por lo general, el objetivo de un mapa es acelerar las búsquedas de la clave al valor, lo que explica por qué no encuentra lo que necesita en los lugares comunes. Puede ser más fácil escribir su propia implementación de Map, y tal vez incluso podría lanzar el código en caso de que alguien más necesite lo mismo.

Answer 4

Escriba el código de una manera que oculte el uso de mapas (de todos modos, debe hacer eso, y parece que usted también). En el momento en que importa, porque ha creado un perfil del código y puede ver que la memoria es realmente un problema, busque uno :-)

Si en este momento usted sabe que hay un problema, entonces, lo siento No sé de uno. Sin embargo, con demasiada frecuencia la gente trata con la "idea" de que el código va a ser lento/con mucha memoria/etc ... y comienza a tratar de optimizarlo por adelantado en lugar de corregir el código.

Dicho esto, si está escribiendo algo que usted sabe que es importante, debería medir a medida que avanza. Por ejemplo, estoy trabajando en el código para analizar archivos de clase, hago un pequeño cambio y luego veo cómo afecta el rendimiento. Por ejemplo, sabía de hecho que un cambio que hice (3 líneas) hizo que mi programa fuera 4 veces más lento ... Pasé el tiempo en ese punto para descubrir la forma más rápida de hacerlo.

Además, ¿está seguro de que se necesitan mapas si el valor de "n" es pequeño? Tal vez una lista es lo suficientemente rápido? ¿También ha intentado sintonizar el mapa existente para que use menos memoria?

Answer 5

podría tener un vistazo a las colecciones de bienes comunes Flat3Map, está optimizado para almacenar valores de 3 en 3 campos y desborda a otro mapa a 4.

No he mirado en la aplicación pero puede ser vale la pena pensar . El único problema es que, como commons-collections es 1.3 compatible, no hay genéricos.

Answer 6

Envuelva una lista de arreglos con la interfaz del mapa. ArrayList usa solo unos pocos bytes. Cada nodo necesita dos punteros, uno para la clave y otro para el valor. Use la búsqueda secuencial para buscar valores. Mientras haya pocas entradas, el rendimiento estará bien [*]. Esto le dará la posibilidad de usar mapas reales para los pocos jarrones donde tiene una gran cantidad de valores.

*: Digamos que el tamaño promedio de su mapa es 10. Las computadoras de hoy en día pueden comparar aproximadamente 100 millones de claves por segundo, por lo que cada búsqueda demorará menos de cinco microsegundos en promedio.

Si el rendimiento es demasiado malo para su caso de uso, puede intentar ordenar la matriz por clave y usar la búsqueda binaria.

Answer 7

Depende mucho de cómo va a utilizar esos mapas, ¿puede rellenarlos de una vez y luego hacer búsquedas (¿necesita esas búsquedas para ser rápido)?

Una implementación utilizando una cantidad mínima de memoria sería poner todos los elementos de una matriz y para hacer una exploración para encontrar elementos (pero supongo que esto no es rápido suficiente para sus necesidades ...)

Si conoce todos los elementos al principio, puede intentar seleccionar un buen método hash sin demasiadas colisiones.

O tal vez usted podría utilizar TreeMap si permite que el tiempo de inserción lenta ...

Answer 8

Quizás esta respuesta es un poco tarde, pero echar un vistazo a Javolution proyecto. Contiene implementaciones de muchas estructuras de datos, destinadas a entornos incrustados y en tiempo real. Concretamente, existe una clase FastMap que podría hacer lo que usted desee.

Answer 9

Si almacena solamente String s, echar un vistazo a http://code.google.com/p/flatmap

edición Oh, lo siento, veo que busca pequeños mapas no es enorme, se olvidan de mi consejo a continuación.

Answer 10

Sé que es una vieja pregunta, pero quizás alguien podría agregar más ideas.

NB: El siguiente sería en realidad sólo tiene sentido para un subconjunto específico de casos de uso:

Si el requisito incluye altamente superpuestos juegos de llaves (en el caso extremo del mismo conjunto de claves para todos los mapas) entonces una solución efectiva muy podría ser "externalizar" las claves con respecto a los mapas y hacer que los mapas solo contengan valores, en una matriz.

La implementación no debe depender "estructuralmente" del factor de superposición, pero la mía funciona mejor cuanto más se superponen las claves. Como era de esperar

No puedo dar detalles exactos de mi implementación, pero es importante tener un mecanismo adecuado para traducir claves (almacenadas fuera de su objeto de mapa) a índices en la matriz de valores, permitiendo también que la matriz de valores permanezca compacta, es decir, tienen una longitud de cinco si su mapa contiene cinco asignaciones.

Digamos que las claves para todos los mapas se sientan en un mapa separado, asignado a los números. Entonces, se trata de tener una forma de relacionar los números y los índices de matriz.

Lo siento si esto no es lo suficientemente específico, pero pensé que la idea es interesante y simple al mismo tiempo, y podría ser utilizado como una dirección alternativa en el desarrollo de una memoria eficiente mapa.

vez más, es inherentemente adecuado para los casos de uso altos "solapamiento" clave, sino que es genérico. Puede sufrir problemas de rendimiento si la superposición es demasiado baja, según los detalles de implementación.