怎么把新信息加入到HashMap和LinkedList里

本篇內(nèi)容主要講解“怎么把新信息加入到HashMap和LinkedList里”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“怎么把新信息加入到HashMap和LinkedList里”吧!

LRU Cache

LRU 是什么

LRU = Least Recently Used 最近最少使用
它是一種緩存逐出策略 cache eviction policies

LRU 算法是假設(shè)最近最少使用的那些信息，將來(lái)被使用的概率也不大，所以在容量有限的情況下，就可以把這些不常用的信息踢出去，騰地方。

比如有熱點(diǎn)新聞時(shí)，所有人都在搜索這個(gè)信息，那剛被一個(gè)人搜過(guò)的信息接下來(lái)被其他人搜索的概率也大，就比前兩天的一個(gè)過(guò)時(shí)的新聞被搜索的概率大，所以我們把很久沒(méi)有用過(guò)的信息踢出去，也就是 Least Recently Used 的信息被踢出去。

舉個(gè)例子：我們的內(nèi)存容量為 5，現(xiàn)在有 1-5 五個(gè)數(shù)。

我們現(xiàn)在想加入一個(gè)新的數(shù)：6
可是容量已經(jīng)滿了，所以需要踢出去一個(gè)。

那按照什么規(guī)則踢出去，就有了這個(gè)緩存逐出策略。比如：

• FIFO (First In First Out) 這個(gè)就是普通的先進(jìn)先出。

• LFU (Least Frequently Used) 這個(gè)是計(jì)算每個(gè)信息的訪問(wèn)次數(shù)，踢走訪問(wèn)次數(shù)最少的那個(gè)；如果訪問(wèn)次數(shù)一樣，就踢走好久沒(méi)用過(guò)的那個(gè)。這個(gè)算法其實(shí)很高效，但是耗資源，所以一般不用。

• LRU (Least Recently Used) 這是目前最常用了。

LRU 的規(guī)則是把很長(zhǎng)時(shí)間沒(méi)有用過(guò)的踢出去，那它的隱含假設(shè)就是，認(rèn)為最近用到的信息以后用到的概率會(huì)更大。

那我們這個(gè)例子中就是把最老的 1 踢出去，變成：

不斷迭代...

Cache 是什么？

簡(jiǎn)單理解就是：把一些可以重復(fù)使用的信息存起來(lái)，以便之后需要時(shí)可以快速拿到。

那至于它存在哪里就不一定了，最常見(jiàn)的是存在內(nèi)存里，也就是 memory cache，但也可以不存在內(nèi)存里。

使用場(chǎng)景就更多了，比如 Spring 中有 @Cacheable 等支持 Cache 的一系列注解。上個(gè)月我在工作中就用到了這個(gè) annotation，當(dāng)然是我司包裝過(guò)的，大大減少了 call 某服務(wù)器的次數(shù)，解決了一個(gè)性能上的問(wèn)題。

再比如，在進(jìn)行數(shù)據(jù)庫(kù)查詢的時(shí)候，不想每次請(qǐng)求都去 call 數(shù)據(jù)庫(kù)，那我們就在內(nèi)存里存一些常用的數(shù)據(jù)，來(lái)提高訪問(wèn)性能。

這種設(shè)計(jì)思想其實(shí)是遵循了著名的“二八定律”。在讀寫數(shù)據(jù)庫(kù)時(shí)，每次的 I/O 過(guò)程消耗很大，但其實(shí) 80% 的 request 都是在用那 20% 的數(shù)據(jù)，所以把這 20% 的數(shù)據(jù)放在內(nèi)存里，就能夠極大的提高整體的效率。

總之，Cache 的目的是存一些可以復(fù)用的信息，方便將來(lái)的請(qǐng)求快速獲得。

LRU Cache

那我們知道了 LRU，了解了 Cache，合起來(lái)就是 LRU Cache 了：

當(dāng) Cache 儲(chǔ)存滿了的時(shí)候，使用 LRU 算法把老家伙清理出去。

思路詳解

說(shuō)了這么多，Let's get to the meat of the problem!

這道經(jīng)典題大家都知道是要用 HashMap + Doubly Linked List，或者說(shuō)用 Java 中現(xiàn)成的 LinkedHashMap，但是，為什么？你是怎么想到用這兩個(gè)數(shù)據(jù)結(jié)構(gòu)的？面試的時(shí)候不講清楚這個(gè)，不說(shuō)清楚思考過(guò)程，代碼寫對(duì)了也沒(méi)用。

和在工作中的設(shè)計(jì)思路類似，沒(méi)有人會(huì)告訴我們要用什么數(shù)據(jù)結(jié)構(gòu)，一般的思路是先想有哪些 operations，然后根據(jù)這些操作，再去看哪些數(shù)據(jù)結(jié)構(gòu)合適。

分析 Operations

那我們來(lái)分析一下對(duì)于這個(gè) LRU Cache 需要有哪些操作：

1. 首先最基本的操作就是能夠從里面讀信息，不然之后快速獲取是咋來(lái)的；

2. 那還得能加入新的信息，新的信息進(jìn)來(lái)就是 most recently used 了；

3. 在加新信息之前，還得看看有沒(méi)有空位，如果沒(méi)有空間了，得先把老的踢出去，那就需要能夠找到那個(gè)老家伙并且刪除它；

4. 那如果加入的新信息是緩存里已經(jīng)有的，那意思就是 key 已經(jīng)有了，要更新 value，那就只需要調(diào)整一下這條信息的 priority，它已經(jīng)從那次被寵幸晉升為貴妃了～

找尋數(shù)據(jù)結(jié)構(gòu)

那第一個(gè)操作很明顯，我們需要一個(gè)能夠快速查找的數(shù)據(jù)結(jié)構(gòu)，非 HashMap 莫屬，還不了解 HashMap 原理和設(shè)計(jì)規(guī)則的在公眾號(hào)內(nèi)發(fā)消息「HashMap」，送你一篇爆款文章；

可是后面的操作 HashMap 就不頂用了呀。。。

來(lái)來(lái)來(lái)，我們來(lái)數(shù)一遍基本的數(shù)據(jù)結(jié)構(gòu)：
Array, LinkedList, Stack, Queue, Tree, BST, Heap, HashMap

在做這種數(shù)據(jù)結(jié)構(gòu)的題目時(shí)，就這樣把所有的數(shù)據(jù)結(jié)構(gòu)列出來(lái)，一個(gè)個(gè)來(lái)分析，有時(shí)候不是因?yàn)檫@個(gè)數(shù)據(jù)結(jié)構(gòu)不行，而是因?yàn)槠渌臄?shù)據(jù)結(jié)構(gòu)更好。

怎么叫更好？忘了我們的衡量標(biāo)準(zhǔn)嘛！時(shí)空復(fù)雜度，趕緊復(fù)習(xí)遞歸那篇文章，公眾號(hào)內(nèi)回復(fù)「遞歸」即可獲得。

那我們的分析如下：

Array, Stack, Queue 這三種本質(zhì)上都是 Array 實(shí)現(xiàn)的（當(dāng)然 Stack, Queue 也可以用 LinkedList 來(lái)實(shí)現(xiàn)。。），一會(huì)插入新的，一會(huì)刪除老的，一會(huì)調(diào)整下順序，array 不是不能做，就是得 O(n) 啊，用不起。

BST 同理，時(shí)間復(fù)雜度是 O(logn).

Heap 即便可以，也是 O(logn).

LinkedList，有點(diǎn)可以哦，按照從老到新的順序，排排站，刪除、插入、移動(dòng)，都可以是 O(1) 的誒！但是刪除時(shí)我還需要一個(gè) previous pointer 才能刪掉，所以我需要一個(gè) Doubly LinkedList.

那么我們的數(shù)據(jù)結(jié)構(gòu)敲定為：
HashMap + Doubly LinkedList

定義清楚數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

選好了數(shù)據(jù)結(jié)構(gòu)之后，還需要定義清楚每個(gè)數(shù)據(jù)結(jié)構(gòu)具體存儲(chǔ)的是是什么，這兩個(gè)數(shù)據(jù)結(jié)構(gòu)是如何聯(lián)系的，這才是核心問(wèn)題。

我們先想個(gè)場(chǎng)景，在搜索引擎里，你輸入問(wèn)題 Questions，谷歌給你返回答案 Answer。

那我們就先假設(shè)這兩個(gè)數(shù)據(jù)結(jié)構(gòu)存的都是 <Q, A>，然后來(lái)看這些操作，如果都很順利，那沒(méi)問(wèn)題，如果有問(wèn)題，我們?cè)僬{(diào)整。

那現(xiàn)在我們的 HashMap 和 LinkedList 長(zhǎng)這樣：

然后我們回頭來(lái)看這四種操作：

操作 1，沒(méi)問(wèn)題，直接從 HashMap 里讀取 Answer 即可，O(1)；

操作 2，新加入一組 Q&A，兩個(gè)數(shù)據(jù)結(jié)構(gòu)都得加，那先要判斷一下當(dāng)前的緩存里有沒(méi)有這個(gè) Q，那我們用 HashMap 判斷，

• 如果沒(méi)有這個(gè) Q，加進(jìn)來(lái)，都沒(méi)問(wèn)題；

• 如果已經(jīng)有這個(gè) Q，HashMap 這里要更新一下 Answer，然后我們還要把 LinkedList 的那個(gè) node 移動(dòng)到最后或者最前，因?yàn)樗兂闪俗钚卤皇褂玫牧寺铩?/p>

可是，怎么找 LinkedList 的這個(gè) node 呢？一個(gè)個(gè) traverse 去找并不是我們想要的，因?yàn)橐?O(n) 的時(shí)間嘛，我們想用 O(1) 的時(shí)間操作。

那也就是說(shuō)這樣記錄是不行的，還需要記錄 LinkedList 中每個(gè) ListNode 的位置，這就是本題關(guān)鍵所在。

那自然是在 HashMap 里記錄 ListNode 的位置這個(gè)信息了，也就是存一下每個(gè) ListNode 的 reference。

想想其實(shí)也是，HashMap 里沒(méi)有必要記錄 Answer，Answer 只需要在 LinkedList 里記錄就可以了。

之后我們更新、移動(dòng)每個(gè) node 時(shí)，它的 reference 也不需要變，所以 HashMap 也不用改動(dòng)，動(dòng)的只是 previous, next pointer.

那再一想，其實(shí) LinkedList 里也沒(méi)必要記錄 Question，反正 HashMap 里有。

這兩個(gè)數(shù)據(jù)結(jié)構(gòu)是相互配合來(lái)用的，不需要記錄一樣的信息。

更新后的數(shù)據(jù)結(jié)構(gòu)如下：

這樣，我們才分析出來(lái)用什么數(shù)據(jù)結(jié)構(gòu)，每個(gè)數(shù)據(jù)結(jié)構(gòu)里存的是什么，物理意義是什么。

那其實(shí)，Java 中的 LinkedHashMap 已經(jīng)做了很好的實(shí)現(xiàn)。但是，即便面試時(shí)可以使用它，也是這么一步步推導(dǎo)出來(lái)的，而不是一看到題目就知道用它，那一看就是背答案啊。

有同學(xué)問(wèn)我，如果面試官問(wèn)我這題做沒(méi)做過(guò)，該怎么回答？

答：實(shí)話實(shí)說(shuō)。

真誠(chéng)在面試、工作中都是很重要的，所以實(shí)話實(shí)說(shuō)就好了。但如果面試官?zèng)]問(wèn)，就不必說(shuō)。。。

其實(shí)面試官是不 care 你做沒(méi)做過(guò)這道題的，因?yàn)榇蠹叶妓㈩}，基本都做過(guò)，問(wèn)這個(gè)問(wèn)題沒(méi)有意義。只要你能把問(wèn)題分析清楚，講清楚邏輯，做過(guò)了又怎樣？很多做過(guò)了題的人是講不清楚的。。。

總結(jié)

那我們?cè)倏偨Y(jié)一下那四點(diǎn)操作：

第一個(gè)操作，也就是 get() API，沒(méi)啥好說(shuō)的；

二三四，是 put() API，有點(diǎn)小麻煩：

畫(huà)圖的時(shí)候邊講邊寫，每一步都從 high level 到 detail 再到代碼，把代碼模塊化。

• 比如“Welcome”是要把這個(gè)新的信息加入到 HashMap 和 LinkedList 里，那我會(huì)用一個(gè)單獨(dú)的 add() method 來(lái)寫這塊內(nèi)容，那在下面的代碼里我取名為 appendHead()，更精準(zhǔn)；

• “踢走老的”這里我也是用一個(gè)單獨(dú)的 remove() method 來(lái)寫的。

當(dāng)年我把這圖畫(huà)出來(lái)，面試官就沒(méi)讓我寫代碼了，直接下一題了...

那如果面試官還讓你寫，就寫唄。。。

class LRUCache {
  // HashMap: <key = Question, value = ListNode>
  // LinkedList: <Answer>

  public static class Node {
      int key;
      int val;
      Node next;
      Node prev;
      public Node(int key, int val) {
          this.key = key;
          this.val = val;
      }
  }

  Map<Integer, Node> map = new HashMap<>();
  private Node head;
  private Node tail;
  private int cap;

  public LRUCache(int capacity) {
      cap = capacity;
  }

  public int get(int key) {
      Node node = map.get(key);
      if(node == null) {
          return -1;
      } else {
          int res = node.val;
          remove(node);
          appendHead(node);
          return res;
      }
  }

  public void put(int key, int value) {
      // 先 check 有沒(méi)有這個(gè) key
      Node node = map.get(key);
      if(node != null) {
          node.val = value;
          // 把這個(gè)node放在最前面去
          remove(node);
          appendHead(node);
      } else {
          node = new Node(key, value);
          if(map.size() < cap) {
              appendHead(node);
              map.put(key, node);
          } else {
              // 踢走老的
              map.remove(tail.key);
              remove(tail);
              appendHead(node);
              map.put(key, node);
          }
      }
  }

  private void appendHead(Node node) {
      if(head == null) {
          head = tail = node;
      } else {
          node.next = head;
          head.prev = node;
          head = node;
      }
  }

  private void remove(Node node) {
      // 這里我寫的可能不是最 elegant 的，但是是很 readable 的
      if(head == tail) {
          head = tail = null;
      } else {
          if(head == node) {
              head = head.next;
              node.next = null;
          } else if (tail == node) {
              tail = tail.prev;
              tail.next = null;
              node.prev = null;
          } else {
              node.prev.next = node.next;
              node.next.prev = node.prev;
              node.prev = null;
              node.next = null;
          }
      }
  }


}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

到此，相信大家對(duì)“怎么把新信息加入到HashMap和LinkedList里”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！