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

2021-02-13 Java知音

作者： 邵磊

juejin.im/post/59bc601ff265da0652708abd

前言

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

場景

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

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

提交地址採用restful風格

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

那麼如何比對客戶端傳過來的題目就是這張試卷裡的呢，假設用戶偽造了試卷怎麼辦？

正常解決思路

得到試卷所有題目id的list

2層for循環比對題號和答案

判定分數

大概代碼如下

//讀取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
}

//遍歷試卷內所有題目
for (Map<String, Object> stringObjectMap : list) {
    //生成每題結果對象
    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循環解決了這個問題，一層是資料庫裡的題目，一層是用戶提交的題目，這時候bug就會暴露出來，假設用戶偽造了1萬道題目或更多，服務端運算量將增大很多。聊聊 HashMap 和 TreeMap 的內部結構

利用hashmap來解決

首先，看看它的定義

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

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

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

思路：

代碼如下：

        //拿到用戶提交的數據
        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，進行存儲
            if (questionOption.getAnswer().equals(resultMap.get(questionOption.getId()))) {
                mexamAnswerInfo.setIsfalse(true);
                totalScore += questionOption.getScore();
            } else {
                mexamAnswerInfo.setIsfalse(false);
            }
            mexamAnswerInfoDao.addEntity(mexamAnswerInfo);
        }

分析HashMap

先看看文檔

大概翻譯為如下幾點

實現Map ，可克隆，可序列化

基於哈希表的Map接口實現。

此實現提供所有可選的映射操作，並允許 空值和空鍵。（HashMap 類大致相當於Hashtable，除非它是不同步的，並且允許null）。這個類不能保證Map的順序; 特別是不能保證訂單在一段時間內保持不變。

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

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

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

HashMap的key在put時，並不需要挨個使用equals比較，那樣時間複雜度O(n)，也就說HashMap內有多少元素就需要循環多少次。

而HashMap是將key轉為hashcode，關於hashcode的確可能存在多個string相同的hashcode，但是最終HashMap還會比較一次bucketIndex。bucketIndex是HashMap存儲k-v的位置，時間複雜度只有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)
                //以樹形結構存儲
                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不存在，則執行插入操作，返回null。
        afterNodeInsertion(evict);

        return null;
    }

}

put方法分兩種情況：bucket是以鍊表形式存儲的還是以樹形結構存儲的。如果是key已存在則修改舊值，並返回舊值。如果key不存在，則執行插入操作，返回null。put操作，當發生碰撞時，如果是使用鍊表處理衝突，則執行的尾插法。

put操作的大概流程：

通過hash值得到所在bucket的下標，如果為null，表示沒有發生碰撞，則直接put

如果發生了碰撞，則解決發生碰撞的實現方式：鍊表還是樹。

如果能夠找到該key的結點，則執行更新操作。

如果沒有找到該key的結點，則執行插入操作，需要對modCount++。

在執行插入操作之後，如果size超過了threshold，這要擴容執行resize()。

END

Java面試題專欄

我知道你 「在看」

相關焦點

  • 教你用 Python 實現 HashMap 數據結構
    這個就是hashmap的基本結構，如果在面試當中問到，你可以直接回答：它本質上就是一個元素是鍊表的數組。這個函數我們可以實現在LinkedList這個類當中，非常簡單，就是一個簡單的遍歷：def get_by_key(self, key):    cur = self.head.succ    while cur !
  • 帶你重新認識HashMap
    小朋友，你是否有很多問號？？？為什麼HashMap類繼承了AbstractMap的同時也實現了Map接口，AbstractMap已經實現了Map接口了呀，不是多此一舉嗎？對，你猜對了，這真的是多此一舉，據 java 集合框架的創始人Josh Bloch描述，這樣的寫法是一個失誤。
  • java中HashMap原理?面試?你是誰,你在哪?
    不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那麼就不能從HashMap中找到你想要的對象。4、HashMap中hash函數怎麼是是實現的?我們可以看到在hashmap中要找到某個元素，需要根據key的hash值來求得對應數組中的位置。如何計算這個位置就是hash算法。
  • Java面試高頻考點:HashMap的底層原理
    作為一個Java開發工程師，在面試的過程中，最高頻被問到的一個問題就是：「請簡述一下HashMap的實現原理」，在日常開發中，大多數程式設計師只會使用，對於其實現細節，卻不了解，殊不知這是較基礎卻也最重要的知識點。這篇文章將向大家詳細解釋hashmap的底層到底做了哪些事情。
  • HashMap容量為什麼必須是2的k次方
    而裡面關鍵的get、put、resize方法更是有過無數分析，今天主要分析一下哈希算法、容量為何選為2k這兩個點，雖然也有大量人分析過，但如果你看完我的分析絕對會讓你更深入理解原理，而不是面試的時候只能巴拉巴拉侃兩句，起碼讓你能侃三句。
  • HashMap是如何工作的
    最簡單形式的 hash，是一種在對任何變量/對象的屬性應用任何公式/算法後， 為其分配唯一代碼的方法。一個真正的hash方法必須遵循下面的原則哈希函數每次在相同或相等的對象上應用哈希函數時, 應每次返回相同的哈希碼。換句話說, 兩個相等的對象必須一致地生成相同的哈希碼。Java 中所有的對象都有 Hash 方法。
  • 一個簡單的例子讓你讀懂數據埋點
    現在App端的數據埋點一般採取Key-Value的形式，Key一般表示某個事件，Value代表相對應的值，一個Key可以對應一個Value或者多個Value。在埋點過程中，同種屬性的多個事件要命名成一個埋點事件ID，並以Key-Value的形式區分。
  • 一個簡單的例子學明白用Python插值
    這篇文章嘗試通過一個簡單的例子來為讀者講明白怎樣使用Python實現數據插值。總共分3部分來介紹：為什麼需要做插值這種事？通過拉格朗日插值法來看看插值這個事的理論要怎麼理解？Python實現拉格朗日插值的一個例子。為什麼需要做插值這種事？這個答案很簡單，無非兩條：首先，這個點上它沒有數據或者數據不能用：（1）沒採集到這個點上的數據；（2）採集到這個點上的數據了，但是數據明顯是錯誤的。
  • 來複習一波,HashMap底層實現原理解析
    如其中有一個equals返回了true，那麼這個節點的value將會被覆蓋。2、map.get(k)實現原理第一步：先調用k的hashCode()方法得出哈希值，並通過哈希算法轉換成數組的下標。重點理解如果這個位置上什麼都沒有，則返回null。如果這個位置上有單向鍊表，那麼它就會拿著參數K和單向鍊表上的每一個節點的K進行equals，如果所有equals方法都返回false，則get方法返回null。
  • 10個簡單步驟,帶你完全理解SQL
    SQL 語言是為計算機聲明了一個你想從原始數據中獲得什麼樣的結果的一個範例，而不是告訴計算機如何能夠得到結果。sql的執行引擎會根據你聲明的數據結果去獲取對應的數據。思考問題的時候從表的角度來思考問題提，這樣很容易理解數據如何在 SQL 語句的「流水線」上進行了什麼樣的變動。4. 靈活引用表能使 SQL 語句變得更強大靈活引用表能使 SQL 語句變得更強大。一個簡單的例子就是 JOIN 的使用。
  • 10 個簡單步驟,帶你完全理解 SQL
    SQL 語言是為計算機聲明了一個你想從原始數據中獲得什麼樣的結果的一個範例，而不是告訴計算機如何能夠得到結果。sql的執行引擎會根據你聲明的數據結果去獲取對應的數據。思考問題的時候從表的角度來思考問題提，這樣很容易理解數據如何在 SQL 語句的「流水線」上進行了什麼樣的變動。4、靈活引用表能使 SQL 語句變得更強大靈活引用表能使 SQL 語句變得更強大。一個簡單的例子就是 JOIN 的使用。
  • 面試題:來,問你幾個關於HashMap的問題?
    最簡單形式的 hash，是一種在對任何變量/對象的屬性應用任何公式/算法後， 為其分配唯一代碼的方法。一個真正的hash方法必須遵循下面的原則。哈希函數每次在相同或相等的對象上應用哈希函數時, 應每次返回相同的哈希碼。換句話說, 兩個相等的對象必須一致地生成相同的哈希碼。Java 中所有的對象都有 Hash 方法。
  • 這10 個簡單的步驟,帶你完全理解 SQL
    SQL 語言是為計算機聲明了一個你想從原始數據中獲得什麼樣的結果的一個範例，而不是告訴計算機如何能夠得到結果。sql的執行引擎會根據你聲明的數據結果去獲取對應的數據。思考問題的時候從表的角度來思考問題提，這樣很容易理解數據如何在 SQL 語句的「流水線」上進行了什麼樣的變動。4、靈活引用表能使 SQL 語句變得更強大靈活引用表能使 SQL 語句變得更強大。一個簡單的例子就是 JOIN 的使用。
  • 一個有趣的例子帶你入門canvas
    一個路徑，甚至一個子路徑，都是閉合的。使用路徑繪製圖形需要一些額外的步驟。beginPath()新建一條路徑，生成之後，圖形繪製命令被指向到路徑上生成路徑。closePath()閉合路徑之後圖形繪製命令又重新指向到上下文中。stroke()通過線條來繪製圖形輪廓。
  • 簡單例子驗證Java對象的分配過程
    當如果Eden區沒有足夠的空間時，虛擬機執行一次Minor GC，運行如下圖：上一步我們知道eden總共9M用了3243K，然後我調用看一個方法產生了4M的數組，接著又準備分配一個3M的內存，很明顯新生代內存肯定不夠了，所以觸發了GC。
  • HashMap源碼閱讀
    {        this.loadFactor = DEFAULT_LOAD_FACTOR;//0.75f        //調用了putVal方法，而putVal方法中有resize方法，有初始化        putMapEntries(m, false);    }對四個構造方法簡單總結一下
  • 多線程高頻題:讀寫鎖,Volatile,ScheduledExecutorService 和 ConcurrentHashMap
    Reading Materials:(1) https://howtodoinjava.com/core-java/multi-threading/best-practices-for-using-concurrenthashmap/(2) Java 關鍵字 volatile 的理解與正確使用下面的視頻是 xcode 的課程的試聽視頻
  • 十個例子帶你完全掌握
    字典是Python中非常重要的數據結構，這篇筆記用十個例子帶你回顧字典創建和使用的常用方法，基本能覆蓋字典的大部分使用場景。首先，回顧下字典是啥來著？字典的主要用途是存放具有映射關係的數據。比如我們我們有一份成績表數據，John:A, Emily: A+, Betty:B, Mike: C, Ashley: A。
  • 生活中悖論例子:你永遠到達不了彼岸,最後歸結為一個簡單的等式
    這裡有個生活中悖論的例子很有意思，最後會歸結為1和0.99999….哪個大的問題，我保證很多高中生都不理解，來吧，看看你的理解能力。射出的箭能否到達目標生活中悖論的例子：射箭悖論不知道誰最早提出的射箭悖論：射出的箭要從a到達b，先要經歷a和b的中點c，到c點前，要經歷a和
  • 一個簡單的例子提高你的算法能力
    你不需要成為一個數學天才才能成為一個優秀的程式設計師，但是有一些技巧你可以添加到你的問題解決包中