hashmap

关键词：

1.HashMap源码

1.1 类Node代码

    HashMap内部存储的单元是Node，Node类源码如下：

??

 

1.2 HashMap数据结构

   HashMap数据结构是由Node数组及每个数组元素都是单向链表组成的，结构如下图：

?

 

  1.3  HashMap get操作  

  get操作就是根据key找到value值。首先key算出hash值，然后调用getNode方法找到value。

? ?

   已知HashMap table长度为n，n为2的m次方，即n=2^m,  然后通过hash算法（n-1)&hash算出下hash的二进制低m位作为table的index值，

  从而索引到Node节点，判断此节点hash值和查找的key的值以及key是否相等，相等的话继续沿着此链表查找，知道查找到满足前两个条件

  返回此Node节点，否则返回空。当节点数超过7个，链表转化为红黑树存储，查询就在此红黑树上进行。

 ?

 

?

 

1.4 HashMap put操作

   HashMap put操作插入对应的key和value。同样先算出key的hash值，然后调用putVal方法。

??

putVal方法,同样首先根据hash(key)&(n-1)取得hash值二进制低m位找到index，这样的散列算法使key比较均匀的分布在各个桶里，找到

index索引到Node节点，如果为空，直接put在此节点，否则判断是否是红黑树，如果是则找到红黑树部分的节点则直接put，否则查找

链表中下一个Node节点的key值和hash等于插入的key和hash值的话直接更新Node节点的value值，否则找到Node节点为NULL的节点，

判断链表个数是否超过阈值7，超过链表转换为红黑树，不超过在链表new 新出的节点，然后判断HashMap的节点数是否大于阈值

（负载因子*table的长度），大于的话resize扩容，否则不扩容。

??

put方法示意图如下：

?

1.5 HashMap resize操作

HashMap resize方法首先计算出新的HashMap的容量newCap和新的threshold newThr。判断旧的map容量oldCap大于0并且大于最大容量，

则newThr设置为整形最大值，如果oldCap小于最大容量，则newCap扩大一倍，newThr也扩大一倍，当oldCap<=0&&oldThr>0更新newThr

等于oldThr，当oldCap<=0&&oldThr<=0时newCap设置为默认值，newThr设置为默认值（负载因子*16），当newThr=0时重新计算newThr的值。

??

计算完newCap和newThr后，开始HashMap的重新散列，因为Map的length(oldCap)发生变化,数据分布hash方法(length-1)&hash计算出来的索引值

有可能会变化，所以数据需要重新分布。方法是：先便利table数组，分别对数组元素对应每个链表执行rehash。如果链表只有一个节点，则只用计算

此节点对应的新的下标直接赋值即可，如果对应是红黑树，按照红黑树的逻辑去执行，如果是链表，则遍历每个链表，对应对一个节点重新计算出index，

jdk设计精巧体现在这里：因为hash方法(n-1)&hash，所以对于同一个key值，hash值一样，唯一的不同就是长度n，假设n是2的m次方，HashMap扩容之后

n扩大两倍，m加1，所以(n-1)&hash由之前的二进制取低m位变成了取低m+1位，前m位都是一样的，所以差别是第m+1位和1与计算后的结果，有两种情况

一是0，这种情况和扩容之前的取低m位一样，所以index也是一样，另一种情况是1，这种情况相当于2^m+扩容之前的index，第m+1位数字也可以用oldCap&hash

计算出等于0索引值不变，等于1索引值+2^m。所以链表就相应拆成两部分，一部分是索引等于index，一部分等于index+2^m。

?
?

?

PS:初始化长度：

?

因为Java规定了static final 类型为静态类变量 int 类型。int类型限制了该变量的长度为4个字节共32个二进制位，最高位是符号位。

hashmap

HashMap可以接受null键值和值，而Hashtable则不能；HashMap是非synchronized;HashMap很快；以及HashMap储存的是键值对HashMap是基于hashing的原理，使用put(key,value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和... 查看详情

hashmap----工作原理

 　　 　　先来些简单的问题　　“你用过HashMap吗？”“什么是HashMap？你为什么用到它？”　　几乎每个人都会回答“是的”，然后回答HashMap的一些特性，譬如HashMap可以接受null键值和值，而HashTable则不能；HashMap是非syn... 查看详情

hashmap问答

一、什么是HashMap二、HashMap的继承关系三、HashMap数据结构四、HashMap查找、添加元素是怎样的五、什么是Hash碰撞六、HashMap是线程安全的吗？七、HashMap怎样处理null一、什么是HashMapHashMap是一个key-value集合，结合了数组和链表的优... 查看详情

java中hashmap详解(代码片段)

HashMap详细解析HashMap的实现原理HashMap的数据结构HashMap构造函数HashMap重要方法hash(K)put(K,V)resize()treeifyBin()get(K)Hash冲突HashMap总结HashMap中MAXIMUM_CAPACITY设置为1<<30HashMap中容量设置为2的整数幂次方HashMap中的负载因子设置为0.75HashMap... 查看详情

hashmap学习

HashMap类在java.util中HashMap类似Python的字典数据类型。HashMap也是一种键值对的数据类型。不过java中键值对表现形式是这样的{1=2,键=值}使用HashMapimportjava.util.HashMap HashMaphashmap=newHashMap(); #往HashMap添加数据hashmap.put("key","val")&n 查看详情

Hashmap 和并发 HashMap 有啥区别？ [复制]

】Hashmap和并发HashMap有啥区别？[复制]【英文标题】：whatisdifferencebetweenHashmapandconcurrentHashMap?[duplicate]Hashmap和并发HashMap有什么区别？[复制]【发布时间】：2013-07-2811:26:39【问题描述】：我是***的新手，通过谷歌搜索但无法理解它... 查看详情

将 HashMap 的创建迭代为另一个 HashMap 中的值

】将HashMap的创建迭代为另一个HashMap中的值【英文标题】：IteratethecreationofaHashMapasavalueinanotherHashMap【发布时间】：2012-11-2311:37:04【问题描述】：我有一个HashMap，键是某个类的对象，值是另一个HashMap，键是字符串，值是双精度：H... 查看详情

hashmap

HashMap是我们最常用的集合之一，同时Java8也提升了HashMap的性能。本着学习的原则，在这探讨一下HashMap。原理简单讲解下HashMap的原理：HashMap基于Hash算法，我们通过put(key,value)存储，get(key)来获取。当传入key时，HashMap会根据key.hash... 查看详情

hashmap

HashMap认识HashMapHashMap和数组的应用场景相似，都属于复合型数据容器。HashMap和数组的区别长度数组不可变HashMap可变，可以动态添加数据顺序数组有序HashMap无序管理数组通过角标管理HashMap通过键值对存储数据(键值对的对应关系... 查看详情

hashmap简析(代码片段)

HashMap简析基本使用对于HashMap的使用，主要是演示不同的操作方式，区别于List列表容器具体的初始化、元素添加，会直接结合源码分析对于更多的API使用，请参考官方提供的API手册//创建HashMap对象HashMap<Integer,String>hashMap=newHa... 查看详情

hashmap误区

HashMap简介HashMap是一个散列表，它存储的内容是键值对(key-value)映射。HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashM... 查看详情

hashmap介绍

第1部分HashMap介绍HashMap简介HashMap是一个散列表(也就是哈希表)，它存储的内容是键值对(key-value)映射。HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。HashMap的实现不是同步的，这意味着它不是线程安全的。它的k... 查看详情

hashmap:cr:csdn

HashMap相关问题1、你用过HashMap吗？什么是HashMap？你为什么用到它？用过，HashMap是基于哈希表的Map接口的非同步实现，它允许null键和null值，且HashMap依托于它的数据结构的设计，存储效率特别高，这是我用它的原因2、你知道HashMa... 查看详情

java中hashmap详解(代码片段)

HashMap详细解析HashMap的工作方式HashMap的实现原理HashMap的数据结构HashMap构造函数HashMap重要方法hash(K)put(K,V)resize()treeifyBin()get(K)Hash冲突HashMap总结HashMap中MAXIMUM_CAPACITY设置为1<<30HashMap中容量设置为2的整数幂次方HashMap中的负载因... 查看详情

hashmap1

   HashMap1.1HashMap特性？　　HashMap的特性：HashMap存储键值对，实现快速存取数据；允许null键/值；非同步；实现map接口。1.2HashMap的原理，内部数据结构？　　HashMap是基于hashing的原理，底层使用哈希表（数组+链表）实... 查看详情

hashmap嵌套hashmap(代码片段)

packagecom.yjf.esupplier.common.test;importjava.util.HashMap;importjava.util.Set;/***@authorshusheng*@descriptionHashMap嵌套HashMap*@Email[email protected]*@date2018/12/1814:46*/publicclassHashMapDemo2publicstaticvoidmain(String[]args)HashMap<String,HashMap<String,Integer>>doubleM... 查看详情

hashmap底层实现原理/hashmap与hashtable区别/hashmap与hashset区别

①HashMap的工作原理HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equ... 查看详情

hashmap的putifabsent()方法

HashMap的putIfAbsent()方法publicstaticvoidmain(String[]args)HashMap<String,Object>hashMap=newHashMap<>();Objectobj=hashMap.putIfAbsent("A",null);if(obj==null)System.out.println("Shit:NPE!");hashMap.putIfAbsent("A",16);hashMap.putIfAbsent("A", 查看详情