HashMap中神奇的h & (length

Stella981 等级 108 0 0
标签: hashmap

众所周知,HashMap是基于Hash表的Map接口实现,HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。但是知道了Hash值之后,又是怎么确定出key在数组中的索引呢?

根据源码得知如下方法
static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值
         return h & (length-1);  

这样做有什么好处呢 ?

1、保证不会发生数组越界

首先我们要知道的是,在HashMap,数组的长度按规定一定是2的幂。因此,数组的长度的二进制形式是:10000…000, 1后面有偶数个0。 那么,length - 1 的二进制形式就是01111.111, 0后面有偶数个1。最高位是0, 和hash值相“与”,结果值一定不会比数组的长度值大,因此也就不会发生数组越界。

2、保证元素尽可能的均匀分布

由上边的分析可知,length一定是一个偶数,length - 1一定是一个奇数。假设现在数组的长度length为16,减去1后length - 1就是15,15对应的二进制是:1111。现在假设有两个元素需要插入,一个哈希值是8,二进制是1000,一个哈希值是9,二进制是1001。和1111“与”运算后,结果分别是1000和1001,它们被分配在了数组的不同位置,这样,哈希的分布非常均匀。那么,如果数组长度是奇数呢?减去1后length - 1就是偶数了,偶数对应的二进制最低位一定是 0,例如14二进制1110。对上面两个数子分别“与”运算,得到1000和1000。结果都是一样的值。那么,哈希值8和9的元素都被存储在数组同一个index位置的链表中。在操作的时候,链表中的元素越多,效率越低,因为要不停的对链表循环比较。

收藏
评论区

相关推荐

3 手写Java HashMap核心源码
手写Java HashMap核心源码 上一章手写LinkedList核心源码,本章我们来手写Java HashMap的核心源码。 我们来先了解一下HashMap的原理。HashMap 字面意思 hash map,map是映射的意思,HashMap就是用hash进行映射的意思。不明白?没关系。我们来具体讲解一下HashMap的原理。 HashMap
HashMap深度解析:一文让你彻底了解HashMap
前言 HashMap是Map族中最为常用的一种,也是 Java Collection Framework 的重要成员。本文首先给出了 HashMap 的实质并概述了其与 Map、HashSet 的关系,紧接着给出了 HashMap 在 JDK 中的定义,并结合源码分析了其四种构造方式。 最后,通过对 HashMap 的数据结构、实现原理、源码实现三
拿下面试!HashMap源码解析!!
拿下面试!HashMap源码解析!! HashMap的设计思想 HashMap的底层结构 本文主要是讲解jdk1.8中的HashMap源码,会对jdk1.7中的HashMap做一些简单的讲解用来和jdk1.8中的HashMap进行对比。 我们先通过下图来理解HashMap的底层结构: (https
一篇文章彻底读懂HashMap之HashMap源码解析
在秋招面试准备中博主找过很多关于HashMap的博客,但是秋招结束后回过头来看,感觉没有一篇全面、通俗易懂的讲解HashMap文章(可能是博主没有找到),所以在秋招结束后,写下了这篇文章,尽最大的努力把HashMap源码讲解的通俗易懂,并且尽量涵盖面试中HashMap的考察点。就博主的经历来看,HashMap是求职面试中名副其实的“明星”,基本上博主面试的每
Java HashMap的工作原理
面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下HashMap内部的工作原理。首先我们从一个例子开始,而不仅仅是从理论上,这样,有助于更好地理解,然后,我们来看下get和put到底是怎样工作的。 我们来看个非常简单的例子。有一个”国家”(Coun
Java HashMap的工作原理
面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下HashMap内部的工作原理。首先我们从一个例子开始,而不仅仅是从理论上,这样,有助于更好地理解,然后,我们来看下get和put到底是怎样工作的。 我们来看个非常简单的例子。有一个”国家”(Coun
java基础之HashMap——第一节
前两篇文章粗略的介绍了java中的List,既然已经讲了两种java的数据结构,那么这篇就接着讲java中的数据结构了。 HashMap作为最常用的一种Map,就放在第一个讲了。 Map是一个较复杂的结构,本身内容不是太难,但是各个实现的思想完全不同,所以可能关于Map的介绍会比较多,源码分析会放在后边,主要是算法分析。 要讲HashM
java集合系列之HashMap源码
java集合系列之HashMap源码 HashMap的源码可真不好消化!!! 首先简单介绍一下HashMap集合的特点。HashMap存放键值对,键值对封装在Node(代码如下,比较简单,不再介绍)节点中,Node节点实现了Map.Entry。存放的键值对的键不可重复。jdk1.8后,HashMap底层采用的是数组加链表、红黑树的数据结构,因此实现起
Collectors.groupingBy分组后的排序问题
默认groupingBy代码里会生成一个HashMap(hashMap是无序的,put的顺序与get的顺序不一致) * HashMap是无序的,HashMap在put的时候是根据key的hashcode进行hash然后放入对应的地方。所以在按照一定顺序put进HashMap中,然后遍历出HashMap的顺序跟put的顺序不同(除非在put的时候key已
GridView实现九宫格
GridView gv=(GridView)findViewById(R.id.g1);         ArrayList<HashMap<String,Object>>data=new ArrayList<HashMap<String, Object>>();         for(int i=0;i<images.length;i++)
HashMap 初始化时赋值
一般初始化一个map并且给map赋值的写法: HashMap<String, String> map = new HashMap<String, String>(); map.put("name", "test"); map.put("age", "20"); 但是我想在初始化的时候就直接给map中set值。
HashMap 怎么 hash?又如何 map?
HashMap 是 Java 中 Map 的一个实现类,它是一个双列结构(数据+链表),这样的结构使得它的查询和插入效率都很高。HashMap 允许 null 键和值,它的键唯一,元素的存储无序,并且它是线程不安全的。 ![](https://oscimg.oschina.net/oscnet/24e81018b69298cf434a8eb39682070
HashMap 简单总结
package test; import java.util.\*; public class Text { public static void main(String \[\] args){ //这里我们说一下hashmap 和 迭代问题 HashMap hs=new HashMap(); //向其中添加数据(key, value),
HashMap中神奇的h & (length
众所周知,HashMap是基于Hash表的Map接口实现,HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。但是知道了Hash值之后,又是怎么确定出key在数组中的索引呢? 根据源码得知如下方法 static
HashMap容量分析
了解过HashMap都应该知道,HashMap内部会创建一个Entry<K, V> table数组来存放元素,而且这个数组的长度永远都是2的指数次方。那么问题来了,为什么选择2的指数次方呢? 首先,思考一下计算出hash值后,应该存放在数组的哪个位置?显然用求余(模)最简单。然而模的效率并不高,看看JDK是怎么做的,indexFor方法: st