ArrayMap和HashMap区别

什么是Map?

Map的三个特点

1.包含键值对  2.键唯一  3.键对应的值唯一

一:hash

什么是Hash

Hash,也可以称为“散列”,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出(也就是多对一的关系)。

HashMap

HashMap内部是使用一个默认容量为16的数组来存储数据的,而数组中每一个元素却又是一个链表的头结点,所以,更准确的来说,HashMap内部存储结构是使用哈希表的拉链结构(数组+链表),这种存储数据的方法叫做拉链法 。如图: 

且每一个结点都是Entry类型,那么Entry是什么呢?我们来看看HashMap中Entry的属性:

1 final K key;  
2 final V value;  
3 final int hash;  
4 HashMapEntry<K, V> next;  

从中我们得知Entry存储的内容有key、value、hash值、和next下一个Entry,那么,这些Entry数据是按什么规则进行存储的呢?就是通过计算元素key的hash值,然后对HashMap中数组长度取余得到该元素存储的位置,计算公式为hash(key)%len,比如:假设hash(14)=14,hash(30)=30,hash(46)=46 我们对len取余,得到hash(14)%16=14,hash(30)%16=14,hash(46)%16=14。所以hash值为14的这个元素存储在数组下标为14的位置。

从中可以看出,如果有多个元素key的hash值相同的话,后一个元素并不会覆盖上一个元素,而是采取链表的方式,把之后加进来的元素加入链表末尾,从而解决了hash冲突的问题,由此我们知道HashMap中处理hash冲突的方法是链地址法。

在此补充一个知识点,处理hash冲突的方法有以下几种:

  1. 开放地址法
  2. 再哈希法
  3. 链地址法
  4. 建立公共溢出区

讲到这里,重点来了,我们知道HashMap中默认的存储大小就是一个容量为16的数组,所以当我们创建出一个HashMap对象时,即使里面没有任何元素,也要分别一块内存空间给它,而且,我们再不断的向HashMap里put数据时,当达到一定的容量限制时(这个容量满足这样的一个关系时候将会扩容:HashMap中的数据量>容量*加载因子,而HashMap中默认的加载因子是0.75),HashMap的空间将会扩大,而且扩大后新的空间一定是原来的2倍,我们可以看put()方法中有这样的一行代码:

1 int newCapacity = oldCapacity * 2;

所以,只要一满足扩容条件,HashMap的空间将会以2倍的规律进行增大。假如我们有几十万、几百万条数据,那么HashMap要存储完这些数据将要不断的扩容,而且在此过程中也需要不断的做hash运算,这将对我们的内存空间造成很大消耗和浪费,而且HashMap获取数据是通过遍历Entry[]数组来得到对应的元素,在数据量很大时候会比较慢,所以在Android中,HashMap是比较费内存的。

所以我们在一些情况下可以使用SparseArray和ArrayMap来代替HashMap。

二:ArrayMap

ArrayMap是一个<key,value>映射的数据结构,它设计上更多的是考虑内存的优化,内部是使用两个数组进行数据存储,一个数组记录key的hash值,另外一个数组记录Value值,它和SparseArray一样,也会对key使用二分法进行从小到大排序,在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index,然后通过index来进行添加、查找、删除等操作,所以,应用场景和SparseArray的一样,如果在数据量比较大的情况下,那么它的性能将退化至少50%。

ArrayMap方法:

public V put(K key, V value)

public V get(Objectkey)

public V remove(Objectkey)

public K keyAt(int index) 

public V valueAt(int index)

ArrayMap应用场景

  • 1.数据量不大,最好在千级以内
  • 2.数据结构类型为Map类型

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HTTP协议 详解

      body中的格式可以是任何类型的数据,但是为了得到服务端的认可,也有一些常见的格式

    Dawnzhang
  • 数据结构与算法学习笔记之 复杂度分析

    大家都知道数据结构和英语,就如同程序员的两条腿一样;只有不断的积累,学习,拥有了健壮的“双腿”才能越走越远;在数据结构和算法的领域,不得不承认自己就是一只菜...

    Dawnzhang
  • 数据结构与算法学习笔记之高效、简洁的编码技巧“递归”

    盗梦空间想象大多数人都看过:电影讲述的是主人公诺兰进入希里安·墨菲梦境植入想法的行动。为了向希里安·墨菲梦植入理念,影片进入四层梦境,即所谓:“梦中的梦中 梦中...

    Dawnzhang
  • 死磕Java之聊聊HashMap源码(基于JDK1.8)

    HashMap是Java程序员使用频率最高的数据结构之一。另外,JDK1.8对HashMap底层的实现进行了优化,如引入红黑树的数据结构以及扩容的优化等等来提高...

    haifeiWu
  • Java集合-HashMap源码解析-JDK1.8

    HashMap在jdk 1.8中使用用的是数组+链表+红黑树的结构来进行存储的,请看下图:

    Java学习录
  • JDK1.8源码分析之HashMap

    HashMap是一种Map,HashMap仅是一种Map的实现版本,下面的图片展示了java中Map的一些实现版本:

    九州暮云
  • Java集合必会14问(精选面试题整理)

    答:通过分析源码我们知道了HashMap通过resize()方法进行扩容或者初始化的操作,下面是对源码进行的一些简单分析:

    Java3y
  • Java集合必会14问(精选面试题整理)

    答:通过分析源码我们知道了HashMap通过resize()方法进行扩容或者初始化的操作,下面是对源码进行的一些简单分析:

    我没有三颗心脏
  • Java集合必会14问(精选面试题整理)

    答:通过分析源码我们知道了HashMap通过resize()方法进行扩容或者初始化的操作,下面是对源码进行的一些简单分析:

    乔戈里
  • 锦囊篇|一文摸懂ButterKnife

    于2020年3月26号,Jack Wharton 官宣 ButterKnife 废弃了。但是我们就没有必要去学习了吗?显然并不是这样的,一个开源库背后的每一分思...

    ClericYi

扫码关注云+社区

领取腾讯云代金券