通過HashMap原理詳解entrySet中的疑問

更新時(shí)間：2022年11月09日 10:03:09 作者：女友在高考

這篇文章主要為大家介紹了通過HashMap原理詳解entrySet中的疑問，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

HashMap底層變量

HashMap的底層的一些變量：

transient Node<K,V>[] table;        //存儲(chǔ)數(shù)據(jù)的Node數(shù)組
      transient Set<java.util.Map.Entry<K,V>> entrySet;
      transient int size;          //map中存放數(shù)據(jù)的個(gè)數(shù)，不等于table.length
      transient int modCount;         //修改的次數(shù)，防止
      int threshold;            //臨界值
      final float loadFactor;        //擴(kuò)展因子，一般情況下threshold=table.length*loadFactor;

構(gòu)造一個(gè)空的HashMap時(shí)，只有l(wèi)oadFactor被賦值為默認(rèn)的0.75。代碼如下：

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

這里我將介紹三個(gè)方法,put get remove,最后介紹entrySet()遍歷。

put()方法：

在調(diào)用put(key,value)方法時(shí)，底層調(diào)用的是這個(gè)方法:

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)==0)
              n=(tab=resize()).length;
          if((p=tab[i=(n-1)&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=0;;++binCount){
                      if((e=p.next)==null){
                          p.next=newNode(hash,key,value,null);
                          if(binCount>=TREEIFY_THRESHOLD-1)
                              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;
      }

這個(gè)方法有5個(gè)參數(shù)，第一個(gè)為hash,可以理解為對(duì)key經(jīng)過運(yùn)算之后的一個(gè)值（具體算法:(key==null)?0:(h = key.hashCode())^(h>>>16)),第二個(gè)為key，第三個(gè)為value，這些都不用說了吧，第四個(gè)為onlyIfAbsent,這里代表的是是否覆蓋，如果為false,同樣的key放在map中，后面放入的值會(huì)覆蓋原來的值，put方法在調(diào)用這個(gè)putVal()方法時(shí)，onlyIfAbsent寫死為false的，所以HashMap中，是沒有重復(fù)的key值的，后來的value會(huì)覆蓋原來的value?？聪旅娣椒ǖ谒膫€(gè)參數(shù)：

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

然后說放入過程：

先檢查table夠不夠存放數(shù)據(jù)。剛剛new出來的HashMap，table是為空的。在放入時(shí)會(huì)先進(jìn)行擴(kuò)容，按照默認(rèn)的大小16.

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

計(jì)算要放入的位置，HashMap是沒有順序的，默認(rèn)的16個(gè)索引位置中，會(huì)隨機(jī)的找一個(gè)放入。（注意：key是可以等于null的，key等于null時(shí)，計(jì)算出來的索引是0）計(jì)算索引的方法是:

(n-1)&hash                //n代表的是table的length,hash就是上面的第一個(gè)參數(shù)hash(key);

所謂的碰撞問題解析：正常情況下直接放入就行了，但是如果加入的元素和之前的元素計(jì)算出來的索引位置是一樣的。例如：新建一個(gè)HashMap,放入(1,"a")和(17,"b")時(shí)，他們計(jì)算出來的索引相同，這時(shí)第一個(gè)Node放入好之后，第二個(gè)Node不會(huì)在重新在table中占一個(gè)索引了，會(huì)在同一個(gè)索引的Node上形成鏈表。即Node1.next=Node2. Node1和Node2都在table數(shù)組里同一個(gè)索引里面。如果在放入一個(gè)(33,"c")，這個(gè)其實(shí)也是和上面兩個(gè)計(jì)算出來是同一個(gè)索引位置，會(huì)放在Node2.next=Node3.

p.next=newNode(hash,key,value,null);                  //newNode方法會(huì)新聲明一個(gè)Node

2. get(Object key)方法：

知道了put方法，get(Object key)方法就比較簡(jiǎn)單了，直接通過key算出他在table數(shù)組中的索引位置直接獲取就行了，因?yàn)橛锌赡芡粋€(gè)索引位置放了幾個(gè)元素，所以他會(huì)先找到第一個(gè)元素，然后對(duì)比hash和key是否都相等。比如，在一個(gè)初始的table中，放入(33,"a"),(17,"b")。他們的hash分別為33和17，key也分別為33和17。當(dāng)我調(diào)用get(17)時(shí)，先會(huì)根據(jù)17算出在table中的索引為1，然后取出在這個(gè)索引中的第一個(gè)元素(33,"aa")，讓對(duì)比他們的hash和key是否都相等。顯而易見，第一個(gè)元素的key和hash都是33，而我們想要get的hash和key都是17.所以不相等。那么他就會(huì)去獲取第一個(gè)元素的next是否存在，如果存在會(huì)獲取出來在判斷hash和key是否都相等。

3. remove(Object key)方法：

和get(Object key)方法類似，先計(jì)算索引位置，找出這個(gè)索引位置的第一個(gè)Node命名為p,在對(duì)比 p的key,hash和參數(shù)中的key,根據(jù)參數(shù)key計(jì)算出來的hash是否一樣，如果一樣那么就在這個(gè)索引位置的值設(shè)為null。如果在有碰撞的情況下，就會(huì)與p.next做對(duì)比，如果一樣那么p.next將指向這個(gè)p.next.next。然后這個(gè)元素沒有了指針也會(huì)就被jvm回收了。

4.entrySet()方法：

我遍歷了一個(gè)HashMap看了看，因?yàn)橄肟纯此窃趺窗雅鲎驳耐粋€(gè)索引位置的那么多數(shù)取出了的，發(fā)現(xiàn)這個(gè)代碼不是很好理解，經(jīng)過百度和自己猜測(cè)，有了一點(diǎn)了解。當(dāng)時(shí)情況是這樣的：

這個(gè)在代碼中是這樣的:調(diào)用entrySet方法來遍歷出一個(gè)個(gè)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;
       }

這個(gè)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,0,-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>0&&(tab=table)!=null){
                   int mc=modCount;
                   for(int i=0;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()里面不應(yīng)該是空的嗎？怎么能夠遍歷出值來呢？

但是debug了下下面的這個(gè)e確實(shí)是有值的。最后查找了一下資料得出，增強(qiáng)性for循環(huán)內(nèi)部是使用的iterator方法，又看了看果然EntrySet類中覆寫了iterator方法。返回的是一個(gè)new EntryIterator()，我又去找EntryIterator類，類里就只有一個(gè)方法。然后又發(fā)現(xiàn)它繼承了HashIterator類，
這個(gè)類東西就多了。

看下面的代碼:

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=0;
              if(t!=null&&size>0){         //先入先進(jìn)
                  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;
          }
      }

可以看出這個(gè)HashIterator迭代器的默認(rèn)構(gòu)造器中，會(huì)初始化一個(gè)next的變量，這個(gè)變量是在table數(shù)組中取得，索引是從0遞增的，即先入先出原則。構(gòu)造初期會(huì)從0開始找有值的索引位置，找到后將這個(gè)Node賦值給next；然后要遍歷的時(shí)候是調(diào)用nextNode()方法，這個(gè)方法是先判斷next.next是否為空，如果為空繼續(xù)往上找有值的索引位置，如果不為空就找next.next。這樣就能都遍歷出來了，是從索引0到table.length去一個(gè)個(gè)尋找遍歷的。

第一次寫自己的理解，希望多多指正！

以上就是通過HashMap原理詳解entrySet中的疑問的詳細(xì)內(nèi)容，更多關(guān)于HashMap entrySet疑問的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: