通过HashMap原理详解entrySet中的疑问

Java
230
0
0
2023-06-14
目录
  • HashMap底层变量
  • put()方法:
  • 2. get(Object key)方法:
  • 3. remove(Object key)方法:
  • 4.entrySet()方法:
  • EntrySet类代码

HashMap底层变量

HashMap的底层的一些变量:

transient Node<K,V>[] table;        //存储数据的Node数组
      transient Set<java.util.Map.Entry<K,V>> entrySet;
      transient int size;          //map中存放数据的个数,不等于table.length
      transient int modCount;         //修改的次数,防止
      int threshold;            //临界值
      final float loadFactor;        //扩展因子,一般情况下threshold=table.length*loadFactor;

构造一个空的HashMap时,只有loadFactor被赋值为默认的0.75。代码如下:

public HashMapMmc(){
          this.loadFactor=DEFAULT_LOAD_FACTOR;
       }

这里我将介绍三个方法,put get remove,最后介绍entrySet()遍历。

put()方法:

在调用put(key,value)方法时,底层调用的是这个方法:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
              boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n,i;
    if((tab=table)==null||(n=tab.length)==)
        n=(tab=resize()).length;
    if((p=tab[i=(n-)&hash])==null)
        tab[i]=newNode(hash,key,value,null);
    else{
        Node<K,V> e;K k;
        if(p.hash==hash&&((k=p.key)==key||(k!=null&&k.equals(key))))
          e=p;
        else if(p instanceof TreeNode)
            e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);
        else{
            for(int binCount=;;++binCount){
                if((e=p.next)==null){
                    p.next=newNode(hash,key,value,null);
                    if(binCount>=TREEIFY_THRESHOLD-)
                        treeifyBin(tab,hash);
                    break;
                }
                if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))
                    break;
                p=e;
            }
        }
        if(e!=null){          // existing mapping for key
            V oldValue=e.value;
            if(!onlyIfAbsent||oldValue==null)
                e.value=value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if(++size>threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

这个方法有5个参数,第一个为hash,可以理解为对key经过运算之后的一个值(具体算法:(key==null)?0:(h = key.hashCode())^(h>>>16)),第二个为key,第三个为value,这些都不用说了吧,第四个为onlyIfAbsent,这里代表的是是否覆盖,如果为false,同样的key放在map中,后面放入的值会覆盖原来的值,put方法在调用这个putVal()方法时,onlyIfAbsent写死为false的,所以HashMap中,是没有重复的key值的,后来的value会覆盖原来的value。看下面方法第四个参数:

public V put(K key,V value ){
    return putVal(hash(key),key,value,false,true);
}

然后说放入过程:

先检查table够不够存放数据。刚刚new出来的HashMap,table是为空的。在放入时会先进行扩容,按照默认的大小16.

Node<K,V>[] newTab=(Node<K,V>[])new Node[newCap];

计算要放入的位置,HashMap是没有顺序的,默认的16个索引位置中,会随机的找一个放入。(注意:key是可以等于null的,key等于null时,计算出来的索引是0)计算索引的方法是:

(n-)&hash                //n代表的是table的length,hash就是上面的第一个参数hash(key);

所谓的碰撞问题解析:正常情况下直接放入就行了,但是如果加入的元素和之前的元素计算出来的索引位置是一样的。例如:新建一个HashMap,放入(1,"a")和(17,"b")时,他们计算出来的索引相同,这时第一个Node放入好之后,第二个Node不会在重新在table中占一个索引了,会在同一个索引的Node上形成链表。即Node1.next=Node2. Node1和Node2都在table数组里同一个索引里面。如果在放入一个(33,"c"),这个其实也是和上面两个计算出来是同一个索引位置,会放在Node2.next=Node3.

p.next=newNode(hash,key,value,null);                  //newNode方法会新声明一个Node

2. get(Object key)方法:

知道了put方法,get(Object key)方法就比较简单了,直接通过key算出他在table数组中的索引位置直接获取就行了,因为有可能同一个索引位置放了几个元素,所以他会先找到第一个元素,然后对比hash和key是否都相等。比如,在一个初始的table中,放入(33,"a"),(17,"b")。他们的hash分别为33和17,key也分别为33和17。当我调用get(17)时,先会根据17算出在table中的索引为1,然后取出在这个索引中的第一个元素(33,"aa"),让对比他们的hash和key是否都相等。显而易见,第一个元素的key和hash都是33,而我们想要get的hash和key都是17.所以不相等。那么他就会去获取第一个元素的next是否存在,如果存在会获取出来在判断hash和key是否都相等。

3. remove(Object key)方法:

和get(Object key)方法类似,先计算索引位置,找出这个索引位置的第一个Node命名为p,在对比 p的key,hash和参数中的key,根据参数key计算出来的hash是否一样,如果一样那么就在这个索引位置的值设为null。如果在有碰撞的情况下,就会与p.next做对比,如果一样那么p.next将指向这个p.next.next。然后这个元素没有了指针也会就被jvm回收了。

4.entrySet()方法:

我遍历了一个HashMap看了看,因为想看看他是怎么把碰撞的同一个索引位置的那么多数取出了的,发现这个代码不是很好理解,经过百度和自己猜测,有了一点了解。当时情况是这样的:

这个在代码中是这样的:调用entrySet方法来遍历出一个个Map.Entry

for(Map.Entry<? extends K,? extends V> e:m.entrySet()){
    K key=e.getKey();
    V value=e.getValue();
}

entrySet()方法的代码如下:

public Set<Map.Entry<K, V>> entrySet(){
     Set<Map.Entry<K, V>> es;
     return (es=entrySet)==null?(es=new EntrySet()):es;
 }

这个entrySet是等于null的,也就是说每次都是new EntrySet();

EntrySet类代码

final class EntrySet extends AbstractSet<Map.Entry<K, V>>{
     public final int size(){return size;}
     public final void clear(){HashMapMmc.this.clear();}
     public final Iterator<Map.Entry<K, V>> iterator(){
         return new EntryIterator();
     }
     public final boolean contains(Object o){
         if(!(o instanceof Map.Entry))
             return false;
         Map.Entry<?, ?> e=(Map.Entry<?, ?>) o;
         Object key=e.getKey();
         Node<K,V> candidate=getNode(hash(key),key);
         return candidate!=null&&candidate.equals(o);
     }
     public final boolean remove(Object o){
         if(o instanceof Map.Entry){
             Map.Entry<?, ?> e=(java.util.Map.Entry<?, ?>) o;
             Object key= e.getKey();
             Object value=e.getValue();
             return removeNode(hash(key), key, value, true,true)!=null;
         }
          return false;   
     }
     public final Spliterator<Map.Entry<K, V>> spliterator(){
         return new EntrySpliterator<>(HashMapMmc.this,,-1,0,0);
     }
     public final void forEach(Consumer<? super Map.Entry<K, V>> action){
         Node<K,V> [] tab;
         if(action==null)
             throw new NullPointerException();
         if(size>&&(tab=table)!=null){
             int mc=modCount;
             for(int i=;i<tab.length;++i){
                 for(Node<K,V> e=tab[i];e!=null;e=e.next)
                     action.accept(e);
             }
             if(modCount!=mc)
                 throw new ConcurrentModificationException();
         }
     }
 }

看了EntrySet之后,感觉new EntrySet()里面不应该是空的吗?怎么能够遍历出值来呢?

但是debug了下下面的这个e确实是有值的。最后查找了一下资料得出,增强性for循环内部是使用的iterator方法,又看了看果然EntrySet类中覆写了iterator方法。返回的是一个new EntryIterator(),我又去找EntryIterator类,类里就只有一个方法。然后又发现它继承了HashIterator类,

这个类东西就多了。

看下面的代码:

for(Map.Entry<? extends K,? extends V> e:m.entrySet()){}
abstract class HashIterator{
    Node<K,V> next;
    Node<K,V> current;
    int expectedModeCount;
    int index;
    HashIterator(){
        expectedModeCount=modCount;
        Node<K,V>[] t=table;
        current=next=null;
        index=;
        if(t!=null&&size>){         //先入先进
            do{}while(index<t.length&&(next=t[index++])==null);
        }
    }
    public final boolean hasNext(){
        return next!=null;
    }
    final Node<K,V> nextNode(){
        Node<K,V>[] t;
        Node<K,V> e= next;
        if(modCount!=expectedModeCount)
            throw new ConcurrentModificationException();
        if(e==null)
            throw new NoSuchElementException();
        if((next=(current=e).next)==null&&(t=table)!=null){
            do{}while(index<t.length&&(next=t[index++])==null);
        }
        return e;
    }
    public final void remove(){
        Node<K,V> p=current;
        if(p==null)
            throw new IllegalStateException();
        if(modCount!=expectedModeCount)
            throw new ConcurrentModificationException();
        current=null;
        K key=p.key;
        removeNode(hash(key),key,null,false,false);
        expectedModeCount=modCount;
    }
}

可以看出这个HashIterator迭代器的默认构造器中,会初始化一个next的变量,这个变量是在table数组中取得,索引是从0递增的,即先入先出原则。构造初期会从0开始找有值的索引位置,找到后将这个Node赋值给next;然后要遍历的时候是调用nextNode()方法,这个方法是先判断next.next是否为空,如果为空继续往上找有值的索引位置,如果不为空就找next.next。这样就能都遍历出来了,是从索引0到table.length去一个个寻找遍历的。

第一次写自己的理解,希望多多指正!