LRU Cache

源码地址在这里，我的环境是 ISO C++14 标准。

LRU Cache（Least Recently Used Cache）是利用最近最少使用的思路来更新和淘汰目标的算法，这里我分享一个C++ 实现的 LRU Cache。

为了实现该算法，需要先实现 Double Linked List 和 Hash Map（下面简称 List 和 Map）。

List

下面是我实现的 List 每个节点 m_node 的定义（为了方便使用，m_node 的数据域包含 key - value 两种）

template<typename K, typename V>
struct m_node
{
	m_node() {}
	m_node(K k, V v) :key(k), value(v) {}
	K key;
	V value;
	m_node* pre{ nullptr };
	m_node* next{ nullptr };
};

下面是我实现的 m_list，只定义大小、头结点、尾结点。

int _size{ 0 };
m_node<K, V>* _head;
m_node<K, V>* _tail;

支持常见的 List 操作，已经做好了内存管理。

Map

为了实现 Map ，我先实现了一个简单通用的 hash 计算函数 m_hash。

template <typename...>
using m_void = void;

struct m_false { constexpr static bool value{ false }; };
struct m_true { constexpr static bool value{ true }; };

template <typename T, typename = m_void<>>
struct m_has_hash : m_false { };
template <typename T>
struct m_has_hash<T, m_void<decltype(std::declval<T&>().hash())>> : m_true { };

template <typename K>
std::enable_if_t<m_has_hash<K>::value, size_t> m_hash(K key)
{
	return key.hash();
}

template <typename K>
std::enable_if_t<!m_has_hash<K>::value, size_t> m_hash(K key)
{
	return hash(key);
}

利用编译期类型检查判断 K是否自己的 hash 函数，如果没有就用通用的 hash 函数。****

通用 hash 函数实现比较简单：

// ELF hash implements.
inline size_t elf_hash(const char* str, size_t len)
{
	size_t _hash = 0;
	size_t _g = 0;
	for (size_t i = 0; i < len; ++i)
	{
		char c = str[i];
		_hash = (_hash << 4) + (c * 13);
		_g = _hash & 0xf0000000;
		if (_g)
		{
			_hash ^= (_g >> 24);
			_hash ^= _g;
		}
	}
	return _hash;
}

template<typename KEY>
inline size_t hash(const KEY& key)
{
	return (size_t)key;
}

template<>
inline size_t hash<std::string>(const std::string& key)
{
	return elf_hash(key.c_str(), key.length());
}

template<>
inline size_t hash<unsigned long long>(const unsigned long long& key)
{
	return elf_hash((const char*)&key, sizeof(unsigned long long));
}

m_map 的定义如下：

size_t _length;
V _default_value;
m_list<K, V>* _tables;
  • _length：散列表数量是 1 << _length， **(hash % (1 << _length)) == (hash & ((1 << _length) - 1))**。
  • _default_value：是没由对应 key 的默认 value。
  • _tables：是实际的散列表，通过前面的 m_list实现。

支持常见的 Map 操作，已经做好了内存管理。

LRU Cache

用 List 存储value，用 map 存储 key - List Node Address （下面简称 Address ）。这样可以在常数时间复杂度下通过Key 获取 Address ，再通过 Address 来对 List 进行操作。

下面是 m_LRU_cache的定义：

int _capacity;
V _default_value;
m_map<K, m_node<K, V>*> _m_map{4, nullptr};
m_list<K, V> _m_list;
  • _capacity：LRU Cache 容量。
  • _default_value：没有找到时的默认返回结果。
  • _m_map：通过 key 在常数时间复杂度下找到 Address 。
  • _m_list：存储 value（不需要存储 key，这里是为了用之前实现的 m_list，实现只有 value 的List 很简单，就不过多赘述）。

这里只实现的LRU Cache 的两个常见操作 get 和 put，支持 reverse（扩容）。

get 实现思路是判断当前 key 有没有 value：

  • 有就返回 value，并把对应节点放到 _m_list 尾部。
  • 没有返回默认值。
V get(K key)
{
	m_node<K, V>* p = _m_map.get(key);
	if (p)
	{
		_m_list.disconnect(p);
		_m_list.push_back(p);
		return p->value;
	}
	return _default_value;
}

put 实现思路是判断当前 key 有没有 value：

  • 有就修改对应 value，并把对应节点放到 _m_list 尾部。

  • 没有就判断当前缓存是否容量已满：

    • 未满就新建一个节点 p。
    • 满了就弹出 _m_list 头部节点到节点 p，并将 key 和 value 修改成对应的。

    将 key 和 p保存到 _m_map，并将 p 放到 _m_list 尾部。

void put(K key, V value)
{
	m_node<K, V>* p = _m_map.get(key);
	if (p)
	{
		_m_list.disconnect(p);
		p->value = value;
		_m_list.push_back(p);
		return;
	}
	if (_m_list.size() < _capacity)
	{
		p = new m_node<K, V>(key, value);
	}
	else
	{
		p = _m_list.pop_front();
		p->key = key;
		p->value = value;
	}
	_m_map[key] = p;
	_m_list.push_back(p);
}

Test

测试 1：

void test01()
{
	std::ofstream log("log.txt", std::ostream::ate);
	if (!log.is_open())
	{
		return;
	}
	morisa::m_LRU_cache<std::string, int> M(3, -1);
	log << "start...\n";
	log << "A -- " << M.get("A") << "(default value)\n";
	M.put("A", 1, "B", 2, "C", 3);
	log << "after put A -- 1, B -- 2, C -- 3:\n";
	M.prints(log);
	M.get("A");
	log << "after get A:\n";
	M.prints(log);
	M.reverse(4);
	M.put("C", 4, "D", 5, "E", 6, "F", 7);
	log << "after reverse 4 and put C -- 4, D -- 5, E -- 6, F -- 7:\n";
	M.prints(log);
	log << "after get D:\n";
	M.get("D");
	M.prints(log);
	log.close();
}

输出：

start...
A -- -1(default value)
after put A -- 1, B -- 2, C -- 3:
A -- 1
B -- 2
C -- 3
after get A:
B -- 2
C -- 3
A -- 1
after reverse 4 and put C -- 4, D -- 5, E -- 6, F -- 7:
C -- 4
D -- 5
E -- 6
F -- 7
after get D:
C -- 4
E -- 6
F -- 7
D -- 5

测试 2：

先实现一个 key class：

  • 空构造、拷贝构造函数。
  • 赋值 = 函数。
  • 类自己的 hash 函数（有用地址的方法，这里我没有这样做）。
  • 为了方便测试，重载 << 运算符。
class Obj
{
public:
	Obj(){}
	Obj(size_t hash) : _hash(hash) {}

	Obj(const Obj& other) { this->_hash = other._hash; }

	Obj& operator = (const Obj& other) 
	{ 
		this->_hash = other._hash;
		return *this; 
	}

	inline const size_t hash() const { return _hash; }
private:
	size_t _hash{ 0 };
};

std::ostream& operator<<(std::ostream& os, const Obj& obj)
{
	os << obj.hash();
	return os;
}

void test02()
{
	std::ofstream log("log.txt", std::ostream::ate);
	if (!log.is_open())
	{
		return;
	}
	morisa::m_LRU_cache<Obj, std::string> M(3, "NULL");
	Obj b1(1), b2(2), b3(3), b4(4), b5(5), b6(6);
	log << "start...\n";
	log << "b1 -- " << M.get(b1) << "(default value)\n";
	M.put(b1, "B1", b2, "B2", b3, "B3");
	log << "after put b1 -- B1, b2 -- B2, b3 -- B3:\n";
	M.prints(log);
	M.get(b1);
	log << "after get b1:\n";
	M.prints(log);
	M.reverse(4);
	M.put(b3, "B4", b4, "B5", b5, "B6", b6, "B7");
	log << "after reverse 4 and put b3 -- B4, b4 -- B5, b5 -- B6, b6 -- B7:\n";
	M.prints(log);
	log << "after get b4:\n";
	M.get(b4);
	M.prints(log);
	log << "after get b1 = b5 and get b1:\n";
	b1 = b5;
	M.get(b1);
	M.prints(log);
	log.close();
}

输出：

start...
b1 -- NULL(default value)
after put b1 -- B1, b2 -- B2, b3 -- B3:
1 -- B1
2 -- B2
3 -- B3
after get b1:
2 -- B2
3 -- B3
1 -- B1
after reverse 4 and put b3 -- B4, b4 -- B5, b5 -- B6, b6 -- B7:
3 -- B4
4 -- B5
5 -- B6
6 -- B7
after get b4:
3 -- B4
5 -- B6
6 -- B7
4 -- B5
after get b1 = b5 and get b1:
3 -- B4
6 -- B7
4 -- B5
5 -- B6