Java中map内部存储方式解析

map，即映射，也称为 键值对，有一个 key， 一个 value 。

比如 groovy 语言中，  def  map = ['name' : 'liudehua', 'age' : 50 ] ，则 map[ 'name' ]  的值是 'liudehua'。
那么 map 内部存储是怎么实现的呢？   下面慢慢讲解.

一、 使用 拉链式存储

这个以 java 中的 hashmap 为例进行讲解。   hashmap 的内部有个数组 entry[]  table， 这个数组就是存放数据的。

entry 类的定义大致是 :

class entry {
object key
object value
entry next;
}

所以， entry[]  table  的每个元素都是一个链表，即 hashmap 的内部存储是 数组 + 链表，即拉链式存储。

当往 haspmap 中 put(key,  value) 数据时，先进行  key.hashcode()  &  (table.length() - 1) ，得到一个小于 table.length() 的值， 称为 index， 则这个新的 entry 就属于 table[index] 这个链表了 ( 如果链表还不存在，则把这个新的 entry 作为链表的头部了 )；  然后开始从前往后遍历  table[index] 这个链表，如果 key.equals( entry.key )， 那么表示这个 key 已经有了旧值，则替换 value 的值即可；

否则，把这个新的 entry 插入到 table[index] 链表的最前面.

以上就是 hashmap 的存储方式介绍了， 而且可以知道，作为 hashmap 的 key， 它的 hashcode() 和 equals() 方法都被使用了

二、数组存储

1.分散的数组存储

这个以 threadlocal  和 threadlocal.values  类为例进行讲解。 values 类里面有两个变量， object[]  table, 和 mask ， table 就是存储数据的数组了，table 的长度是 2 的倍数 ，  mask 的值就是  table.length - 1 ;  这一点和 hashmap 的内部存储很像。  不过 table 中的每个元素就不是链表了。

当往  values 中进行 put(key, value) 时，先进行 key.hashcode & mask ，得到一个小于 table.length 的值，称为 index (与上面的 hashmap 好像，哈哈), 然后去检查 table[index] 的值，如果不存在，则在 table[index] 处放入 key， table[index + 1] 处放入 value; 如果已经存在了，且 key.equals( oldkey ) 不成立，即发生了冲突，那么 index = index + 2 ( 此处是 + 2，因为 key ，value 两个是挨着放的，一个元素占俩坑 ) ; 往下一地方找找，如果再冲突，再找，直到找到一个可插入的地方，把 table[index] = key, table[index + 1] = value; 

有两处需要注意:

key.hashcode() 必须是 2 的倍数, 否则 index 的值有可能为奇数，如此就可能发生冲突了.  可参考 threadlocal.hash 这个成员变量

table 内部的数据是分散着存储的.

2.连续的数组存储

这个以 android 中新增的 arraymap 为例进行分析( 据说没 arraymap 是用来替换 hashmap 的哈 ),  arraymap 中有两个主要变量， int[]  mhashes, object[]  marrays.

mhashes 主要是存放 key 的 hash 值的， marrays 是用来存放数据的，它也是奇数存放 key ，偶数存放 value ， key 和 value 顺序排列( 这个和 theadlocal.value 中的 table 存储方式很像 )。  marrays 的长度是 mhashes 的 2 倍，毕竟 marrays 是 key, value 都要存嘛~

mhashes 中存放 key 的 hash 值，是从小到大排列的，如果有多个 key 的 hash 值有一样的，那么就挨着排列

当往 arraymap 中进行 put(key, value) 时，先 int hash = key.hashcode, 然后通过二分查找在 mhashes 中查找 hash 的位置( 如果里面有，就返回，如果无，就先找到最接近的位置，然后进行取反操作并返回 )  index，如果 index > 0 ，那么再去 marrays 中 2 * index 处获取 key 值，比对两个 key 是否 equals(), 如果不相等，那么再分别向上、向下查找附近相同 hash 值的 key ，看是否有 equals() 的 key, 若有，则替换，若无，则插入;    如果 index < 0 ，表示之前没有相等 hash 的 key 插入过，那么 index = ~index( 再次取反，就是个正数了，代办要插入的位置)， 再在 mhashes 的 index 处插入 hash， 在 marrays 的 2 * index 处插入 key, 在 (2 * index ) + 1 处，插入 value .

注意：

mhashes 和 marrays 在插入新数据时，都需要把插入位置后面的数据向后移动一个单位，这个对于频繁插入、删除的动作来说消耗比较大.

key 的 hash 大小决定了插入的顺序

3.以数字为 key 的数组存储

这类的 map 比较特殊，key 是数字类型。  这个以 android 中新增的 sparsearray 进行分析。 sparsearray 中有两个主要变量， int[]  mkeys  和  object[]  mvalues ， mkeys 是存放 key 的，是个有序数组，从小到大排列；  mvalues 是与 mkeys 一一对应的 value 值集合.   mkeys 和 mvalues 的长度是相等的。

当往  sparsearray 中 put(key, value) 时，先用二分查找在 mkeys 中查找 key 所在的位置 (如果找到，返回； 如果没有找到，则找到它应该插入的位置，取反并返回) ，记为 index， index > 0 ，则直接在 mvalues[index] 处替换 value; 如果 index < 0 ，则 index = ~index， 即取反， 然后在 mkeys 的 index 处插入 key ， 在 mvalues[index] 处插入 value ，之前的数据自 index 处后移一个单位。

注意:

mkeys 和 marrays 的数据插入时，都是要进行数据移动的，对频繁插入、删除的 map 来说消耗很大.
最后了，对它们的优缺点做些对比。

hashmap : 内存占用较大，增、删的效率较高，改、查的效率一般

threadlocal.values :  内存占用一般，当数据量比较小时，增删改查的效率高；数据量大时，增删改查效率一般

arraymap: 内存占用较小，改、查的效率高，增、删的效率较低

sparsearray : 内存占用较小，改、查的效率高，增、删的效率低，且主键是数字

总结

我们不评判哪种存储方式好，一切都要以实际情况实际分析，找出最符合的那种存储，哈哈~。希望对大家有所帮助。感兴趣的朋友可以参阅：javabean和map相互转化方法代码示例  浅谈对象与map相互转化  struts2 使用ognl遍历map方法详解等。感谢大家对本站的支持。