你的位置:首页 > Java教程

[Java教程]关于hashmap的理解

首先分析第一个比较重要的方法 put 方法,源码如下

public V put(K key, V value) {if (key == null)return putForNullKey(value); //这里判断key是否为空,若为空则调用putForNullKey处理null值int hash = hash(key); //根据key的hashCode计算hash值int i = indexFor(hash, table.length);//搜索该key的hash值在table中的索引,其中table是当HashMap用于存放entry的一个数组//这里循环遍历table中对应该索引的entry,若发现存在key与put进来的key相同则覆盖其value值for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;//将key value 添加到 索引i处addEntry(hash, key, value, i);return null;}

 

 

分析上面的源码,我们可以得到下面的结论:

当我们试图将一个key-value 调用put方法放入HashMap的时候,首先会调用key的hashCode方法算出该Entry存放的位置,若两个key的hashCode相同则在table中的存储位置相同,则先调用equals方法判断两个key是否相同,相同则覆盖,不相同则产生一个Entry链表(因为table数组中一个索引位置只能放入一个Entry,所以当有多个key的hashCode相同时,这些key就会以链表的形式存在,并且最后put进来的key在链表的最前面)

 

然后则是HashMap的构造方法,这里以 HashMap(int initialCapacity, float loadFactor)这个构造器为例,源码如下

public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);// Find a power of 2 >= initialCapacityint capacity = 1;while (capacity < initialCapacity)capacity <<= 1;this.loadFactor = loadFactor;threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);table = new Entry[capacity];useAltHashing = sun.misc.VM.isBooted() &&(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);init();}

 

从上面的源码可以看出 ,初始容量不能为负数,若初始容量大于最大容量,则让它等于最大容量,负载因子必须大于0,并且传入的initialCapacity不是HashMap的容量大小,

实际容量大小的计算规则是大于传入的initialCapacity的最小的2的n次方,比如传入的initialCapacity是5 那么实际容量则是8 因为2的3次方大于5。

 

下面再分析一下HashMap的存储性能,下面的 get方法的源码

public V get(Object key) {if (key == null)return getForNullKey();Entry<K,V> entry = getEntry(key);return null == entry ? null : entry.getValue();}

 

 

 

final Entry<K,V> getEntry(Object key) {int hash = (key == null) ? 0 : hash(key);for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;}return null;}

 

再次强调一下table的概念,table就是当我们初始化一个HashMap时,会自动创建一个长度为capacity的Entry数组,我们把这个数组存放元素的位置叫“桶”,并且每个桶只存储一个Entry元素(也就是我们的键值对),并且当我们put一个键值对时,先计算key的hashCode来判断这个键值对会放入哪一个桶,所以若多个key的hashCode相同时,他们都要被放入一个桶里面,但是一个桶里面只能放入一个Entry(键值对),要解决这个问题先看下面的代码

Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;}

 

这时Entry的构造方法,我们可以看出Entry对象包含一个Entry的引用,用来指向下一个Entry,这样就解决了hashCode相同,存放冲突的问题,所以当有多个key的hashCode相同时,就会形成一个Entry链,我们从get方法可以看出当系统通过key的hashCode找到了对应的桶的时候,会遍历这个Entry链,来找到我们要取的value的key,这个时候,若刚好这个Entry在链表的末端(也就是我们最开始put进去的Entry)那么当这个链表太长了,势必会影响我们的查询性能,这个时候就引出了loadFactor(负载因子的说法),HashMap的默认附在因子是0.75,我对负载因子的理解就是,表示HashMap在什么时候扩容,也就是说若我们初始的HashMap容量是16 负载因子是0.75,那么当有12个“桶”有了Entry时,HashMap

就会扩容,并且扩大的容量是原来容量的2倍,为什么是12呢?因为0.75x16=12。并且负载因子是可以更改的,修改它的前提是如果内存比较紧张就可以适当的增加负载因子,

若空间,内存比较充足,更关注查询效率则减少负载因子。为什么会这样呢?因为若负载因子减少了,比如说减少到了0.5,默认HashMap容量大小还是16,那么当我有8个"桶"中存放了Entry数组时我就会扩容了,该桶里的Entry链相比于之前就不会那么长,从而提升了查询性能。

 

今天先到这里,下次再写。