时间复杂度为O(1)的Iveely搜索缓存策略

原文链接：http://www.cnblogs.com/liufanping/archive/2012/08/12/2635353.html

在上周发布的Iveely Search Engine 0.1.0版本中，未包含IveelySE的搜索缓存策略，如果没有此缓存，那么每次搜索都将是从数据系统中分析读取结构，将是件很麻烦的事情。今天花了2个小时，写了下缓存策略的Codes。搜索缓存的主要工作是将最近最近搜索比较活跃的内容保存到内存中，以便下次搜索更加快速反应给用户，主要目的也是减少CPU计算和磁盘IO。

IveelySE此时的缓存策略相对简单：将用户搜索的结果，按照时间顺序存入内存中，如果已经在内存中，那么将其提升到最近使用范围内，直到内存中的缓存数量（自定义）达到饱和后，依次淘汰最久未使用的搜索结果。思路相对简单，但是这样的数据结构，我们有一个要求，因为在插入缓存和提取缓存上我们要求时间复杂度为0(1)，要实现这个有一定的难度，HashTable可以实现插入和查找的效率在0(1),但是此时出现了一个问题，我们对关键字的最近最少使用就出现了问题，它不能准确的定位哪一个关键字在另外一个关键字的之前被搜索，以帮助我们记录谁先进入缓存中，而且缓存中内部又是不断变化的。举例说明：

第一时间，搜索关键字“Iveely 1”，那么将记录<Iveely 1,"搜索结果">

第二时间，搜索关键字“Iveely 2”，那么将记录<Iveely 2,"搜索结果">

... ...

第i时间，搜索关键字“Iveely i”，那么将记录<Iveely i,"搜索结果">

... ...

第N时间，搜索关键字“Iveely N”，那么将记录<Iveely N,"搜索结果">

此时此刻，当搜索"Iveely 2"的时候，Hashtable都能为我们提供O(1)的插入缓存和从缓存中提取的效率。但是N已经是我们设定的缓存最大数量了（缓存过大会会占用过多内存，影响程序性能），当我搜索“Iveely Liu” 的时候就糟糕了，由于在缓存中不能找到，那么搜索引擎将从数据库（或分布式文件系统中）提取搜索“Iveely Liu”的结果，然后需要存入缓存，那么如何替换缓存呢？此时，Hashtable就不能为我们做出判断，此时就是我们的双向链表给我们判断，处于双向链表末尾的需要删除，然后将“Iveely Liu” 的搜索结果存入缓存，标记为双向链表的表头的next。

所以我们需要添加辅助的结构-哈希双向链表（自定义命名，原创）。哈希双向链表的主要意义在于，对哈希表的每一个元素都加一个前驱结点和后继结点。图示如下：




每一个Node节点中，都是一个Key-Value，Value中对应着真实的value以及这个节点的前结点和后结点。双向链表的目的是确定该结点的逻辑位置。那么为什么各方面的效率是0(1)呢?

首先看看增加。缓存策略中，新加入的缓存始终是放在最上面的，所以，只需要在Hashtable中Add即可，然后将头结点的替换为它即可。链表的头结点插入（此处是头部插入，不是尾部插入）。所以是O(1).

其次是删除。删除只需要Hashtable的Remove这是0(1),然后将删除结点的前后节点连接即可。也是O(1)

接着是改。在这里，改是先删除，然后再插入。由上面增加和删除，均是O(1)。

最后是查。这是Hashtable的强项，所以，显然是O(1).

这里面，主要是提出一种数据结构，哈希双向链表结构，这种结构，可以在很多情况下使用，并且达到很高的效率。

附上测试源码。我将会在本周，将这些代码融入到IveelySE的缓存策略当中，然后Check-in，供大家看实际应用效果。


namespace Cache
{
/// <summary>
/// 哈希链表
/// </summary>
public class HashLinkTable
{
/// <summary>
/// 内部类，节点值
/// </summary>
public class NodeValue
{

/// <summary>
/// 前驱指针
/// </summary>
public NodeValue Pre { get; set; }

/// <summary>
/// 节点关键字
/// </summary>
public object Key { get; set; }

/// <summary>
/// 节点值
/// </summary>
public object Content { get; set; }

/// <summary>
/// 节点的下一节点值
/// </summary>
public NodeValue Next { get; set; }

/// <summary>
/// 构造方法
/// </summary>
public NodeValue()
{
}
}

/// <summary>
/// Hashtable 是我们最基础的结构
/// 存储结构如下：
/// Key-value（content,next）
/// </summary>
private Hashtable table;

/// <summary>
/// 头部节点
/// </summary>
private NodeValue Head;

/// <summary>
/// 尾部节点
/// </summary>
private NodeValue Tail;

/// <summary>
/// 默认表的容量(不能无限制，太大会占用过多内存影响性能)
/// </summary>
private const int Size = 3;

/// <summary>
/// 构造方法
/// </summary>
public HashLinkTable()
{
//实例化头部节点
this.Head = new NodeValue();
//实例化尾部节点
this.Tail = new NodeValue();
//实例化Hash表
this.table = new Hashtable();
}

/// <summary>
/// 添加节点
/// </summary>
/// <param name="key">关键字</param>
/// <param name="values">值</param>
public void Add(object key, object values)
{
//如果不包含此关键字，则直接添加到头部
if (this.ContainsKey(key))
{
//找到在此关键字
NodeValue nodeValue = (NodeValue)this.table[key];
//将关键字的前驱结点的后继结点该向它的后继节点
if (nodeValue.Next == null)
{
((NodeValue)this.table[nodeValue.Pre.Key]).Next = null;
//尾节点等于它的前驱结点
Tail = (NodeValue)this.table[nodeValue.Pre.Key];
}
else
{
((NodeValue)this.table[nodeValue.Pre.Key]).Next = (NodeValue)this.table[nodeValue.Next.Key];
}
//将关键字的后继节点的前驱指针指向它的前驱结点
if (nodeValue.Next != null)
{
((NodeValue)this.table[nodeValue.Next.Key]).Pre = (NodeValue)this.table[nodeValue.Pre.Key];
}
//删除它在表中的存在
this.table.Remove(key);
}
//添加入节点
this.AddNode(key, values);
}

/// <summary>
/// 返回缓存中存在的值
/// </summary>
/// <param name="key">查找的关键字</param>
/// <returns>返回关键字对应的结果</returns>
public object FindValue(object key)
{
return this.ContainsKey(key) == true ? ((NodeValue)this.table[key]).Content : "NULL";
}

/// <summary>
/// 清楚搜索缓存
/// </summary>
public void Clean()
{
this.table.Clear();
this.Head = new NodeValue();
}


/// <summary>
/// 是否包含关键字
/// </summary>
/// <param name="key">用户的关键字</param>
/// <returns>True为存在，False为不存在</returns>
private bool ContainsKey(object key)
{
return table.ContainsKey(key);
}


/// <summary>
/// 添加节点到表头
/// </summary>
/// <param name="key">节点的Key</param>
/// <param name="values">节点的Value</param>
private void AddNode(object key, object values)
{
//新建节点
NodeValue nodeValue = new NodeValue()
{
Content = values,
Next = Head.Next,
Pre = null,
Key = key
};
//Head的子节点的前驱结点指向nodeValue
if (Head.Next != null)
{
Head.Next.Pre = nodeValue;
nodeValue.Next = Head.Next;
}
//那么此节点是默认的尾节点
else
{
Tail = nodeValue;
}
当前节点为Head节点
//Head = nodeValue;
//head的后驱节点时nodeValue
Head.Next = nodeValue;
Head.Pre = null;
//nodeValue的前驱结点指向Head
nodeValue.Pre = Head;
//当前节点为Head节点
//Head = nodeValue;
//Hash表中先加入
this.table.Add(key, nodeValue);
//如果大于了表的容量
if (this.table.Count > Size)
{
//删除最近进入的元素
NodeValue preValue = Tail.Pre;
this.table.Remove(Tail.Key);
Tail = preValue;
Tail.Next = null;
}
}
}


/// <summary>
/// 缓存队列
/// </summary>
public static class Content
{
/// <summary>
/// 哈希链表
/// </summary>
private static HashLinkTable linkTable = new HashLinkTable();

/// <summary>
/// 加入缓存队列
/// </summary>
/// <param name="key">用户搜索关键字</param>
/// <param name="result">用户关键字对应的结果</param>
public static void Join(object key, object result)
{
linkTable.Add(key, result);
}

/// <summary>
/// 搜索匹配
/// </summary>
/// <param name="key">用户搜索的关键字</param>
/// <returns>返回缓存中的结果</returns>
public static string Match(string key)
{
return linkTable.FindValue(key).ToString();
}

/// <summary>
/// 清楚搜索缓存
/// </summary>
public static void Clean()
{
linkTable.Clean();
}

}
}



执行代码测试：




class Program
{
static void Main(string[] args)
{
Content.Join("A", "a");
Content.Join("B", "b");
Content.Join("C", "c");
Content.Join("D", "d");
Content.Join("E", "e");
Content.Join("C", "c");
Content.Join("A", "a");
Console.ReadKey();
}
}