专栏首页每天学点Android知识ArrayMap数据结构分析

ArrayMap数据结构分析

ArrayMap是Android上特有的一个性能比较高的Map,和HashMap一样,也实现了Map接口。

这里只分析其数据结构部分,不分析其高效缓存部分。

分析

ArrayMap的结构是int[] mHashes,记录每个key的hash值;Object[] mArray记录Key和Value,对于每一组Key和Value,按照Key和Value的顺序排列。

put(K,V)时,首先根据K计算出来一个Hash值,然后在mHashes中使用二分查找来查找这个Hash值,既然能使用二分查找也就是说,这个mHashs数组是有序的,得到了index后,再在mArray中查找,其中index2表示key的位置,index2+1表示value的位置。

mHashes虽然是个有序的,但却是可以重复的;对于重复的mHashs,在mArray中进行匹配时是通过Key#equals()方法来判断是否相同的。

举个例子:

class SameHashObj(val num:Int){

    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (other !is SameHashObj) return false

        if (num != other.num) return false

        return true
    }

    override fun hashCode(): Int {
        return num%4
    }
}

SameHashObj持有一个int,equals就是比较num值是否相同;而hashCode()这里为了测试,对4取了个模。

进行下列代码:

val arrayMap=ArrayMap<SameHashObj,String>()

        arrayMap[SameHashObj(0)] = "0"

        arrayMap[SameHashObj(1)] = "1"
        arrayMap[SameHashObj(2)] = "2"
        arrayMap[SameHashObj(3)] = "3"

        arrayMap[SameHashObj(4)] = "4"

最终结构是这样的:

对于SameHashObj(0)和SameHashObj(4),虽然hashCode都是0,但是其equals却不同,所以会出现上面的现象。

多说一点

ArrayMap一共有三个构造方法,其中有一个是hide的,如下:

public ArrayMap() {
        this(0, false);
    }

    /**
     * Create a new ArrayMap with a given initial capacity.
     */
    public ArrayMap(int capacity) {
        this(capacity, false);
    }

    /** {@hide} */
    public ArrayMap(int capacity, boolean identityHashCode) {
        mIdentityHashCode = identityHashCode;

        // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
        // instance instead of the usual EmptyArray.INT. The reference
        // is checked later to see if the array is allowed to grow.
        if (capacity < 0) {
            mHashes = EMPTY_IMMUTABLE_INTS;
            mArray = EmptyArray.OBJECT;
        } else if (capacity == 0) {
            mHashes = EmptyArray.INT;
            mArray = EmptyArray.OBJECT;
        } else {
            allocArrays(capacity);
        }
        mSize = 0;
    }

区别就是identityHashCode这个值的定义问题,我们一般能用到的就是false。下面试着用反射来初始化一个为true的ArrayMap,看看有啥变化。

结构如下图了:

可以看到mHashes数组,那是个啥鬼?

这个identityHashCode到底是啥作用呢?看名字,应该可以猜得出来,对于默认的情况,是允许mHashes中出现相同的值的,比如说上面的情况。

put()方法中有如下代码:

    public V put(K key, V value) {
        final int osize = mSize;
        final int hash;
        int index;
        if (key == null) {
            hash = 0;
            index = indexOfNull();
        } else {
            hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
            index = indexOf(key, hash);
        }
        ...
}

如果mIdentityHashCode=true,那么会使用System.identityHashCode(key)来计算Key的hashCode,否则就是key的hashCode方法。

对于默认的情况,就会调用SameHashObj重写的hashCode()方法;对于true的情况下,最终会调用到没有重写hashCode()的情况,而默认的hashCode()方法返回的是每个对象的内存地址,所以自然每个不同的对象都是不同的,不管你hashCode()怎么实现,压根不去调你,就不会重复了。

参考

  • ArrayMap
  • 深度解读ArrayMap优势与缺陷
  • 深入剖析 Android中的 ArrayMap

本文分享自微信公众号 - 每天学点Android知识(android_every_day),作者:星风coder

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-29

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 闲话元注解@Retention

    元注解是用来描述注解的。@Retention用来描述注解将会在哪个层次存在,有三个值:

    用户1108631
  • 玩Android客户端(1)——搭建主页面

    最近在学Flutter,想着画点时间做个app,就做玩Android,可以利用现有的APi进行操作。 第一步:搭建主页面,如下:

    用户1108631
  • EventBus源码分析之发布流程

    继上篇文章EventBus源码分析之订阅流程之后,继续介绍EventBus的发布,事件发送完,EventBus如何做到调用之前注册的方法。

    用户1108631
  • Python学习入门基础教程

      在if分支判断语句里的条件判断语句不一定就是一个表达式,可以是多个(布尔)表达式的组合关系运算,这里如何使用更多的关系表达式构建出一个比较复杂的条件判断呢...

    py3study
  • 小甲鱼《零基础学习Python》课后笔记(四):改进我们的小游戏

    会一直打印直到电脑内存被占用完。字符串‘C’是一个非0值,所以while语句判断为真,就会一直打印。

    小火柴棒
  • 筹码分布原理探索

    最近在学习一点股票的知识,可是发现自己在像个小白,找不到门路,可是如果不学习就会变韭菜。人们常说股市就如同赌博,这没有问题。但谁能说去买菜或者买东西...

    用户5602455
  • [牛客OI测试赛2]F假的数学游戏(斯特灵公式)

    $n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n$

    attack
  • SpringFramework之ControllerAdvice注解的源码分析

        我们会通过@ControllerAdvice和@ExceptionHandler来处理异常,Springmvc是如何进行处理的呢?

    克虏伯
  • leetcode: 47. Permutations II

    JNingWei
  • 中小企业生存多艰?拼多多开出了一道新方子

    根据QuestMobile和猎豹大数据的相关数据显示,截止2018年9月,拼多多的一二线城市的用户占比接近50%。这意味着,拼多多不再是人们印象中的只做“五环外...

    罗超频道

扫码关注云+社区

领取腾讯云代金券