投稿
  1. 云图网首页
  2. 技术专区
  3. 编程笔记

LRU算法详解编程语言

• 编程笔记

LRU

目的：创建了一个哈希表作为缓存，每次查找一个用户的时候先在哈希表中查询，以此提高访问性能

LRU 全称 Least Recently Used,也就 是最近最少使用的意思，是一种内存菅理算法，最早应用于Linux操作系统

LRU算法基于一种假设：长期不被使用的数据，在未来被用到的几率也不大。

因此.当数据所占内存达到一定阈值吋, 我们要移除掉最近最少被使用的数据。

代码：

import java.io.*; 
import java.util.*; 
 
class test   
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
        LRUCache lruCache = new LRUCache(5); 
        lruCache.put("001", "用户1信息"); 
        lruCache.put("002", "用户2信息"); 
        lruCache.put("003", "用户3信息"); 
        lruCache.put("004", "用户4信息"); 
        lruCache.put("005", "用户5信息"); 
         
        System.out.println("原始序列 : "); 
        lruCache.viewAllNode();//原始序列 
         
        lruCache.get("002");//更新002之后,002位置提前了 
         
        System.out.println("更新002之后 : "); 
        lruCache.viewAllNode(); 
         
        lruCache.put("004", "用户4信息更新");//更新004之后,004位置提前了 
        System.out.println("更新004之后 : "); 
        lruCache.viewAllNode(); 
         
        System.out.println("插入006之后 : "); 
        lruCache.put("006", "用户6信息");//插入新的值,001被挤掉了 
        lruCache.viewAllNode(); 
         
    } 
} 
 
class LRUCache{ 
     
    private Node head; 
    private Node end; 
     
    //缓存存储上限 
    private int limit; 
    private HashMap<String, Node> hashMap; 
     
    public LRUCache(int limit) { 
        this.limit = limit; 
        hashMap = new HashMap<String, Node>(); 
    } 
     
    public String getFirstNode(){ 
        if(head != null){ 
            return head.value; 
        }else{ 
            return null; 
        } 
    } 
     
    public String getEndNode(){ 
        if(end != null){ 
            return end.value; 
        }else{ 
            return null; 
        } 
    } 
     
    public void viewAllNode(){ 
        if(head != null){ 
            System.out.print(head.value); 
            Node temp = head.next; 
            while(temp != null){ 
                System.out.print(" - " + temp.value); 
                temp = temp.next; 
            } 
            System.out.println(""); 
        } 
    } 
     
    public String get(String key) { 
        Node node = hashMap.get(key); 
        if (node == null){ 
            return null; 
        } 
        refreshNode(node); 
        return node.value; 
    } 
     
    public void put(String key, String value) { 
        Node node = hashMap.get(key); 
        if (node == null) { 
            //如果key不存在，插入key-value 
            if (hashMap.size() >= limit) { 
                String oldKey = removeNode(head); 
                hashMap.remove(oldKey); 
            } 
            node = new Node(key, value); 
            addNode(node); 
            hashMap.put(key, node); 
        }else { 
            //如果key存在，刷新key-value 
            node.value = value; 
            refreshNode(node); 
        } 
    } 
     
    public void remove(String key) { 
        Node node = hashMap.get(key); 
        removeNode(node); 
        hashMap.remove(key); 
    } 
     
    /**  
     * 刷新被访问的节点位置  
     * @param  node 被访问的节点  
     */ 
    private void refreshNode(Node node) { 
        //如果访问的是尾节点，无需移动节点 
        if (node == end) { 
            return; 
        } 
        //移除节点 
        removeNode(node); 
        //重新插入节点 
        addNode(node); 
    } 
     
    /** 
     * 删除节点  
     * @param  node 要删除的节点  
     */ 
    private String removeNode(Node node) { 
        if (node == end) { 
            //移除尾节点 
            end = end.pre; 
        }else if(node == head){ 
            //移除头节点 
            head = head.next; 
        } else { 
            //移除中间节点 
            node.pre.next = node.next; 
            node.next.pre = node.pre; 
        } 
        return node.key; 
    } 
     
    /** 
     * 尾部插入节点 
     * @param  node 要插入的节点  
     */ 
    private void addNode(Node node) { 
        if(end != null) { 
            end.next = node; 
            node.pre = end; 
            node.next = null; 
        } 
        end = node; 
        if(head == null){ 
            head = node; 
        } 
    } 
     
} 
 
 
class Node { 
    Node(String key, String value){ 
        this.key = key; 
        this.value = value; 
    } 
    public Node pre; 
    public Node next; 
    public String key; 
    public String value; 
}

下面加上 synchronized 解决进程安全问题

import java.io.*; 
import java.util.*; 
 
class test   
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
        LRUCache lruCache = new LRUCache(5); 
        lruCache.put("001", "用户1信息"); 
        lruCache.put("002", "用户2信息"); 
        lruCache.put("003", "用户3信息"); 
        lruCache.put("004", "用户4信息"); 
        lruCache.put("005", "用户5信息"); 
         
        System.out.println("原始序列 : "); 
        lruCache.viewAllNode();//原始序列 
         
        lruCache.get("002");//更新002之后,002位置提前了 
         
        System.out.println("更新002之后 : "); 
        lruCache.viewAllNode(); 
         
        lruCache.put("004", "用户4信息更新");//更新004之后,004位置提前了 
        System.out.println("更新004之后 : "); 
        lruCache.viewAllNode(); 
         
        System.out.println("插入006之后 : "); 
        lruCache.put("006", "用户6信息");//插入新的值,001被挤掉了 
        lruCache.viewAllNode(); 
         
    } 
} 
 
class LRUCache{ 
     
    private Node head; 
    private Node end; 
     
    //缓存存储上限 
    private int limit; 
    private HashMap<String, Node> hashMap; 
     
    public LRUCache(int limit) { 
        this.limit = limit; 
        hashMap = new HashMap<String, Node>(); 
    } 
     
    public String getFirstNode(){ 
        if(head != null){ 
            return head.value; 
        }else{ 
            return null; 
        } 
    } 
     
    public String getEndNode(){ 
        if(end != null){ 
            return end.value; 
        }else{ 
            return null; 
        } 
    } 
     
    public void viewAllNode(){ 
        if(head != null){ 
            System.out.print(head.value); 
            Node temp = head.next; 
            while(temp != null){ 
                System.out.print(" - " + temp.value); 
                temp = temp.next; 
            } 
            System.out.println(""); 
        } 
    } 
     
    public synchronized String get(String key) { 
         
        try { 
             
            Node node = hashMap.get(key); 
            if (node == null){ 
                return null; 
            } 
             
            refreshNode(node); 
            return node.value; 
             
        } catch (Exception e) { 
            e.printStackTrace(); 
        } 
        return ""; 
    } 
     
    public synchronized void put(String key, String value) { 
         
        try { 
             
            Node node = hashMap.get(key); 
            if (node == null) { 
                //如果key不存在，插入key-value 
                if (hashMap.size() >= limit) { 
                    String oldKey = removeNode(head); 
                    hashMap.remove(oldKey); 
                } 
                node = new Node(key, value); 
                addNode(node); 
                hashMap.put(key, node); 
            }else { 
                //如果key存在，刷新key-value 
                node.value = value; 
                refreshNode(node); 
            } 
             
        } catch (Exception e) { 
            e.printStackTrace(); 
        } 
         
    } 
     
    public void remove(String key) { 
        Node node = hashMap.get(key); 
        removeNode(node); 
        hashMap.remove(key); 
    } 
     
    /**  
     * 刷新被访问的节点位置  
     * @param  node 被访问的节点  
     */ 
    private void refreshNode(Node node) { 
        //如果访问的是尾节点，无需移动节点 
        if (node == end) { 
            return; 
        } 
        //移除节点 
        removeNode(node); 
        //重新插入节点 
        addNode(node); 
    } 
     
    /** 
     * 删除节点  
     * @param  node 要删除的节点  
     */ 
    private String removeNode(Node node) { 
        if (node == end) { 
            //移除尾节点 
            end = end.pre; 
        }else if(node == head){ 
            //移除头节点 
            head = head.next; 
        } else { 
            //移除中间节点 
            node.pre.next = node.next; 
            node.next.pre = node.pre; 
        } 
        return node.key; 
    } 
     
    /** 
     * 尾部插入节点 
     * @param  node 要插入的节点  
     */ 
    private void addNode(Node node) { 
        if(end != null) { 
            end.next = node; 
            node.pre = end; 
            node.next = null; 
        } 
        end = node; 
        if(head == null){ 
            head = node; 
        } 
    } 
     
} 
 
 
class Node { 
    Node(String key, String value){ 
        this.key = key; 
        this.value = value; 
    } 
    public Node pre; 
    public Node next; 
    public String key; 
    public String value; 
}

输出：

原始序列 :  
用户1信息 - 用户2信息 - 用户3信息 - 用户4信息 - 用户5信息 
更新002之后 :  
用户1信息 - 用户3信息 - 用户4信息 - 用户5信息 - 用户2信息 
更新004之后 :  
用户1信息 - 用户3信息 - 用户5信息 - 用户2信息 - 用户4信息更新 
插入006之后 :  
用户3信息 - 用户5信息 - 用户2信息 - 用户4信息更新 - 用户6信息

原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/20729.html

赞 (0)
0 0
上一篇 2021年7月19日
下一篇 2021年7月19日

相关推荐

发表回复

登录后才能评论