java memory sparse-array

Arreglo escaso de memoria eficiente en Java



memory sparse-array (4)

(Hay algunas preguntas sobre las matrices dispersas eficientes en cuanto al tiempo, pero estoy buscando la eficiencia de la memoria).

Necesito el equivalente de una List<T> o un Map<Integer,T> que

  1. Puede crecer a demanda simplemente configurando una clave más grande que cualquiera que se haya encontrado anteriormente. (Puede suponer que las claves no son negativas).
  2. Es tan eficiente en cuanto a la memoria como una ArrayList<T> en el caso de que la mayoría de los índices no sean null , es decir, cuando los datos reales no son muy escasos.
  3. Cuando los índices son escasos, consume espacio proporcional a la cantidad de índices no null .
  4. Utiliza menos memoria que HashMap<Integer,T> (ya que esto autocaptura las claves y probablemente no aprovecha el tipo de clave escalar).
  5. Puede obtener o establecer un elemento en el tiempo de registro (N) amortizado donde N es el número de entradas: no necesita ser tiempo lineal, la búsqueda binaria sería aceptable.
  6. Implementado en una biblioteca Java de código abierto no viral (preferiblemente en Maven Central).

¿Alguien sabe de tal clase de utilidad?

Hubiera esperado que Commons Collections tuviera uno, pero no parecía.

Me encontré con org.apache.commons.math.util.OpenIntToFieldHashMap que parece casi correcto, excepto que el tipo de valor es un elemento de campo que parece gratuito; Solo quiero que T extends Object . Parece que sería fácil editar su código fuente para que sea más genérico, aunque prefiero usar una dependencia binaria si hay una disponible.

Intentaría con colecciones trove , hay TIntObjectMap que puede funcionar para sus intenciones.

Le sugiero que use OpenIntObjectHashMap desde la biblioteca Colt. Enlazar

Guarde mi caso de prueba como jglick / inthashmap . Los resultados:

HashMap size: 1017504 TIntObjectMap size: 853216 IntHashMap size: 846984 OpenIntObjectHashMap size: 760472