脚本宝典收集整理的这篇文章主要介绍了浅谈Java中的Hashmap,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
在Java
中,有一种而且我们使用很频繁的数据结构,叫做HashMap
,其实准确的来说,这是散列表
的一种冲突解决的实现,那么什么是散列表
呢?这个概念在网上可以找到很多专业的回答,这里我们就举一个很简单的例子来说明一下什么是散列表
。
首先我们要明确的一点,就是散列表肯定是用来存取东西的,那么如果我们要把西瓜
,苹果
,草莓
这三种东西按照重量
存到某个地方,方便我们后面再拿来使用,这个该如何操作呢?首先我们可以拿一个弹簧,然后使用这个弹簧将这些东西按照重量弹出去,因为重量的不同,将会落在不同的区域,这样就将这些东西“保存”了起来。如果我们后面要使用这些东西的时候,只需要按照重量再去使用一次弹簧就可以了,这样就能找到我们所需要找的。
这里我们再明确几个概念,这个例子中的几种东西,就是我们要存放的数据
,弹簧指的是hash算法
,因为这些数据的存放是无序的,所以这些概念综合起来看,称这种形式为散列表
。
还有一个问题,就是如果在这个散列表中有两个数据通过hash
算法落到了同一个区域,那么在这里就称之为冲突
,或者叫hash
冲突,在散列表中,解决冲突的方式有线性探测法
,平方探测法
,链式地址法
。。。很多种方式,在这里就不讨论每一种解决方式的利弊,我们只是对于Java
中的HashMap
作为研究。
如果看过HashMap
源码的朋友就会知道,在Java
中HashMap
是基于链式地址法来实现的,当然也有很多朋友可能不太喜欢看源码,好的,那么我们就按照HashMap
来动手写一个简单的实现。
我们先定义一个节点类。
public class Entry { PRivate Integer key; private String value; private Entry next; public Entry(Integer key, String value, Entry next){ this.key = key; this.value = value; this.next = next; } }
然后我们在定义一个CopyHashMap类。
public class CopyHashMap { private final static int DEFAULT_CApciTY = 11; private Entry[] arrEntry; public CopyHashMap(){ arrEntry = new Entry[DEFAULT_CAPCITY]; } public CopyHashMap(int size){ arrEntry = new Entry[size]; } private int hash(int key){ return key % DEFAULT_CAPCITY; } public String get(int key){ int h = hash(key); Entry entry = arrEntry[h]; for (Entry e = entry; e != null; e = e.getNext()){ if (e.getKey().equals(key)){ return e.getValue(); } } return null; } public void put(int key, String value){ int h = hash(key); Entry entry = arrEntry[h]; for (Entry e = entry; e != null; e = e.getNext()){ if (e.getKey().equals(key)){ e.setValue(value); } } arrEntry[h] = new Entry(key, value, arrEntry[h]); } }
这里只是简单的写了一个get
和put
方法,代码很简单,看一看应该都能明白,可以看到其底层实现还是依赖于一个数组,这里有一个hash
的方法,这个就是我们刚开始例子中的弹簧,对于每一个key
都要去计算对应的hash
值是多少,然后才能确定存放在数组中的哪个位置,所以能够看出,散列表
中的hash
算法的设计是非常重要的。
这段代码中还有一些东西没有做,比如remove
方法,还有rehash
方法,如果你有兴趣,那么可以动手实现一下这两个方法,rehash
的过程在这里顺便提一下,简单的说就是如果存储列表不够用的情况下,hash
表会扩容,然后将里面的数据重新hash
一次,当然这个rehash
会提前开始进行的,所以这里我们可以观察到一个现象就是如果散列表rehash
一次,对程序的性能影响还是比较大的,对了,在JDK8
中,HashMap
也做了一些改进,链式存储的时候,在其长度达到某一个定值,后面的存储方式会转为红黑树的形式,有兴趣的话可以看一下源码。
HashMap
在Java
中的使用很频繁,很多人应该都懂其原理,可能也有很多人不太明白,希望这篇文章能让大家初窥HashMap
的门道,更深入的研究就只能大家自己探索了。
以上是脚本宝典为你收集整理的浅谈Java中的Hashmap全部内容,希望文章能够帮你解决浅谈Java中的Hashmap所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。