当前位置:网站首页>Hash table: least recently used cache
Hash table: least recently used cache
2022-06-13 02:45:00 【Zeng Qiang】
List of articles
background
The basis of hash table
Hash table is a more complex and efficient data structure , Include HashSet and HashMap, The time complexity of their query to delete an element is O(1). Often used to optimize time efficiency . Hash tables are efficient , But not everything , If you need to sort elements , Then use TreeMap.
Design of hash table
- Array : Design hash table based on array , The remainder of the hash value of the element to the length of the array is used as the array subscript , The time efficiency of finding elements is O(1).
- Linked list : When the hash values are equal , Array subscripts will cause conflicts , You need to store multiple elements in the same location of the array in a linked list .
- Capacity expansion : To ensure efficiency , When the ratio of the number of elements to the length of the array exceeds the threshold , We need to expand the length of the array .
subject
Please design and implement a least recently used cache , The time complexity of the following two operations is required to be O(1).
- get(key)
- put(key, value)
Their thinking
This problem requires us to design a cached data structure ,
- We have to record the order in which the nodes are accessed . If we use HashMap, Use get,put when , Time complexity can be achieved O(1), Visit one node at a time , Let's take the node's key Store as key hashMap in , Node most HashMap Value storage for , At the same time, the node is added to the end of the linked list , In this way, the head node of the linked list is the least used node , The tail node is the newly used node .
- Two way linked list replaces one-way linked list . Enables you to quickly delete and query nodes .
Something to watch out for :
- When the number of nodes exceeds the threshold , The least recently used nodes need to be eliminated .
- With the help of sentry node , Easy to update cache .
The specific logic code is as follows :
Code
class LRUCache {
private int capacity = 0;
private ListNode head;
private ListNode tail;
private Map<Integer, ListNode> cache;
public LRUCache(int capacity) {
this.capacity = capacity;// threshold
// Initialize cache hash table
cache = new HashMap<Integer, ListNode>();
// Initializing a double linked list , Here the sentry node is used to quickly add the tail node .
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head.next = tail;
tail.pre = head;
}
public int get(int key) {
ListNode node = cache.get(key);
if(node == null) {
return -1;
}
moveToTail(node, node.value);
return node.value;
}
public void put(int key, int value) {
if(cache.containsKey(key)) {
moveToTail(cache.get(key), value);
} else {
if(cache.size() == capacity) {
ListNode tobeDeleteNode = head.next;
deleteNode(tobeDeleteNode);
cache.remove(tobeDeleteNode.key);
}
ListNode node = new ListNode(key, value);
insertToTail(node);
cache.put(key, node);
}
}
private void deleteNode(ListNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void moveToTail(ListNode node, int value) {
//detete
deleteNode(node);
//insertToTail
node.value = value;
insertToTail(node);
}
private void insertToTail(ListNode node) {
node.pre = tail.pre;
tail.pre.next = node;
node.next = tail;
tail.pre = node;
}
class ListNode {
ListNode pre;
ListNode next;
int key;
int value;
public ListNode(int key, int value){
this.key = key;
this.value = value;
}
}
}
/** * 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); */
summary
This topic examines the knowledge points of hash table , It should be noted that the least recently used cache needs to record the order of element access , So the data structure of the final cache is designed as hash table and bidirectional linked list .
边栏推荐
- Laravel 权限导出
- 在IDEA使用C3P0連接池連接SQL數據庫後卻不能顯示數據庫內容
- Resource arrangement
- too old resource version,Code:410
- Introduction to facial expression recognition system -- offline environment configuration
- Leetcode 473. Match to square [violence + pruning]
- 02 优化微信开发者工具默认的结构
- Sans certificate generation
- [reading paper] generate confrontation network Gan
- A real-time target detection model Yolo
猜你喜欢
Detailed explanation of handwritten numeral recognition based on support vector machine (Matlab GUI code, providing handwriting pad)
[reading some papers] introducing deep learning into the public horizon alexnet
03 recognize the first view component
[reading point paper] deeplobv3 rethinking atlas revolution for semantic image segmentation ASPP
Huffman tree and its application
[thoughts in the essay] mourn for development technology expert Mao Xingyun
[reading papers] transformer miscellaneous notes, especially miscellaneous
智能安全配电装置如何减少电气火灾事故的发生?
[data analysis and visualization] key points of data drawing 9- color selection
05 tabBar导航栏功能
随机推荐
[thoughts in the essay] mourn for development technology expert Mao Xingyun
[reading papers] visual convolution zfnet
Professional database management software: Valentina Studio Pro for Mac
Implementing fillet in custom dialog
How did you spend your winter vacation perfectly?
專業的數據庫管理軟件:Valentina Studio Pro for Mac
js多种判断写法
01 initial knowledge of wechat applet
Using binary heap to implement priority queue
02 optimize the default structure of wechat developer tools
04 route jump and carry parameters
redis
[data analysis and visualization] key points of data drawing 9- color selection
冲刺强基计划数学物理专题一
Ijkplayer source code - setting option 2
Leetcode 450. Delete node in binary search tree [binary search tree]
AAR packaging and confusion
[life science] DNA extraction of basic biological experiments
Pycharm installation pyqt5 and its tools (QT designer, pyuic, pyrcc) detailed tutorial
The weight of the input and textarea components of the applet is higher than that of the fixed Z-index