面接官:集合フレームワークを使わずにLRUを書いてください.

ツールバーの

前言

ソースコード

一、どのように設計しますか?

二、コア定義

1. クラス設計

2. 内部クラス

三、方法実現

1. ヘッド挿入方法addToHead

2. 末尾削除方法removeLast

3. keyによるノード

の検索

4. ノードをチェーンヘッド

に移動する

5. キー値ペアを追加するputメソッド

6. クエリーデータメソッドget

7. その他

contains

isEmpty

toString

四、総括

前言
前回はLRUのアイデアを紹介し、Java集合フレームワークのLinkedListとHashMapを借りて非常に簡単にLRUを実現しました.面接問題アルゴリズム(1)--LRUアルゴリズムですが、面接で集合フレームワークを借りてLRUを書くと、面接官は満足していないでしょう.ここまで考えて、昼休みをあきらめてJava集合フレームワークを使わないLRUをやめました
ソースコード
ここをクリックしてソースを取得して、スターを注文するのを忘れないでくださいね~
一、どのように設計しますか.
集合フレームがありませんが、どうすればいいですか?集合フレームワークのapiだけを普段から用いてその原理を研究しないと,このような問題は考えにくい.LinkedListの最下層は双方向チェーンテーブルで、私も前に双方向チェーンテーブルでLinkedListを実現する文章を書いたことがあります:ゼロから1つのデータ構造(1)——双方向チェーンテーブルを引き裂いて、中もLRUに対して口を出しました
LRUはキー値ペアを格納しています.集合フレームワークを使用する実装ではHashMapを使用しています.手書きHashMapは現実的ではないようです.hash関数や拡張などの操作も複雑です.ここでは、双方向チェーンテーブルにキー値ペアを格納する形でLRUを設計します.
二、核心定義
1.クラス設計

/**
 *          LRU
 * @param 
 * @param 
 */
public class PureLRU<K,V> {
     

    /**
     *     
     */
    private int capacity;

    /**
     *       
     */
    private int size;

    /**
     *     、   
     */
    private Entry head, tail;

    public PureLRU(int capacity){
     
        this.capacity=capacity;
        this.size=0;
    }
}

集合フレームワークを使用しないため、PureLRUと名付けられました^-^ヘッドテールポインタは双方向チェーンテーブルに必須ですが、キャッシュの容量とキャッシュ要素の数はコンテナが満載かどうかを判断する根拠です
2.内部クラス

    /**
     *      
     * @param 
     * @param 
     */
    private class Entry<K,V>{
     
        
        /**
         *       
         */
        public K key;
        
        /**
         *       
         */
        public V val;

        /**
         *        
         */
        public Entry next,pre;

        public Entry(K key,V val){
     
            this.key = key;
            this.val = val;
        }
    }

双方向チェーンテーブルよりも1つのフィールドを追加しました:keyこれでチェーンテーブルにキー値のペアを格納することができます~
三、方法実現
Leetcode 146ではputメソッドとgetメソッドのみを実装する必要があるが、この2つのメソッドをサポートするためには、以下の方法を実装する必要がある.

ヘッドソケット

尾削除

keyによってノード

を探す

ノードをチェーンヘッド

に移動する.
まず一つずつ叶えましょう
1.頭挿し方法addToHead

    /**
     *     
     * @param entry
     */
    private void addToHead(Entry entry){
     
        //                     
        entry.next = head;
        //                     
        head.pre = entry;
        //                
        
        //           ，    
        head = entry;
        //        ，size  
        ++size;
    }

2.末尾削除方法removeLast

    /**
     *     
     */
    private void removeLast(){
     
        //                   
        tail = tail.pre;
        //           （       ）   null
        tail.next = null;
        //                ，size  
        --size;
    }

3.keyでノードを探す
チェーンテーブルにノードを探すには、チェーンテーブル全体を巡るしかないので、java.util.LinkedListのindexOfも同様であり,時間的複雑度はO(n)である.

    /**
     *   key    ，O(n)
     * @param key
     * @return
     */
    private Entry findEntryByKey(K key){
     
        /**
         *       ，     
         * 1.           null key   
         * 2.   key.equals         
         */
        //  key   ，     key     
        if (key == null){
     
            for(Entry cur = head; cur != null; cur = cur.next) {
     
                if(cur.key==null){
     
                    return cur;
                }
            }
        }else {
     
            // key    ，  key         
            for(Entry cur = head; cur != null; cur = cur.next){
     
                if(key.equals(cur.key)){
     
                    return cur;
                }
            }
        }
        return null;
    }

4.ノードをチェーンヘッダに移動

    /**
     *         
     * @param entry
     */
    private void moveToHead(Entry entry){
     
        //          ，    
        if(entry == head){
     
            return;
        }
        //          ，      
        if(entry == tail){
     
            removeLast();
            addToHead(entry);
            return;
        }
        //           
        Entry pre = entry.pre;
        Entry next = entry.next;
        pre.next = next;
        next.pre = pre;
        //                 ，   size  
        --size;
        //           ，      
        addToHead(entry);
    }

実は簡単です.

既存の

を削除する.

は、削除するヘッドプラグ

を挿入する.
5.キー値ペアを追加するputメソッド

    /**
     *      
     * @param key
     * @param val
     */
    public void put(K key,V val){
     
        //                  
        Entry entry = findEntryByKey(key);
        if(entry != null){
     
            moveToHead(entry);
            //     
            head.val=val;
            return;
        }

        //             
        //  Entry      
        Entry<K,V> newEntry = new Entry<>(key,val);
        //       ，   =   ，
        if (this.isEmpty()){
     
            head = newEntry;
            tail = head;
            //    size   
            ++size;
        }else {
     
            //        
            //         
            if (size == capacity){
     
                removeLast();
            }
            //      
            addToHead(newEntry);
        }
    }

状況別討論:

チェーンテーブルに入力キーと等しいキーが存在する場合、そのノードをチェーンヘッダ

に移動する.

チェーンテーブルには、入力キーに等しいキーは存在しません.

チェーンテーブルの長さを確認します.

は0(isEmpty)?——処理ヘッダ/エンドノード

0より大きいのはcapacityより小さいですか?——ヘッドソケット

を行う

キャッシュフル(size==capacity)?——末尾削除+頭挿し

を行う


6.クエリーデータメソッドget

    /**
     *     
     * @param key
     * @return
     */
    public V get(K key){
     
        Entry target = findEntryByKey(key);
        //       ，     
        if(target == null){
     
            return null;
        }
        //               
        moveToHead(target);
        return (V)target.val;
    }

アクセスされたデータをチェーンヘッダーに移動すればよい
7.その他
データの表示/読み取りを容易にするために、contains、isEmptyなどのコンテナの一般的な方法を別途書き、toStringも書き直しました.
contains

    /**
     *            key
     * @param key
     * @return
     */
    public boolean contains(K key){
     
        return findEntryByKey(key) != null;
    }

isEmpty

    public boolean isEmpty(){
     
        return size==0;
    }

toString

    @Override
    public String toString(){
     
        StringBuilder sb = new StringBuilder();
        for(Entry cur = head; cur != null; cur = cur.next) {
     
            sb.append(cur.key).append(",");
        }
        return sb.deleteCharAt(sb.length()-1).toString();
    }

四、まとめ
これにより、集合フレームワークを使用しないLRUが完了し、双方向チェーンテーブルとほぼ同じテストが実行されます.

public class Test  {
     
    public static void main(String[] args) {
     
        PureLRU<Integer,String> pureLRU = new PureLRU<>(3);
        System.out.println(pureLRU.isEmpty()); // true
        pureLRU.put(1,"A");
        pureLRU.put(2,"B");
        pureLRU.put(3,"C");
        System.out.println(pureLRU.toString()); // 3,2,1
        System.out.println(pureLRU.get(1)); // A
        System.out.println(pureLRU.toString()); // 1,3,2
        pureLRU.get(2);
        System.out.println(pureLRU.toString()); // 2,1,3

        pureLRU.put(4,"D");
        System.out.println(pureLRU.toString()); // 4,2,1

        pureLRU.put(1,"Z");
        System.out.println(pureLRU.toString()); // 1,4,2
        System.out.println(pureLRU.get(1)); // Z

        System.out.println(pureLRU.contains(4)); // true
        System.out.println(pureLRU.isEmpty()); // false

        pureLRU.put(null,"nullVal");
        System.out.println(pureLRU.toString()); // null,1,4
        System.out.println(pureLRU.get(null)); // nullVal
    }
}

テストエラーなし