一個簡單的例子帶你理解HashMap

作者：邵磊 2020-03-26 17:00:53

我知道大家都很熟悉hashmap，并且有事沒事都會new一個，但是hashmap的一些特性大家都是看了忘，忘了再記，今天這個例子可以幫助大家很好的記住。

前言

我知道大家都很熟悉hashmap，并且有事沒事都會new一個，但是hashmap的一些特性大家都是看了忘，忘了再記，今天這個例子可以幫助大家很好的記住。

場景

用戶提交一張試卷答案到服務(wù)端，post報文可精簡為

[{"question_id":"100001","answer":"A"},  
{"question_id":"100002","answer":"A"},  
{"question_id":"100003","answer":"A"},  
{"question_id":"100004","answer":"A"}]

提交地址采用restful風(fēng)格

http://localhost:8080/exam/{試卷id}/answer

那么如何比對客戶端傳過來的題目就是這張試卷里的呢，假設(shè)用戶偽造了試卷怎么辦？

正常解決思路

得到試卷所有題目id的list
2層for循環(huán)比對題號和答案
判定分?jǐn)?shù)

大概代碼如下

//讀取post題目  
for (MexamTestpaperQuestion mexamTestpaperQuestion : mexamTestpaperQuestions) {  
    //通過考試試卷讀取題目選項對象  
    MexamQuestionOption questionOption = mexamQuestionDao.findById(mexamTestpaperQuestion.getQuestionId());  
          map1.put("questionid", mexamTestpaperQuestion.getQuestionId());  
          map1.put("answer", mexamQuestionDao.findById(mexamTestpaperQuestion.getQuestionId()).getAnswer());  
          questionAnswerList.add(map1);  
          //將每題分add到一個List  
}  
//遍歷試卷內(nèi)所有題目  
for (Map<String, Object> stringObjectMap : list) {  
    //生成每題結(jié)果對象  
    mexamAnswerInfo = new MexamAnswerInfo();  
    mexamAnswerInfo.setAnswerId(answerId);  
    mexamAnswerInfo.setId(id);  
    mexamAnswerInfo.setQuestionId(questionid);  
    mexamAnswerInfo.setResult(anwser);  
    for (Map<String, Object> objectMap : questionAnswerList) {  
        if (objectMap.get("questionid").equals(questionid)) {  
            //比較答案  
            if (anwser.equals(objectMap.get("answer"))) {  
                totalScore += questionOption.getScore();  
                mexamAnswerInfo.setIsfalse(true);  
            } else {  
                mexamAnswerInfo.setIsfalse(false);  
            } 
        }  
    }  
    mexamAnswerInfoDao.addEntity(mexamAnswerInfo);  
}

使用普通的2層for循環(huán)解決了這個問題，一層是數(shù)據(jù)庫里的題目，一層是用戶提交的題目，這時候bug就會暴露出來，假設(shè)用戶偽造了1萬道題目或更多，服務(wù)端運算量將增大很多。聊聊 HashMap 和 TreeMap 的內(nèi)部結(jié)構(gòu)

利用hashmap來解決

首先，看看它的定義

基于哈希表的 Map 接口的實現(xiàn)。此實現(xiàn)提供所有可選的映射操作，并允許使用 null 值和 null 鍵。（除了不同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恒久不變。

主要看HashMap k-v均支持空值，我們何不將用戶提交了答案add到一個HashMap里，其中題目id作為key，答案作為value，而且HashMap的key支持以字母開頭。

我們只需要for循環(huán)試卷所有題目，然后通過這個map.put("題目id")就能得到答案，然后比較答案即可，因為HashMap的key是基于hashcode的形式存儲的，所以在程序中該方案效率很高。

思路：

將提交答案以questionid為key，answer為value加入一個hashmap
for循環(huán)實體列表，直接比對答案
判分

代碼如下：

//拿到用戶提交的數(shù)據(jù)  
       Map<String, String> resultMap = new HashMap<>();  
       JSONArray questions = JSON.parseArray(params.get("questions").toString());  
       for (int size = questions.size(); size > 0; size--) {  
           JSONObject question = (JSONObject) questions.get(size - 1);  
           resultMap.put(question.getString("questionid"), question.getString("answer")); 
       }  
       //拿到試卷下的所有試題  
       List<MexamTestpaperQuestion> mexamTestpaperQuestions = mexamTestpaperQuestionDao.findBy(map);  
       int totalScore = 0;  
       for (MexamTestpaperQuestion mexamTestpaperQuestion : mexamTestpaperQuestions) {  
           MexamQuestionOption questionOption = mexamQuestionDao.findById(mexamTestpaperQuestion.getQuestionId());  
           MexamAnswerInfo mexamAnswerInfo = new MexamAnswerInfo(); 
            mexamAnswerInfo.setAnswerId(answerId);  
           mexamAnswerInfo.setId(id);  
           mexamAnswerInfo.setQuestionId(questionOption.getId());  
           mexamAnswerInfo.setResult(resultMap.get(questionOption.getId()));  
           //拿到試卷的id作為resultMap的key去查，能查到就有這個題目，然后比對answer，進(jìn)行存儲  
           if (questionOption.getAnswer().equals(resultMap.get(questionOption.getId()))) {  
               mexamAnswerInfo.setIsfalse(true);  
               totalScore += questionOption.getScore();  
           } else {  
               mexamAnswerInfo.setIsfalse(false);  
           }  
           mexamAnswerInfoDao.addEntity(mexamAnswerInfo);  
       }

分析HashMap

先看看文檔

大概翻譯為如下幾點

實現(xiàn)Map ，可克隆，可序列化
基于哈希表的Map接口實現(xiàn)。
此實現(xiàn)提供所有可選的映射操作，并允許空值和空鍵。（HashMap 類大致相當(dāng)于Hashtable，除非它是不同步的，并且允許null）。這個類不能保證Map的順序; 特別是不能保證訂單在一段時間內(nèi)保持不變。

這個實現(xiàn)為基本操作（get和put）提供了恒定時間的性能，假設(shè)散列函數(shù)在這些存儲桶之間正確分散元素。集合視圖的迭代需要與HashMap實例的“容量” （桶數(shù)）及其大小（鍵值映射數(shù)）成正比。因此，如果迭代性能很重要，不要將初始容量設(shè)置得太高（或負(fù)載因子太低）是非常重要的。

HashMap的一個實例有兩個影響其性能的參數(shù)：初始容量和負(fù)載因子。容量是在哈希表中桶的數(shù)量，和初始容量是簡單地在創(chuàng)建哈希表中的時間的能力。該負(fù)載系數(shù)是的哈希表是如何充分允許獲得之前它的容量自動增加的措施。當(dāng)在散列表中的條目的數(shù)量超過了負(fù)載因數(shù)和電流容量的乘積，哈希表被重新散列（即，內(nèi)部數(shù)據(jù)結(jié)構(gòu)被重建），使得哈希表具有桶的大約兩倍。

那么put邏輯是怎么樣的呢？

HashMap的key在put時，并不需要挨個使用equals比較，那樣時間復(fù)雜度O(n)，也就說HashMap內(nèi)有多少元素就需要循環(huán)多少次。

而HashMap是將key轉(zhuǎn)為hashcode，關(guān)于hashcode的確可能存在多個string相同的hashcode，但是最終HashMap還會比較一次bucketIndex。bucketIndex是HashMap存儲k-v的位置，時間復(fù)雜度只有O(1)。

圖解

源碼

/**  
   * Associates the specified value with the specified key in this map.  
   * If the map previously contained a mapping for the key, the old  
   * value is replaced. 
   *  
   * @param key key with which the specified value is to be associated  
   * @param value value to be associated with the specified key  
   * @return the previous value associated with <tt>key</tt>, or  
   *         <tt>null</tt> if there was no mapping for <tt>key</tt>.  
   *         (A <tt>null</tt> return can also indicate that the map  
   *         previously associated <tt>null</tt> with <tt>key</tt>.)  
   */  
  public V put(K key, V value) {  
      // 以key的哈希碼作為key    
      return putVal(hash(key), key, value, false, true);  
  }  
  /**  
   * Implements Map.put and related methods  
   *  
   * @param hash hash for key  
   * @param key the key  
   * @param value the value to put  
   * @param onlyIfAbsent if true, don't change existing value  
   * @param evict if false, the table is in creation mode.  
   * @return previous value, or null if none  
   */  
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
                 boolean evict) {  
      Node<K,V>[] tab; Node<K,V> p; int n, i;  
      // 處理key為null，HashMap允許key和value為null   
      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 || (key != null && key.equals(k))))  
              e = p;  
          else if (p instanceof TreeNode)  
              //以樹形結(jié)構(gòu)存儲 
               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) // -1 for 1st  
                          treeifyBin(tab, hash);  
                      break;  
                  }  
                  if (e.hash == hash &&  
                      ((k = e.key) == key || (key != null && key.equals(k))))  
                      break;  
                  p = e;  
              }  
          }  
          //如果是key已存在則修改舊值，并返回舊值  
          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();  
      //如果key不存在，則執(zhí)行插入操作，返回null。 
      afterNodeInsertion(evict);  
      return null;  
  }

put方法分兩種情況：bucket是以鏈表形式存儲的還是以樹形結(jié)構(gòu)存儲的。如果是key已存在則修改舊值，并返回舊值。如果key不存在，則執(zhí)行插入操作，返回null。put操作，當(dāng)發(fā)生碰撞時，如果是使用鏈表處理沖突，則執(zhí)行的尾插法。

put操作的大概流程：

通過hash值得到所在bucket的下標(biāo)，如果為null，表示沒有發(fā)生碰撞，則直接put
如果發(fā)生了碰撞，則解決發(fā)生碰撞的實現(xiàn)方式：鏈表還是樹。
如果能夠找到該key的結(jié)點，則執(zhí)行更新操作。
如果沒有找到該key的結(jié)點，則執(zhí)行插入操作，需要對modCount++。
在執(zhí)行插入操作之后，如果size超過了threshold，這要擴(kuò)容執(zhí)行resize()。

責(zé)任編輯：龐桂玉來源： Java知音