ArrayMap VS HashMap

在Java里面用Collection里面的HashMap作为容器我们使用的频率很高,而ArrayMap是Android api提供的一种用来提升特定场和内存使用率的特殊数据结构。今天我就写一篇博客记录一下。

HashMap

QQ截图20150823235946

Java库里的HashMap其实是一个连续的链表数组,通过让key计算hash值后插入对应的index里。当hash值发生碰撞时,可以采用线性探测,二次hash,或者后面直接变成链表的结构来避免碰撞。因为hash的值不是连续的,所以hashmap实际需要占用的大小会比它实际能装的item的容量要大。我们可以看一下HashMap的源码:

  
 public HashMap(int initialCapacity, float loadFactor)   
 {   
     // 初始容量不能为负数  
     if (initialCapacity < 0)   
         throw new IllegalArgumentException(   
        "Illegal initial capacity: " +   
             initialCapacity);   
     // 如果初始容量大于最大容量,让出示容量  
     if (initialCapacity > MAXIMUM_CAPACITY)   
         initialCapacity = MAXIMUM_CAPACITY;   
     // 负载因子必须大于 0 的数值  
     if (loadFactor <= 0 || Float.isNaN(loadFactor))   
         throw new IllegalArgumentException(   
         loadFactor);   
    //....
    // 设置容量极限等于容量 * 负载因子  
     threshold = (int)(capacity * loadFactor);   
     // 初始化 HashMap用于存储的数组  
     table = new Entry[capacity];            // ①  
     init();   
 }   

你会发现它又一个变量叫loadfactor,还有threshold。threshold就是临界值的意思,代表当前HashMap的储存机构能容纳的最大容量,它等于loadfactor * 容量。当HashMap记录存入的item size大于threshold后,HashMap就会进行扩容(resize)。当我们第一次新建一个HashMap对象的时候,默认的容量是16,若你只打算在HashMap里放入3个元素那将浪费至少13个空间。

ArrayMap

ArrayMap是怎么实现节省内存的呢?先放数据结构图:

QQ截图20150824001700

 

他用两个数组来模拟Map,第一个数组存放存放item的hash值,第二数组是把key,value连续的存放在数组里,通过先算hash在第一个数组里找到它的hash index,根据这个index在去第二个数组里找到这个key-value。

在这里,在第一个数组里查找hash index的方法当然是用二分查找啦(binary search)。QQ截图20150824002101

这个数据结构的设计就做到了,有多个item我就分配多少内存,做到了memory的节约。并且因为数据结构是通过数组组织的,所以遍历的时候可以用index直接遍历也是很方便的有没有!但是缺点也很明显,查找达不到HashMap O(1)的查找时间。

当要存储的对象较少的时候(1000以下的时候)可以考虑用ArrayMap来减少内存的占用。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>