HashMap的内部实现-创新互联

权衡时空

创新互联建站专业提供资阳移动机房服务，为用户提供五星数据中心、电信、双线接入解决方案，用户可自行在线购买资阳移动机房服务，并享受7*24小时金牌售后服务。

HashMap是以键值对的方式存储数据的。

如果没有内存限制，那我直接用哈希Map的键作为数组的索引，取的时候直接按索引get就行了，可是地价那么贵，哪里有无限制的地盘呢。

如果没有时间限制的话，我可以把数据放到一个无序数组中，按顺序查找，迟早也能找到。可是time is money，光阴那么短暂，谁又等得起呢。

所以，HashMap做了个折中的策略，使用适当的时间和空间做出了权衡，具体可以归结为“链表散列法”，这是一个hash表处理冲突的经典方法。

链表散列

那么什么是”链表散列法”呢？看下图：

HashMap的内部实现

纵向的是一个数组，数组的每一项都是一个链表。你可以把这个数组看成是N个桶，每一个桶放着一个链子。

数组是干嘛的？数组的每一项负责放链表的。

链表是干嘛的？负责放Map数据的，比如一个HashMap有两个键，一个是key1，一个是key2。那么该链表就会分出两个节点分别存放这两个键值对（每一个键值对是打包放在Entry对象中的）。

链表是怎么链起来的？Entry包含有key、value、下一个节点next、hash值等，这个next就把各个节点串了起来。

HashMap保存数据的过程为：先计算当前要保存的键值对的哈希值（决定着当前键值对要放到哪个桶中），根据这个哈希值找到对应的桶。如果桶中没有数据，那就直接放进去。如果桶中已经放了数据（也即：桶中的链条上放着一个或者多个键值对），那就顺着桶中的这个链条一个一个比对，看有没有key与当前要保存的数据的key相同。如果有相同，直接覆盖原来key的value。如果没有相同的，那么将该元素保存在链头（最早保存的元素就会跑到链尾）。

装填因子

桶的数量决定了能放多少个HashMap，而具体用了多少个桶，则直接关系着查找的效率。打个比方，你去隔壁班找小明，班里有10个人，你很快就会找到小明，班里坐着100个人，你可能找半天才能找到。所以你去看HashMap的构造函数是这样的：

HashMap的内部实现

public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }public HashMap() {        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

HashMap的内部实现

三个构造函数都牵动着两个东西：initialCapacity，loadFactor。前者表示的是桶的初始数量（即数组大小），后者表示“装填因子”，装填因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。比如，数组初始大小为100，如果装填因子=0.6，表示当数组中存放了60个Map之后，就要把数组扩容后才能继续存放。这就是为了解决上面讲到的效率问题。

装填因子定的小了，查找数据就快些，但是浪费空间。装填因子大了，空间利用率就高，但是浪费时间。生活就是这样，顾此失彼在所难免，万事哪有两全的呢。系统权衡利弊后，默认给的装填因子是0.75，这个一般我们是不需要改动的。

除留余数

那么还有个问题。拿到一个Map的哈希值，怎么决定放到哪个桶里呢？如果最后数组中的Map数据都挤到一块儿那可不行，查询就会慢。太松了也不行，浪费空间。Java用了一招“除留余数法”，保证数据在数组中分布均匀。

“除留余数法”，就是取模。比如数组的长度是100，Map的哈希值是80，用80%100，余数是80，就放到80那个位置。但是Java可不是那样干算的呦，且看源码：

HashMap的内部实现

void addEntry(int hash, K key, V value, int bucketIndex) {        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
}

HashMap的内部实现

上面代码就是HashMap中的添加Entry数据的方法。BucketIndex就是当前Map在数组中的索引。第三行扩容且不谈，重点在indexFor方法，这个方法就是”取模”。我们点进去看一下：

HashMap的内部实现

static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";

        return h & (length-1);

}

HashMap的内部实现

H是Map的哈希值，length是数组的长度。它直接使用了一个h & (length - 1)。这一句其实就相当于对数组取模，但是直接用二进制的位操作，比数学计算要快的多。这也给了我们程序员一个启发，能用位运算时尽量用，提高逼格又提高效率。

均匀分布

还有个有趣的地方，上面代码的注释部分：length must be a non-zero power of 2，这句是说，数组的长度必须是2的n次方。

为啥是2的n次方呢？

如果不是2的n次方，比如length为15，h分别为2,3,4。那么用h & (length -1)有：

h	Length-1	h & (length -1)
0010	1110	0010，即2
0011	1110	0010，即2
0100	1110	0100，即4

你看，随便测了三个数字，就发生了碰撞。为什么会这样呢？

这是因为：如果不是2的n次方，那么2^n – 1的最低位必然为0，而0、1分别和0作“与”运算，结果都为0。也就是说，不论h为多少，h & (length - 1)的结果最低位都是0。那么数组中最低位为1的那些位置就全部空缺着，这就导致数据在数组中分布不均匀了，继而影响了查询的效率。

读取数据的时候就简单多了，通过key的hash值找到在table数组中的索引处的Entry，然后返回该key对应的value即可。

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

网页名称：HashMap的内部实现-创新互联
本文来源：https://www.cdcxhl.com/article6/gejig.html

成都网站建设公司_创新互联，为您提供网站内链、网站设计公司、移动网站建设、云服务器、电子商务、自适应网站

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容