您好、欢迎来到现金彩票网!
当前位置:秒速牛牛投注 > 桶链算法 >

HashMap的深入了解

发布时间:2019-09-01 20:02 来源:未知 编辑:admin

  HashMap在日常开发中使用频率非常高的用于键值对处理的数据类型。在JDK1.8中,对HashMap底层进行了优化,引入了红黑树的数据结构和扩容的优化,在这里就深入了解一下HashMap的结构实现和功能原理。深入了解这些特点,对工作编码(面试)有很大的帮助。

  根据键(Key)的HashCode值存储数据,大多数情况下可以直接定位到他的值,因而具有很快的访问速度,但遍历顺序是不确定的。HashMap最多允许一条记录的键为null,允许多条记录的值(value)为null。HashMap非线程安全,如果同一时刻多个线程同时写HashMap,则可能导致数据的不一致。如果需要满足线程安全,可以使用Collections的SynchronizedMap方法使HashMap具有线程安全的能力,或者可以使用ConcurrentHashMap。

  LinkedMapMap是HashMap的一个子类,保留了输入的插入顺序,在遍历LinkedMapMap时,先得到的记录是先插入的,也可以在构造时带参数,按照访问次序排序。

  TreeMap实现了SortedMap接口,能够把它保存的记录根据键排序,默认是升序,也可以指定排序的比较器,当遍历TreeMap时,得到的记录是排过序的。在使用TreeMap时,必须实现Compareble接口或在构造时传入自定义的Comparetor,否则会在运行时抛出g.ClassCastException类型的异常。

  在以上四个实现类中,要求映射的key是不可变对对象。该对象创建对应的哈希值后不会被改变。如果哈希值改变。可能会定位不到对应的的value值了。

  从结构实现上来讲,HashMap是数组+链表+红黑树实现的。盗一张特别棒的图。

  Node是HashMap中的一个内部类,实现了Map.Entry接口(Entry接口是Map接口中的一个内部接口),本质是一个映射。

  (2)HashMap就是使用哈希表来存值的。哈希表为解决冲突,可以采用k开放地址法和链地址法来解决问题,Java中HashMap采用了链地址法。链地址法,就是数组加链表的结合。在每个数组元素上都是一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标的链表上。

  会先调用系统的hashCode()方法得到hashCode值,然后通过Hash算法的后两步运算来定位该键值的存储位置(在哈希桶数组中的下标)。如果两个key值的HashCode相同,则发生了Hash碰撞,所以需要将两个Node放在哈希桶数组中同一存储位置的链表中。Hash算法计算结果越均匀,Hash碰撞的几率越小,map的存储效率就会越高。

  如果哈希桶数组很大,即使较差的Hash算法也会分布的比较分散,如果哈希桶数组很小,即使很好的Hash算法也会出现较多碰撞,所以就需要在空间和时间成本之间权衡,其实就是根据实际情况确定哈希桶数组的大小,并在此基础上设计好的Hash算法减少Hash碰撞。

  首先,Node[]的初始长度是length(默认值是16),loadFactor为负载因子(默认值是0.75),shreshold是HashMap所能容纳键值对的最大数量,threshold = length * Load factor。也就是说,在定义好长度后,负载因子越大(可以大于1),所能容纳的键值对越多。

  当键值对的数量大于threshold时,HashMap会对threshold扩容,容量变为之前的两倍。默认的负载因子系数0.75是对空间和时间效率的一个平衡选择,一般不需要修改。如果内存空间很多而且对时间效率要求高,可以降低负载因子系数的值(提高哈希桶中的每个位置只有一个键值对的概率);如果空间紧张且对时间效率要求不高,可以增加负载因子系数的值。

  size是HashMap中实际存在的键值对。modCount字段用来记录HashMap内部结构发生变化的次数(链表变为红黑树,红黑树变为链表,扩容),主要用于迭代的快速失败。key对应的value被覆盖不算结构变化。

  (4)在HashMap中,哈希桶数组的长度必须为2的N次方,这是一种非常规的设计,常规设计是把桶的大小设计为素数。

  HashTable初始化桶的大小为11,就是桶数为素数的应用(Hashtable扩容后不能保证还是素数)。

  HashMap采用非常规设计,主要是为了在取模和扩容时做优化,同时为了减少冲突,HashMap定位桶索引位置时,也加入了高位参与运算的过程。

  (5)即使负载因子和Hash算法设计的再合理,也避免不了拉链过长的情况,一旦拉链过长,则会严重影响HashMap的性能。所以在JDK1.8中,对数据结构进行了进一步的优化,引入了红黑树。当拉链大于8时,链表会转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能。当拉链小于6时,红黑树会转换为链表。

  好的确定索引位置算法,可以使哈希桶中元素的位置分布的均匀,当使用hash算法获取位置时,可以直接得到元素,而不需要遍历连表,大大优化查询效率。

  这里的Hash算法本质有三步,取key的hashCode,高位运算,取模运算。

  ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

  ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

  ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

  ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

  ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

  ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

  扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。Java中的数组是无法扩容的,所以是用一个新的数组代替原有的数组。

  在多线程使用场景中,应该尽量避免使用HashMap,而使用线程安全的ConcurrentHashMap。在多线程并发的情况下,使用HashMap可能造成死循环。

  HashMap的逻辑是先进行插入,插入后判断容量是否达到threshold,到达阈值后进行扩容。如果两个线程插入数据后,都需要对哈希桶进行扩容。先扩容的线程的会通过计算hashCode,找到数组索引位置,指定某个节点A和A的next节点B;第二个线程再次扩容操作,该索引位置的节点设为B,然后将B的next节点设置为A,这样就造成了死循环。

  扩容是一个特别消耗性能的操作,所以在使用HashMap时,要给定一个大致的数值,避免HashMap频繁的扩容。

  深入了解HashMap,代表小生对HashMap的是用过程中的一些分析与见解,如果有不准确的地方还希望批评指正....博文来自:congspark的博客

  昨天面试官问我 用java实现hashmap我直接蒙蔽了,所以回来看了看hashmap是个什么东西?via:什么是哈希表和哈希算法?比如这里有一万首歌,给你一首新的歌X,要求你确认这首歌是否在那一万首...博文来自:的博客

  Map类关系图HashMap(Java8以前):数组+链表(非synchronized)Java8及以后:数组+链表+红黑树观看源码不要立即卡在细节中,而是要先过整体,了解程序的主要设计再来看细节。H...博文来自:u012919352的博客

  工作一到五年的程序员出去面试,大部分人都会被问到hashmap源码,因为hashmap是一个非常经典的数据结构,所以很有必要研究一下hashmap在jdk1.8中的源码。首先谈一下hashmap的数据...博文来自:LE_912的博客

  hash:散列讲一个任意长度通过某种hash函数算出一个固定值Java通过移位来实现通过hash出来的一个指,通过值定为到map,然后value存储在这个map中源码分析:初始化容量1左移4位=16h...博文来自:GeekTeamXin的博客

  【HashMap简介】    ①HashMap是java中最常用的集合类框架之一,是java语言中非常典型的数据结构,是一个散列表,它存储的内容是键值对(key-value)映射。    ②HashM...博文来自:Summer

  1.HashMap数据结构首先先看下HashMap的数据结构图我们都知道数组的储存方式在是连续的,查找速度比较快,但插入和删除数据比较慢而链表的存储方式是非连续的,所以插入和删除速度较快,但查找速度就...博文来自:xhbsss的博客

  hashmap关注个人开源项目hashmap是实现map接口的实现类,是线程非安全的,所以效率大于hashtablehashmap默认有4个构造方法HashMap()构造一个具有默认初始容量(16)和...博文来自:haoxd的博客

  HashMap是JavaColletionFramework的重要成员,HashMap是Map接口的常用实现类,在我们平常开发时会经常使用到Map,在我们面试的时候也会问到map的存储原理,今天特地来...博文来自:漫长学习路

  HashMapkey映射到value的集合。HashMap的初始容量是16,默认加载因子是0.75,HashMap的容量一定会是2的倍数。所有的集合类都是使用数组来保存数据,只不过这个数组的大小可以自...博文来自:wanglong1615的专栏

  最近在研究一下HashMap,发现annegu写的一篇文章很好,就先记录下来,免的以后难找。博文来自:oceanson23的专栏

  众所周知,hashMap的使用率在开发中有着极高的位置,而且在面试中也是经典。下面让我们走进hashMap的世界。一、HashMap的数据结构当我们打开hashMap的源码时候,发现一堆堆的代码,看起...博文来自:不积跬步无以至千里

  感言昨天参加了支付宝的电话一面,备受打击,更多的是让自己明白了自己的缺陷在哪,以及了解了互联网公司面试是怎样问问题的。从结果来看,肯定是挂了,因为只谈了46分钟。从自我来看,收获满满,4个字评...博文来自:RojerAlone的博客

  HashMap主要用来做什么?为什么要这么做?hashmap我们都用过很多次了,主要目的就是为了加快我们的查找速度。我们学过数据结构的都知道,数组的查询和修改速度很快,但是增加一个元素或者删除一个元素...博文来自:weixin_33924220的博客

  Hashcode方法Java中的hashcode方法就是根据一定的规则将与对象相关的信息(比如对象的存储地址,对象的字段等)映射成一个数值,这个数值称作为散列值。Hashcode是用来查找的。我们这个...博文来自:weixin_43803139的博客

  以前学习HahsMap都是粗略的了解一下,能够用就行了。这次对HahsMap的源代码看了几遍,对此有一定的理解,就我的理解我总结出如下几点。但在此之前,我们先说下HahsMap的结构,简单来说:Hah...博文来自:YL—博客

  第一周:n内容包括,Java环境搭建,变量,数据类型,二进制,if/else,switch,for,while,do while等基础语法内容n n第二周:n讲解数组及面向对象的相关技术,封装,继承,多态,还有面向对象的实战讲解n n第三周:n讲解集合及IO流,这两项在后期的项目开发中尤其重要,在面试中也占有非常重要的比重n n第四周:n讲解异常,多线程,网络编程,内存分析,内部类

  HashMap是数组+链表的组合体,底层结构其实就是一个数组结构,数组中的每一项又是一个链表,当新创建一个HashMap的时候,就初始化一个数组。如下图所示:   (盗图一张)            ...博文来自:兔兔耶耶

  之前陆陆续续推出了一系列HashMap的源码解析和算法解析,到这里hashmap的学习就告一段落了,大家可以点下面的传送门查看相应的章节:深入理解HashMap(一)hashmap所用算法、构造函数深...博文来自:BodyCoding

  目录1.HashMap是如何实现原理?2.HashMap采用的hash算法是什么?3.为什么map进行2倍扩容?4.HashMap的扩容机制?5.为什么要引入红黑树?6.红黑树专题7.多线程下Hash...博文来自:的博客

  1.绪论在Java数据结构中HashMap的实现,是相对复杂一点的了,其在Java数据结构中比较有代表性的了,面试中凡是问到Java数据结构,HashMap会被反复的问到,由此也可以看出,它是Java...博文来自:MrCao杰罗尔德的博客

  **概述:**HashMap是我们常用的一种集合类,数据以键值对的形式存储。我们可以在HashMap中存储指定的key,value键值对;也可以根据key值从HashMap中取出相应的value值;也...博文来自:马一凡的博客

  深入理解JavaHashMap本文我们探索java集合框架中最受欢迎Map接口实现类。首先我们需要指出,List和Set集合接口继承自Collection,但Map不是。简单地说,HashMap通过键...博文来自:neweastsun的专栏

  本文来自:高爽Coder,原文地址:,转载请注明。 HashMap可以说是Java中最常用的集合...博文来自:ydlmlh的专栏

  想必对于一个Java开发程序员来说,HashMap用的不少了,当被人问起你了解HashMap的时候,也许你会说:HashMap是线程不安全的,HashMap采取K,V的形式存储,HashMap是高效,...博文来自:ninetyhe的博客

  最近做项目的时候,添加了阿里的代码规范扫描插件扫描的时候指出我的HashMap未指定初始化大小,这是不规范的推荐:HashMap集合初始化时,指定集合初始值大小。网上给的解释是:不指定的话,hashM...博文来自:Fyf_010316的博客

  一、二叉树性质若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;任意节点的左、右子树也分别为二叉查找树。没有键值相...博文来自:SeanXu Blogs

  首先转载一个不错的讲解,在网上看了那么多都是吧hashMap的源码贴上去。说起来没有一点儿实际形象意义。下面的这个还是不错的,学习了!博文来自:SmallSunL的博客

  **以下是具体的put过程(JDK1.8版)1、对Key求Hash值,然后再计算下标**2、如果没有碰撞,直接放入桶中(碰撞的意思是计算得到的Hash值相同,需要放到同一个bucket中)3、如果碰撞...博文来自:weixin_44675503的博客

  详细讲解示波器中各个参数和功能,并解释这么参数和功能之间的互相影响关系。

  多个关键字请用空格分隔,最多填写5个多个关键字请用空格分隔,最多填写5个

  Azul Systems CTO & co-Founder, Gil Tene 在SpringOne2GX 2012大会上发表的演讲资料,全面深入地阐述Java垃圾回收的四种机制。并介绍了当今世界上性能与吞吐量最高的JVM产品Zi...

http://duchtech.com/tongliansuanfa/509.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有