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 条评论
登录 后参与评论

相关文章

来自专栏小狼的世界

Leetcode刷题记录:构建最大数二叉树

给定一个不含重复数字的数组,最大二叉树构建规则如下: 1、根是数组中最大的数字 2、左边的子树是最大数字左边的内容 3、右边的子树是最大数字右边的内容

11620
来自专栏绿巨人专栏

学习Scala: 初学者应该了解的知识

29540
来自专栏spring源码深度学习

为什么很多编程语言中的数组都从0开始编号?——你真的了解数组吗?

数组是学习数据结构的开端。尽管数组看起来非常基础、简单,但是有多少人理解数组的精髓呢?

12420
来自专栏CSDN技术头条

算法入门,其实可以像读小说一样有趣

我琢磨着目录,心想终于要把这些主题搞明白了。但那本书深奥难懂,看了几周后我就放弃了。直到遇到一位优秀的算法教授后,我才认识到这些概念是多么地简单而优雅。

47240
来自专栏面朝大海春暖花开

c++入门笔记

C++函数的返回值类型可以是除数组和函数以外的任何类型。 函数可以返回一个引用,将函数说明为返回一个引用的主要目的是为了将函数用在赋值运算符的左边。函数原型的表...

13040
来自专栏轮子工厂

8. 一花一世界,while for 循环?

wo这周有点懒啊,这才第 2 篇,个人有点事情,本来预计可以更新……1 篇的,︿( ̄︶ ̄)︿

12120
来自专栏noteless

java集合框架容器 java框架层级 继承图结构 集合框架的抽象类 集合框架主要实现类

java集合框架  框架设计理念  容器 继承层级结构 继承图 集合框架中的抽象类  主要的实现类 实现类特性   集合框架分类 集合框架并发包 并发实现类

17620
来自专栏和蔼的张星的图像处理专栏

372. 在O(1)时间复杂度删除链表节点复制节点的值

给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。

8520
来自专栏Fundebug

代码面试需要知道的8种数据结构(附面试题及答案链接)

为了保证可读性,本文采用意译而非直译。另外,本文版权归原作者所有,翻译仅用于学习。

17170
来自专栏aCloudDeveloper

一个交换程序的通用版本

Author:bakari   Date:2012.9.3       交换程序是每个开始学习编程的人必学习的一个初级算法。算法思想很简单,就是为两个交换的双方...

17960

扫码关注云+社区

领取腾讯云代金券