JDK1.7-HashMap原理 (4)

那我们回到addEntry()方法中

void addEntry(int hash, K key, V value, int bucketIndex) { /* JDK1.7以后的扩容条件;size大于等于threshold,并且新添加元素所在的索引值不等为空 也就是当size达到或超过threshold,新增加元素,只要不会引起hash冲突则不扩容; JDK1.8去掉了为null的判断 */ if ((size >= threshold) && (null != table[bucketIndex])) { //将大小扩容到原来的两倍 resize(2 * table.length); //如果key为null,将放到index为0的位置,否则进行取hash的操作 hash = (null != key) ? hash(key) : 0; //根据获取的hash值进行获取下标 bucketIndex = indexFor(hash, table.length); } //创建entry createEntry(hash, key, value, bucketIndex); }

resize()方法下面取hash操作的hash()方法和获取下标的indexFor方法都已经在上面写过,这里就不再赘述

接下来主要来看createEntry方法

void createEntry(int hash, K key, V value, int bucketIndex) { //先获取当前下标entry节点,也可能为null Entry<K, V> e = table[bucketIndex]; //如果有entry节点,那么在添加新的entry时将会形成链表 table[bucketIndex] = new Entry<>(hash, key, value, e); //将hashmap的大小加1 size++; }

因为hash值,所在下标位置都已经获取过了,所以方法传入参数直接使用

到这里put方法中putForNullKey()添加null key的方法就完成了,我们返回put方法继续

//put方法,省略一些刚刚写过的方法 int hash = hash(key); int i = indexFor(hash, table.length); //接下来,找到 table[i]处,以及该处的数据链表,看是否存在相同的key;判断key相同, // 首先判断hash值是否相等,然后再 判断key的equals方法是否相等 for (Entry<K, V> e = table[i]; e != null; e = e.next) { Object k; //首先判断hash,如果对象的hashCode方法没有被重写,那么hash值相等两个对象一定相等 //并且判断如果key相等或者key的值相等那么覆盖并返回旧的value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; //进行添加操作 addEntry(hash, key, value, i); return null;

最上面hash()和indexFor()方法上面写过,不再赘述,中间的判断覆盖参考注释应该可以理解,而下面的addEntry方法上面也写过

get方法

如果理解了put方法后,get方法会相对简单很多

public V get(Object key) { //判断如果key等于null的话,直接调用得到nullkey的方法 if (key == null) return getForNullKey(); //通过getEntry方法的到entry节点 Entry<K, V> entry = getEntry(key); //判断如果为null返回null,否则返回entry的value return null == entry ? null : entry.getValue(); }

首先来看key为null的情况

private V getForNullKey() { //如果hashmap的大小为0返回null if (size == 0) { return null; } /** 开始研究时有个问题困扰着我,写博客时突然明白了, 问题就是既然已知key为null的entry都会被放入下标0的位置,为什么还要循环,直接获取0下标的entry覆盖不行吗 然后我在写indexFor方法时想到,不仅仅null的key下标为0,如果一个hash算法算完后通过indexFor方法 算出的下标正好是0呢,它就必须通过循环来找到那个key为null的entry */ for (Entry<K, V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }

逻辑比较简单,就不解释了,我们回到get看下一个getEntry方法

final Entry<K, V> getEntry(Object key) { //如果hashmap的大小为0返回null if (size == 0) { return null; } //判断key如果为null则返回0,否则将key进行hash int hash = (key == null) ? 0 : hash(key); //indexFor方法通过hash值和table的长度获取对应的下标 //遍历该下标下的(如果有)链表 for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //判断当前entry的key的hash如果和和参入的key相同返回当前entry节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }

到此JDK1.7中HashMap的基本get,put方法就完成了

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyzdpy.html