[PHP知识库]LRU缓存机制【php版】

class LRUCache {
	private $_capacity;
	private $_size;
	private $_hashMap;
	private $_head;
	private $_tail;
	/**
	 * @param Integer $capacity
	 */
	function __construct($capacity) {
		$this->_capacity = $capacity;
		$this->_size = 0;
		$this->_head = new DlinkList(-1, -1);
		$this->_tail = new DlinkList(-1, -1);
        $this->_head->next = $this->_tail;
		$this->_tail->prev = $this->_head;
		$this->_hashMap = [];
	}

	/**
	 * @param Integer $key
	 * @return Integer
	 */
	function get($key) {
		if (!array_key_exists($key, $this->_hashMap)) {
			return -1;
		}

		$node = $this->_hashMap[$key];
		$this->moveToHead($node);
		return $node->val;
	}

	/**
	 * 将结点移动到头部
	 * @param $node
	 */
	function moveToHead($node) {
		$this->removeNode($node);
		$this->addToHead($node);
	}
	/**
	 * 双向链表中删除结点
	 * @param $node
	 */
	function removeNode($node) {
		$node->prev->next = $node->next;
		$node->next->prev = $node->prev;
	}

	/**
	 * 双向链表头部插入结点
	 * @param $node
	 */
	function addToHead($node) {
		$node->next = $this->_head->next;
		$node->prev = $this->_head;
		$node->next->prev = $node;
		$this->_head->next = $node;
	}

	/**
	 * @param Integer $key
	 * @param Integer $value
	 * @return NULL
	 */
	function put($key, $value) {
		if (array_key_exists($key, $this->_hashMap)) {
			$node = $this->_hashMap[$key];
			$node->val = $value;
            $this->moveToHead($node);
			return;
		}

		$node = new DlinkList($key, $value);
		$this->_hashMap[$key] = $node;

		$this->addToHead($node);
		++$this->_size;
		if ($this->_size > $this->_capacity) {
			// 删除尾部结点
			$tailNode = $this->_tail->prev;
			$this->removeNode($tailNode);
			unset($this->_hashMap[$tailNode->key]);
			--$this->_size;
		}
	}
}

class DlinkList {

	public $prev = null;
	public $next = null;
	public $val = null;
	public $key = null;

	public function __construct($key, $val) {
		$this->key = $key;
		$this->val = $val;
	}
}