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方法详解等。感谢大家对本站的支持。

赞 (0)

相关推荐

  • Java中遍历Map的多种方法示例及优缺点总结

    前言 关于java中的map遍历有多种方法,从最早的Iterator,到java5支持的foreach,再到java8 Lambda,让我们一起来看下具体的用法以及各自的优缺点 先初始化一个map public class TestMap { public static Map<Integer, Integer> map = new HashMap<Integer, Integer>(); } keySet values 如果只需要map的key或者value,用map的keySe

  • 利用java读取web项目中json文件为map集合方法示例

    前言 本文主要介绍了关于java读取web项目中json文件为map集合的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 实例介绍 假设当前项目web目录(/resource/test.json)下有一json文件如下: [ { "path": "content_111", "title": "文章1", "imgUrl": "../../../libs/img/ppt

  • java中用ObjectMapper类实现Json与bean的转换示例

    前言 ObjectMapper是jackson中的方法,本文主要给大家介绍了关于java中用ObjectMapper类实现Json与bean转换的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 一.将json字符串转为bean public class JsonToJavaBean { public static void main(String[] args) { String str="{\"student\":[{\"name\&q

  • Java中LinkedHashMap源码解析

    概述: LinkedHashMap实现Map继承HashMap,基于Map的哈希表和链该列表实现,具有可预知的迭代顺序. LinedHashMap维护着一个运行于所有条目的双重链表结构,该链表定义了迭代顺序,可以是插入或者访问顺序. LintHashMap的节点对象继承HashMap的节点对象,并增加了前后指针 before after: /** * LinkedHashMap节点对象 */ static class Entry<K,V> extends HashMap.Node<K,V

  • Javabean和map相互转化方法代码示例

    在做导入的时候,遇到了需要将map对象转化 成javabean的问题,也就是说,不清楚javabean的内部字段排列,只知道map的 key代表javabean的字段名,value代表值. 那现在就需要用转化工具了.是通用的哦! 首先来看 JavaBean 转化成Map的方法: [java] /** * 将一个 JavaBean 对象转化为一个 Map * @param bean 要转化的JavaBean 对象 * @return 转化出来的 Map 对象 * @throws Introspec

  • java 遍历Map及Map转化为二维数组的实例

    java 遍历Map及Map转化为二维数组的实例 实例代码: import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class Test { public static void main(String[] args) { int a = 0, b = 0, c = 0; // 第一种:通过Map.keySet()遍历Map及将Map转化为二维数组 Map<String, String>

  • Java中map内部存储方式解析

    Map,即映射,也称为 键值对,有一个 Key, 一个 Value . 比如 Groovy 语言中,  def  map = ['name' : 'liudehua', 'age' : 50 ] ,则 map[ 'name' ]  的值是 'liudehua'. 那么 Map 内部存储是怎么实现的呢?   下面慢慢讲解. 一. 使用 拉链式存储 这个以 Java 中的 HashMap 为例进行讲解.   HashMap 的内部有个数组 Entry[]  table, 这个数组就是存放数据的. E

  • Java中map遍历方式的选择问题详解

    1. 阐述 对于Java中Map的遍历方式,很多文章都推荐使用entrySet,认为其比keySet的效率高很多.理由是:entrySet方法一次拿到所有key和value的集合:而keySet拿到的只是key的集合,针对每个key,都要去Map中额外查找一次value,从而降低了总体效率.那么实际情况如何呢? 为了解遍历性能的真实差距,包括在遍历key+value.遍历key.遍历value等不同场景下的差异,我试着进行了一些对比测试. 2. 对比测试 一开始只进行了简单的测试,但结果却表明k

  • Java中Map的遍历方法及性能测试

    1. 阐述 对于Java中Map的遍历方式,很多文章都推荐使用entrySet,认为其比keySet的效率高很多.理由是:entrySet方法一次拿到所有key和value的集合:而keySet拿到的只是key的集合,针对每个key,都要去Map中额外查找一次value,从而降低了总体效率.那么实际情况如何呢? 为了解遍历性能的真实差距,包括在遍历key+value.遍历key.遍历value等不同场景下的差异,我试着进行了一些对比测试. 2. 对比测试 一开始只进行了简单的测试,但结果却表明k

  • Java中Map实现线程安全的3种方式

    目录 方式1. 使用Hashtable 方式2. 使用Collections.synchronizedMap(newHashtable()) 方式3. 使用ConcurrentHashMap 方式1.  使用Hashtable Map<String,Object> hashtable=new Hashtable<String,Object>(); 这是所有人最先想到的,那为什么它是线程安全的?那就看看它的源码,我们可以看出我们常用的put,get,containsKey等方法都是同

  • Java中Map集合中的Entry对象用法

    Entry: 键值对 对象. 在Map类设计是,提供了一个嵌套接口(static修饰的接口):Entry.Entry将键值对的对应关系封装成了对象,即键值对对象,这样我们在遍历Map集合时,就可以从每一个键值对(Entry)对象中获取对应的键与对应的值. Entry为什么是静态的? Entry是Map接口中提供的一个静态内部嵌套接口,修饰为静态可以通过类名调用. Map集合遍历键值对的方式: Set<Map.Entry<K,V>> entrySet(); //返回此映射中包含的映射

  • 分析Java中Map的遍历性能问题

    分析Java中Map的遍历性能问题

    一.引言 我们知道java HashMap的扩容是有成本的,为了减少扩容的次数和成本,可以给HashMap设置初始容量大小,如下所示: HashMap<string, integer=""> map0 = new HashMap<string, integer="">(100000); 但是在实际使用的过程中,发现性能不但没有提升,反而显著下降了!代码里对HashMap的操作也只有遍历了,看来是遍历出了问题,于是做了一番测试,得到如下结果:

  • Java中Map接口使用以及有关集合的面试知识点汇总

    目录 Map接口 存储特点 常用实现类 创建方法 常用方法 遍历方法 不同实现类的使用 集合面试知识点补充 结语 Map接口 存储特点 以键(key)值(value)对的形式存储 键无序.无下标.元素不可重复 值无序.无下标.元素可以重复 常用实现类 HashMapJDK1.2 底层哈希表实现 线程不安全,效率高 LinkedHashMapJDK1.2 是HashMap的子类,底层哈希表实现 线程不安全,效率高 TreeMapJDK1.2 是SortedMap的实现类,底层红黑树实现 线程不安全

  • Android开发笔记之Android中数据的存储方式（一）

    对于开发平台来讲,如果对数据的存储有良好的支持,那么对应用程序的开发将会有很大的促进作用. 总体的来讲,数据存储方式有三种:一个是文件,一个是数据库,另一个则是网络.其中文件和数据库可能用的稍多一些,文件用起来较为方便,程序可以自己定义格式:数据库用起稍烦锁一些,但它有它的优点,比如在海量数据时性能优越,有查询功能,可以加密,可以加锁,可以跨应用,跨平台等等:网络,则用于比较重要的事情,比如科研,勘探,航空等实时采集到的数据需要马上通过网络传输到数据处理中心进行存储并进行处理,有实时性的需求等.

  • Java中Map的entrySet()使用说明

    由于Map中存放的元素均为键值对,故每一个键值对必然存在一个映射关系. Map中采用Entry内部类来表示一个映射项,映射项包含Key和Value Map.Entry里面包含getKey()和getValue()方法 Set<Entry<T,V>> entrySet() 该方法返回值就是这个map中各个键值对映射关系的集合. 可使用它对map进行遍历. Iterator<Map.Entry<Integer, Integer>> it=map.entrySet

  • java中Map、Set、List的简单使用教程（快速入门）

    java中Map、Set、List的简单使用教程（快速入门）

    Map.Set.List List的常用方法 1.创建 List<Integer> list = new ArrayList<>(); List<Integer> list = new LinkedList<>(); //同时可以作为链表用 List<List<Integer>> list = new ArrayList<>(); 2.遍历 //本质上其实是调用Iterator for(String s:list){ Sy

随机推荐