3.1.25 #
解答 #
英文原文指的是 most recently accessed key，因此指的是最近访问的键。
实现比较简单，先在类中定义一个新的成员 cache 作为缓存，
然后修改 Get 方法，在实际查找之前先检查缓存，如果缓存未命中则在查找之后更新它。
要注意的是缓存指向内容的有效性，在数组中指的是下标是否有效，在链表中指的是结点是否为空。
利用《双城记》测试的结果：
代码 #
BinarySearchST #
cache 是一个 int 类型的变量，代表下标。
在二分查找前先检查缓存，要注意cache超出数组大小的情况。
如果缓存未命中，则进行二分查找，并在返回结果前更新缓存。
public TValue Get(TKey key)
{
if (key == null)
throw new ArgumentNullException(nameof(key), "argument to Get() is null");
if (IsEmpty())
return default;
if (_cache < _n && _keys[_cache].Equals(key)) // 缓存检查
return _values[_cache];
var rank = Rank(key);
if (rank < _n && _keys[rank].Equals(key))
{
_cache = rank; // 更新缓存
return _values[rank];
}
return default;
}
SequentialSearchST #
cache 是一个结点类型的变量，代表一个键值对。
类似的，在顺序查找前先检查缓存，如果缓存未命中则更新缓存。
要注意的是如果缓存的结点被删除，需要将缓存置为 null。
Get() 方法
public TValue Get(TKey key)
{
if (key == null)
throw new ArgumentNullException(nameof(key), "key can't be null");
if (_cache != null && _cache.Key.Equals(key)) // 检查缓存
return _cache.Value;
for (var pointer = _first; pointer != null; pointer = pointer.Next)
{
if (pointer.Key.Equals(key))
{
_cache = pointer; // 更新缓存
return pointer.Value;
}
}
return default;
}
Delete() 方法
public void Delete(TKey key)
{
if (key == null)
throw new ArgumentNullException(nameof(key), "key can't be null");
Node before = null, target = _first;
while (target != null && !target.Key.Equals(key))
{
before = target;
target = target.Next;
}
if (target == _cache) // 删除缓存
_cache = null;
if (target != null)
Delete(before, target);
}