HashMap源码中的位运算符&详解

引言

最近在读HashMap源码的时候,发现在很多运算符替代常规运算符的现象。比如说用hash & (table.length-1) 来替代取模运算hash&(table.length);用if((e.hash & oldCap) == 0)判断扩容后元素的位置等等。

1.取模运算符%底层原理

​总所周知,位运算&直接对二进制进行运算;而对于取模运算符%:a % b 相当于 a - a / b * b,底层实际上是除法器,究其根源也是由底层的减法和加法共同完成。所以其运行效率要远远小于位运算符&。

2.位运算符&如何实现取模功能

​我们先来看两个例子

5 & 7                9 & 7
0101----5            1001----9
&                         &
0111----7             0111----7
=                          =
0101----5             0001----1

​确实,hash & (table.length-1) 来实现了运算hash&(table.length)从二进制的角度来说,5%8实际上是将二进制5(0101)向右移动3位,而与7(0111)进行与运算实际上就是将位数向右移动三位。不过要注意的是,只有当length的长度为2^n时,结论才成立。

3.位运算符&在if((e.hash & oldCap) == 0)判断扩容后元素的位置

​这是出自于JDK1.8中扩容函数resize()的一行代码,用于判断在扩容后原数组中的元素是否需要移动。举个例子:

0001 1010----26                0000 1010----10                
&                              &
0001 0000----16                0001 0000----16
=                              =
0001 0000----非0               0000 0000-----0

利用hash值和oldCap进行与运算,很明显当结果大于0代表hash值大于oldCap时,下标位置变为旧数组的下标j + oldCap;若结果等于0代表小于oldCap,则下标位置不变。相比于JDK1.7重新计算每个元素的哈希值,通过高位运算(e.hash & oldCap)无疑效率更高。

到此这篇关于HashMap源码中的位运算符&详解的文章就介绍到这了,更多相关HashMap源码中的位运算符&内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2020-07-23

Java HashMap原理及实例解析

这篇文章主要介绍了Java HashMap原理及实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 示例 1 : HashMap的键值对 HashMap储存数据的方式是-- 键值对 package collection; import java.util.HashMap; public class TestCollection { public static void main(String[] args) { HashMap<String

学习Java HashMap,看这篇就够了

HashMap 是一个散列表,它存储的内容是键值对(key-value)映射. HashMap 实现了 Map 接口,根据键的 HashCode 值存储数据,具有很快的访问速度,最多允许一条记录的键为 null,不支持线程同步. HashMap 是无序的,即不会记录插入的顺序. HashMap 继承于AbstractMap,实现了 Map.Cloneable.java.io.Serializable 接口. HashMap 的 key 与 value 类型可以相同也可以不同,可以是字符串(Str

Java5种遍历HashMap数据的写法

本文介绍了最好的Java5种遍历HashMap数据的写法,分享给大家,也给自己留一个笔记,具体如下: 通过EntrySet的迭代器遍历 Iterator < Entry < Integer, String >> iterator = coursesMap.entrySet().iterator(); while (iterator.hasNext()) { Entry < Integer, String > entry = iterator.next(); System

JAVA--HashMap热门面试题

1. 为什么我们建议在定义HashMap的时候,就指定它的初始化大小呢? 答:在当我们对HashMap初始化时,如果没有为其设置初始化容量,那么系统会默认创建一个容量为16的大小的集合.当我们向HashMap中添加元素时,如果HashMap的容量值超过了它的临界值(默认16*0.75=12)时,(0.75是HashMap的加载因子)HashMap将会重新扩容到下一个2的指数次幂(2^4=16 下一个2的指数次幂是2^5=32).由于HashMap扩容要进行resize的操作,频繁的resize,

Java实现简易HashMap功能详解

本文实例讲述了Java实现简易HashMap功能.分享给大家供大家参考,具体如下: 创建节点类 节点类含有的属性:键值对(value,key)以及指向下一节点的next: 这些属性的get以及set方法 代码如下: /** * 节点类 * @author HP * */ public class Node { private Object value; private Object key; private Node next; /** * 空节点 */ public Node() { } /*

Java手写简易版HashMap的使用(存储+查找)

HashMap的基本结构 package com.liuyuhe; public class Node { int hash; Object key; Object value; Node next; } package com.liuyuhe; public class MyHashMap { Node[] table; //位桶数组 int size; //存放键值对的个数 public MyHashMap() { table=new Node[16]; } } put()方法存储键值对 p

java中hashmap容量的初始化实现

HashMap使用HashMap(int initialCapacity)对集合进行初始化. 在默认的情况下,HashMap的容量是16.但是如果用户通过构造函数指定了一个数字作为容量,那么Hash会选择大于该数字的第一个2的幂作为容量.比如如果指定了3,则容量是4:如果指定了7,则容量是8:如果指定了9,则容量是16. 为什么要设置HashMap的初始化容量 在<阿里巴巴Java开发手册>中,有一条开发建议是建议我们设置HashMap的初始化容量. 下面我们通过具体的代码来了解下为什么会这么

Java使用HashMap实现并查集

并查集的定义: 并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述. 并查集是一种树型的数

JAVA中哈希表HashMap的深入学习

深入浅出学Java--HashMap 哈希表(hash table) 也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对java集合框架中HashMap的实现原理进行讲解,并对JDK7的HashMap源码进行分析. 一.什么是哈希表 在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能 数组:采用一段连续的存储单元来存储数据.对于指定下标的查找,时间复杂度为O(1):通过给定值进

java中哈希表及其应用详解

哈希表也称为散列表,是用来存储群体对象的集合类结构. 什么是哈希表 数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系.当要查找一个对象时,只能以某种顺序(如顺序查找或二分查找)与各个元素进行比较,当数组或向量中的元素数量很多时,查找的效率会明显的降低. 一种有效的存储方式,是不与其他元素进行比较,一次存取便能得到所需要的记录.这就需要在对象的存储位置和对象的关键属性(设为 k)之间建立一个特定的对应关系(设为 f),使每个对象与一个唯一的存储位置

在Java中如何决定使用 HashMap 还是 TreeMap

HashMap简单总结: 1.HashMap 是链式数组(存储链表的数组)实现查询速度可以,而且能快速的获取key对应的value: 2.查询速度的影响因素有 容量和负载因子,容量大负载因子小查询速度快但浪费空间,反之则相反: 3.数组的index值是(key 关键字, hashcode为key的哈希值, len 数组的大小):hashcode%len的值来确定,如果容量大负载因子小则index相同(index相同也就是指向了同一个桶)的概率小,链表长度小则查询速度快,反之index相同的概率大

C#中哈希表(HashTable)用法实例详解(添加/移除/判断/遍历/排序等)

本文实例讲述了C#中哈希表(HashTable)用法.分享给大家供大家参考,具体如下: 1.  哈希表(HashTable)简述 在.NET Framework中,Hashtable是System.Collections命名空间提供的一个容器,用于处理和表现类似keyvalue的键值对,其中key通常可用来快速查找,同时key是区分大小写:value用于存储对应于key的值.Hashtable中keyvalue键值对均为object类型,所以Hashtable可以支持任何类型的keyvalue键

java数据结构和算法中哈希表知识点详解

树的结构说得差不多了,现在我们来说说一种数据结构叫做哈希表(hash table),哈希表有是干什么用的呢?我们知道树的操作的时间复杂度通常为O(logN),那有没有更快的数据结构?当然有,那就是哈希表: 1.哈希表简介 哈希表(hash table)是一种数据结构,提供很快速的插入和查找操作(有的时候甚至删除操作也是),时间复杂度为O(1),对比时间复杂度就可以知道哈希表比树的效率快得多,并且哈希表的实现也相对容易,然而没有任何一种数据结构是完美的,哈希表也是:哈希表最大的缺陷就是基于数组,因

Java中Hashtable类与HashMap类的区别详解

Hashtable类 Hashtable继承Map接口,实现一个key-value映射的哈希表.任何非空(non-null)的对象都可作为key或者value. 添加数据使用put(key, value),取出数据使用get(key),这两个基本操作的时间开销为常数. Hashtable通过initial capacity和load factor两个参数调整性能.通常缺省的load factor 0.75较好地实现了时间和空间的均衡.增大load factor可以节省空间但相应的查找时间将增大,

C#中哈希表(Hashtable)的介绍及简单用法

key通常可用来快速查找,同时key是区分大小写:value用于存储对应于key的值.Hashtable中key/value键值对均为object类型,所以Hashtable可以支持任何类型的key/value键值对 <BR><BR><BR>在哈希表中添加一个key/value键值对:HashtableObject.Add(key,value); 在哈希表中去除某个key/value键值对:HashtableObject.Remove(key); 从哈希表中移除所有元素

java中创建两表之间的触发器详解

创建一个触发器实现借书自增数量/还书自减 在 books 被借阅属性 islend 更新时在 lender 表中同时更新借书数量 amount,其中islend 属性更新后保存的是借阅人 lender 的 id,lender 中 id 是主键,books 表中 islend 是外键,连接这两张表. 两个数据库表结构在下方给出,目前写的触发器如下: CREATE TRIGGER `lendBook` AFTER UPDATE ON `books` FOR EACH ROW BEGIN UPDATE

js中哈希表的几种用法总结

1. 复制代码 代码如下: <html><head><script type="text/javascript">// by Go_Rush(我们)  from http://www.jb51.net/ var hash={    "百度"            :"http://www.baidu.com/",    "Google"        :"http://www.go

Windows Powershell使用哈希表

哈希表存放的是对,在哈希表中不再仅仅限制使用数字寻址,可以使用任意类型的数据类型寻址. 创建哈希表 之前使用@()创建数组,现在使用@{}创建哈希表,使用哈希表的键访问对应的值. PS C:Powershell> $stu=@{ Name = "小明";Age="12";sex="男" } PS C:Powershell> $stu Name Value ---- ----- Name 小明 Age 12 sex 男 PS C:Pow

JS模拟实现哈希表及应用详解

本文实例讲述了JS模拟实现哈希表及应用.分享给大家供大家参考,具体如下: 在算法中,尤其是有关数组的算法中,哈希表的使用可以很好的解决问题,所以这篇文章会记录一些有关js实现哈希表并给出解决实际问题的例子. 说明: 这篇文章所写并不是真正意义的哈希表,只是与哈希表的使用有相似之处. 第一部分:相关知识点 属性的枚举: var person = { name: "zzw", sex: "Male", age: 21 }; for (var prop in person