LRU 算法是一种缓存淘汰策略，它根据数据的访问情况来决定哪些数据应该被保留在缓存中，哪些数据应该被淘汰。具体来说，当缓存达到一定大小时，如果需要添加新数据，就会先检查缓存中是否已经存在该数据，如果存在，则将其移到缓存的最前面；如果不存在，则将新数据添加到缓存的最前面，同时将缓存中最后一个数据淘汰。

<?php

/**
 * Created by PhpStorm.
 * User: LinFei
 * Created time 2023/05/20 20:01:54
 * E-mail: fly@eyabc.cn
 */
declare (strict_types=1);

class LRUCache
{
    /**
     * The front of the array contains the LRU element
     *
     * @var array
     */
    protected array $data = [];

    /**
     * Create a LRU Cache
     *
     * @throws InvalidArgumentException
     */
    public function __construct(
        /**
         * Cache capacity
         * @var int $capacity
         */
        protected int $capacity
    )
    {
        if ($capacity <= 0) {
            throw new InvalidArgumentException();
        }
    }

    /**
     * Get the value cached with this key
     *
     * @param int|string $key Cache key
     * @param mixed|null $default The value to be returned if key not found. (Optional)
     * @return mixed
     */
    public function get(int|string $key, mixed $default = null): mixed
    {
        if (isset($this->data[$key])) {
            $this->recordAccess($key);
            return $this->data[$key];
        } else {
            return $default;
        }
    }

    /**
     * Put something in the cache
     *
     * @param int|string $key Cache key
     * @param mixed $value The value to cache
     */
    public function put(int|string $key, mixed $value): void
    {
        if (isset($this->data[$key])) {
            $this->data[$key] = $value;
            $this->recordAccess($key);
        } else {
            $this->data[$key] = $value;
            if ($this->size() > $this->capacity) {
                // remove least recently used element (front of array)
                reset($this->data);
                unset($this->data[key($this->data)]);
            }
        }
    }

    /**
     * Get the number of elements in the cache
     *
     * @return int
     */
    public function size(): int
    {
        return count($this->data);
    }

    /**
     * Does the cache contain an element with this key
     *
     * @param int|string $key The key
     * @return bool
     */
    public function has(int|string $key): bool
    {
        return isset($this->data[$key]);
    }

    /**
     * Remove the element with this key.
     *
     * @param int|string $key The key
     * @return mixed Value or null if not set
     */
    public function remove(int|string $key): mixed
    {
        if (isset($this->data[$key])) {
            $value = $this->data[$key];
            unset($this->data[$key]);
            return $value;
        } else {
            return null;
        }
    }

    /**
     * Clear the cache
     */
    public function clear(): void
    {
        $this->data = [];
    }

    /**
     * Moves the element from current position to end of array
     *
     * @param int|string $key The key
     */
    protected function recordAccess(int|string $key)
    {
        $value = $this->data[$key];
        unset($this->data[$key]);
        $this->data[$key] = $value;
    }

    /**
     * Get the cache data
     * @return array
     */
    public function getData(): array
    {
        return $this->data;
    }
}

$time = microtime(true);

$lru = new LRUCache(100);

for ($i = 0; $i < 10000; $i++) {
    $lru->put('key' . $i, 'value' . $i);
}

// foreach ($lru->getData() as $key => $value) {
//     echo $key . '=>' . $value . PHP_EOL;
// }

// var_dump($lru->size());
var_dump(microtime(true) - $time);