Java中map内部存储方式解析
Map，即映射，也称为键值对，有一个Key，一个Value。
比如Groovy语言中， def map=['name':'liudehua','age':50]，则map['name'] 的值是'liudehua'。
那么Map内部存储是怎么实现的呢？ 下面慢慢讲解.
一、使用拉链式存储
这个以Java中的HashMap为例进行讲解。 HashMap的内部有个数组Entry[] table，这个数组就是存放数据的。
Entry类的定义大致是:
classEntry{
Objectkey
Objectvalue
Entrynext;
}
所以，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)时，先inthash=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方法详解等。感谢大家对本站的支持。