java开放地址法和链地址法解决hash冲突的方法示例
hashMap对各位小伙们来说,没有不知道的了,使用过的人想必或多或少的都了解一点hashMap的底层实现原理,总结来说就是,数组+链表,至于源码的实现,大家可参看源码,今天想说的是hashMap是怎么解决hash冲突的呢?
首先看一张图,
从这张图也大概可以看出来,hashMap维护的是一个数组,数组里面的每个单元又是一个个链表,那么为什么会产生hash冲突呢?这也就是接下来要探讨的问题。
既是数组,必然会有长度,当我们在往数组中插入数据的时候,不管是什么类型的数据,对于数组来说,就是占据了某个下标对应的空间,那么当加入的数据越来越多的时候,是否会出现多个数据占据同一个位置呢?答案是肯定的,这就是hash冲突产生的原始因素;
首先,我们先弄清楚几个概念,对于hashMap或者其他类似的map来说,我们往里面添加数据的时候,并不是直接往数组里面加,而是通过计算这个插入数据的hash值,即通过一个hash的算法,然后把这个值加进去,以后再去查找数据的时候,hashMap同样会根据你的key,倒推出这个hash值然后取出数据,即这个hash值可以理解为插入值对应的数组下表;
但通过实验我们可以发现,hash函数计算不同的key的时候,可能得到相同的hash值,这样一来,如果再用这个hash值作为数组的标识这个值的下标,就无法定位这个值了,这个时候冲突就发生了;
下面我们用代码来模拟一下这个使用开发地址法解决hash冲突的问题,首先定义一个对象,这里为Info,为了更接近真实场景,我们这里的属性都为字符串,
什么是开放地址法呢?
当冲突发生的时候,通过查找数组的一个空位,将数据插入进去,而不再用hash函数计算获取数的下标,这个方法就叫做开发地址法;
publicclassInfo{ privateStringkey; //关键字,或者能标识对象的唯一属性 privateStringname; //值域 publicInfo(Stringkey,Stringname){ this.key=key; this.name=name; } publicStringgetKey(){ returnkey; } publicvoidsetKey(Stringkey){ this.key=key; } publicStringgetName(){ returnname; } publicvoidsetName(Stringname){ this.name=name; } }
接下来手工写一个hashTable,用于模拟hashMap,
/** *模拟hashMap * */ publicclassHashTable{ privateInfo[]arr; /** *默认的构造方法 */ publicHashTable(){ arr=newInfo[100]; } /** *指定数组初始化大小 */ publicHashTable(intmaxSize){ arr=newInfo[maxSize]; } /** *插入数据 */ publicvoidinsert(Infoinfo){ //获得关键字 Stringkey=info.getKey(); //关键字所自定的哈希数 inthashVal=hashCode(key); //如果这个索引已经被占用,而且里面是一个未被删除的数据 while(arr[hashVal]!=null&&arr[hashVal].getName()!=null){ //进行递加,避免漏找 ++hashVal; //循环 hashVal%=arr.length; } arr[hashVal]=info; } /** *查找数据 */ publicInfofind(Stringkey){ inthashVal=hashCode(key); while(arr[hashVal]!=null){ if(arr[hashVal].getKey().equals(key)){ returnarr[hashVal]; } ++hashVal; hashVal%=arr.length; } returnnull; } /** *删除数据 */ publicInfodelete(Stringkey){ inthashVal=hashCode(key); //循环查找,数组中下标为hashVal的值,没有找到返回null while(arr[hashVal]!=null){ if(arr[hashVal].getKey().equals(key)){ Infotmp=arr[hashVal]; tmp.setName(null); returntmp; } ++hashVal; //由于数组的值是连续的,为了避免漏找,需要依次往下找 hashVal%=arr.length; } returnnull; } /** *获得关键字的hash值,也可以自定义 */ publicinthashCode(Stringkey){ BigIntegerhashVal=newBigInteger("0"); BigIntegerpow27=newBigInteger("1"); for(inti=key.length()-1;i>=0;i--){ intletter=key.charAt(i)-96; BigIntegerletterB=newBigInteger(String.valueOf(letter)); hashVal=hashVal.add(letterB.multiply(pow27)); pow27=pow27.multiply(newBigInteger(String.valueOf(27))); } returnhashVal.mod(newBigInteger(String.valueOf(arr.length))).intValue(); } }
可以看到,我们是通过对要插入的数值先进行hash编码,再对数值的长度进行取模i,这样得到的位置总能够落在数值的长度内,
里面有个地方可能不太好理解,就是在插入数据的时候,我们使用while循环进行插入,既然是开发地址,也就是说数组的每一个闲置的空间我们都能使用,前提是这个位置没有被其他的值占用,由于数组是连续的,所以我们需要循环的去寻找一个这样的位置,所以才有++hashVal这段代码,直到找到了一个空位,然后我们把数据插入进去,
运行测试main方法,我们看到,数据成功插入,但通过hash函数计算得到的“a”和"ct"却是一样的,再一次印证了我们前面所说的问题,
以上便是所说的采用开发地址法解决hash冲突的解决方法,但这样就万无一失了吗?
我们考虑一下,数据的长度是有限的,但我们可能会往数组里面添加很多数据进去,数组总有被填满的时候,那样开发地址法也不管用了,当然,实际业务中,如果可以预料数据的大小,我们可以采用这样的方式解决部分问题,但问题是这样确实不是万无一失的解决办法,
更合适的方式是什么呢?其实就是hashMap中使用较多的链地址法,也就是一开始我们图中展示的,基本结构仍然是一个数组,但是数组的每个单元维护的不再是一个个数据,而是一个个链表,也就是类似于linkedList这样的结构,当新插入的多个数据通过计算hash函数得到的是相同的数组下标时候,我们只需要把值往这个索引位置维护的链表中插入即可,什么是链地址法呢?
**
在hash表每个单元中设置链表,某个要插入的数据项的关键字还是像通常那样映射到hash表的某个单元中,而数据项的本身则被插入到该单元维护的链表中;
**
下面用代码来实现一下这个过程,同上面所有不同的是,链表中的结构我们通过是维护者一个个节点,即Node,对链表结构不熟悉的同学可以先自行百度一下,不是很难,
1、定义一个对象Info,
publicclassInfo{ privateStringkey; privateStringname; publicInfo(Stringkey,Stringname){ this.key=key; this.name=name; } publicStringgetKey(){ returnkey; } publicvoidsetKey(Stringkey){ this.key=key; } publicStringgetName(){ returnname; } publicvoidsetName(Stringname){ this.name=name; } }
2、定义一个Node作为链表中的基本存储单元,
publicclassNode{ //数据域 publicInfoinfo; //指针域,指向对下一个节点引用 publicNodenext; publicNode(Infoinfo){ this.info=info; } }
3、定义一个链表,
/** *模拟linkedList * *@authorasus * */ publicclassLinkList{ //头结点 privateNodefirst; publicLinkList(){ first=null; } //插入一个节点 publicvoidinsertFirst(Infoinfo){ Nodenode=newNode(info); node.next=first; first=node; } //删除一个节点,在头结点后进行删除 publicNodedeleteFirst(){ Nodetemp=first; first=temp.next; returntemp; } /** *查找方法 */ publicNodefind(Stringkey){ Nodecurrent=first; while(!key.equals(current.info.getKey())){ if(current.next==null){ returnnull; } current=current.next; } returncurrent; } /** *删除方法 */ publicNodedelete(Stringkey){ Nodecurrent=first; Nodeprevious=first; while(!key.equals(current.info.getKey())){ if(current.next==null){ returnnull; } previous=current; current=current.next; } if(current==first){ first=first.next; }else{ previous.next=current.next; } returncurrent; } }
4、模拟hashMap的几个方法,
publicclassHashTable{ privateLinkList[]arr; /** *默认的构造方法 */ publicHashTable(){ arr=newLinkList[100]; } /** *指定数组初始化大小 */ publicHashTable(intmaxSize){ arr=newLinkList[maxSize]; } /** *插入数据 */ publicvoidinsert(Infoinfo){ Stringkey=info.getKey(); //获取关键字的自定义hash函数 inthashVal=hashCode(key); if(arr[hashVal]==null){ //如果数组某个单元的位置为空,则需要重新构造一个linkList arr[hashVal]=newLinkList(); } arr[hashVal].insertFirst(info); } /** *查找数据 */ publicInfofind(Stringkey){ inthashVal=hashCode(key); returnarr[hashVal].find(key).info; } /** *删除数据 */ publicInfodelete(Stringkey){ inthashVal=hashCode(key); returnarr[hashVal].delete(key).info; } /** *自定义计算hash的函数 */ publicinthashCode(Stringkey){ BigIntegerhashVal=newBigInteger("0"); BigIntegerpow27=newBigInteger("1"); for(inti=key.length()-1;i>=0;i--){ intletter=key.charAt(i)-96; BigIntegerletterB=newBigInteger(String.valueOf(letter)); hashVal=hashVal.add(letterB.multiply(pow27)); pow27=pow27.multiply(newBigInteger(String.valueOf(27))); } returnhashVal.mod(newBigInteger(String.valueOf(arr.length))).intValue(); } }
和上面开发地址法插入数据和查找数据不同,此种方式进行数据查找的时候,其实是进行两次查到的,第一次定位数组中的位置,第二次去到链表中,调用链表的查找方法进行查找,这一点值得注意,插入和删除的思想也是类似,
下面我们来测试一下,可以看到,依然达到了效果,说明我们模拟的链地址法也生效了,
以上就是通过开发地址法和链地址法解决hash冲突的两种方式,希望对大家理解hashMap的底层原理有所帮助…感谢观看!也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。