public $hash = []; // key => DoubleListNode
* @param Integer $capacity
function __construct($capacity)
$this->cache = new DoubleList();
if (!isset($this->hash[$key])) return -1;
/** @var DoubleListNode $node */
$node = $this->hash[$key];
$this->cache->remove($node);
$this->cache->append($node);
function put($key, $value)
if (isset($this->hash[$key])) { // key 存在
/** @var DoubleListNode $node */
$node = $this->hash[$key];
$this->cache->remove($node);
$this->cache->append($node);
} else { // key 不存在, 新增节点
$node = new DoubleListNode($key, $value);
$this->cache->append($node);
$this->hash[$key] = $node;
if ($this->size == $this->cap) {
$oldNode = $this->cache->tail->pre;
$this->cache->remove($oldNode);
unset($this->hash[$oldNode->key]);
public function __construct($key = null, $val = null)
if ($key) $this->key = $key;
if ($val) $this->val = $val;
public function __construct()
$this->head = new DoubleListNode();
$this->tail = new DoubleListNode();
$this->head->next = $this->tail;
$this->tail->pre = $this->head;
public function append(DoubleListNode $node)
$node->pre = $this->head;
$node->next = $this->head->next;
$this->head->next->pre = $node;
$this->head->next = $node;
public function remove(DoubleListNode $node)
$node->pre->next = $node->next;
$node->next->pre = $node->pre;