LRU算法實現

LRU是Last Recent Used 縮寫，做為一種緩存算法，將最近較少使用的緩存失效。memcache采用了該算法。如下采用了一種PHP的實現方式。該算法將每次新增的內容，放到緩存頂部，達到緩存極限時，將緩存底部的內容清除。可以通過如下PHP代碼來模擬。

<?php
class LRUCache {private $head;private $tail;private $capacity;private $hashmap;public function __construct($capacity) {$this->capacity = $capacity;$this->hashmap = array();$this->head = new Node(null, null);$this->tail = new Node(null, null);$this->head->setNext($this->tail);$this->tail->setPrevious($this->head);}public function get($key) {if (!isset($this->hashmap[$key])) { return null; }$node = $this->hashmap[$key];if (count($this->hashmap) == 1) { return $node->getData(); }// refresh the access$this->detach($node);$this->attach($this->head, $node);return $node->getData();}public function put($key, $data) {if ($this->capacity <= 0) { return false; }if (isset($this->hashmap[$key]) && !empty($this->hashmap[$key])) {$node = $this->hashmap[$key];// update data$this->detach($node);$this->attach($this->head, $node);$node->setData($data);}else {$node = new Node($key, $data);$this->hashmap[$key] = $node;$this->attach($this->head, $node);// check if cache is fullif (count($this->hashmap) > $this->capacity) {// we're full, remove the tail$nodeToRemove = $this->tail->getPrevious();$this->detach($nodeToRemove);unset($this->hashmap[$nodeToRemove->getKey()]);}}return true;}private function attach($head, $node) {$node->setPrevious($head);$node->setNext($head->getNext());$node->getNext()->setPrevious($node);$node->getPrevious()->setNext($node);}private function detach($node) {$node->getPrevious()->setNext($node->getNext());$node->getNext()->setPrevious($node->getPrevious());}}/*** Class that represents a node in a doubly linked list*/
class Node {private $key;// the content of the nodeprivate $data;// the next nodeprivate $next;// the previous nodeprivate $previous;public function __construct($key, $data) {$this->key = $key;$this->data = $data;}public function setData($data) {$this->data = $data;}public function setNext($next) {$this->next = $next;}public function setPrevious($previous) {$this->previous = $previous;}public function getKey() {return $this->key;}public function getData() {return $this->data;}public function getNext() {return $this->next;}public function getPrevious() {return $this->previous;}}

?

來源：?http://it.taocms.org/03/138.htm

來自為知筆記(Wiz)