3.1.25

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

英文原文指的是 most recently accessed key,因此指的是最近访问的键。

实现比较简单,先在类中定义一个新的成员 cache 作为缓存,
然后修改 Get 方法,在实际查找之前先检查缓存,如果缓存未命中则在查找之后更新它。
要注意的是缓存指向内容的有效性,在数组中指的是下标是否有效,在链表中指的是结点是否为空。

利用《双城记》测试的结果:

代码

BinarySearchST

cache 是一个 int 类型的变量,代表下标。
在二分查找前先检查缓存,要注意cache超出数组大小的情况。
如果缓存未命中,则进行二分查找,并在返回结果前更新缓存。

public TValue Get(TKey key)
{
    if (key == null)
        throw new ArgumentNullException("argument to Get() is null");
    if (IsEmpty())
        return default(TValue);
    if (this.cache < this.n && this.keys[this.cache].Equals(key)) // 缓存检查
        return this.values[this.cache];
    int rank = Rank(key);
    if (rank < this.n && this.keys[rank].Equals(key))
    {
        this.cache = rank;                                        // 更新缓存
        return this.values[rank];
    }

    return default(TValue);
}

SequentialSearchST

cache 是一个结点类型的变量,代表一个键值对。
类似的,在顺序查找前先检查缓存,如果缓存未命中则更新缓存。
要注意的是如果缓存的结点被删除,需要将缓存置为 null

Get() 方法

public TValue Get(TKey key)
{
    if (key == null)
        throw new ArgumentNullException("key can't be null");

    if (this.cache != null && this.cache.Key.Equals(key)) // 检查缓存
        return this.cache.Value;
    for (Node pointer = this.first; pointer != null; pointer = pointer.Next)
    {
        if (pointer.Key.Equals(key))
        {
            this.cache = pointer;                         // 更新缓存
            return pointer.Value;
        }
    }
    return default(TValue);
}

Delete() 方法

public void Delete(TKey key)
{
    if (key == null)
        throw new ArgumentNullException("key can't be null");
    Node before = null, target = this.first;
    while (target != null && !target.Key.Equals(key))
    {
        before = target;
        target = target.Next;
    }
    if (target == this.cache)           // 删除缓存
        this.cache = null;
    if (target != null)
        Delete(before, target);
}

另请参阅

SymbolTable 库

上一题 下一题