一种哈希表元素失效删除方法

摘要

本发明提供了一种哈希表元素失效删除方法，解决哈希表失效元素及时删除的问题。该方法通过为每个哈希桶提供超时时间T

说明书

技术领域

本发明涉及计算机算法领域，涉及一种哈希表元素失效删除方法。

背景技术

随着网络信息化在世界范围内不断提高，Internet上的网络节点数以亿 计，导致各种网络节点之间的交互关系剧增。而在网络节点行为实时分析时， 需要一种快速的定位和操作节点交互行为的方法，同时，由于计算节点的RAM 存储量比较小，需要及时删除失效的网络节点交互行为。因此，在分析网络 节点行为时，需要一种高效的失效元素删除方法。

哈希表又叫散列表，它通过把关键码值映射到表中一个位置来访问记录， 以加快查找速度，其中映射函数叫做哈希函数。当不同的关键码值映射到同 一个地址时，就存在碰撞，而解决碰撞的一个基本方法是采用链表法。对哈 希表有三个操作：插入、查询、删除。目前存在的哈希表元素失效（超时） 删除方法可以有如下几种：（1）、基于元素生命周期完结触发超时删除方法； （2）、基于优先级队列的超时方法；（3）、基于哈希表元素轮询的超时方法。

其中第一种方法由于假设元素具有完整生命周期的特点，导致当元素无 失效条件时，将永远无法被删除，第二种方法基于哈希表元素相对较少，优 先级队列所占内存相对较少。第三种方法基于对哈希表元素扫描所占时间不 足以影响其他操作的实时性。

发明内容

为了解决哈希表失效元素及时删除功能，本发明提供了一种哈希表元素 失效删除方法。

一种哈希表元素失效删除方法,通过为每个哈希桶提供超时时间T_bucket，为 每个关键码提供超时时间T_key，两个时间粒度进行不同元素插入、查询时，更 新每个关键码值T_key，并将最新访问的关键码值放置到哈希桶最优先访问的位 置上，在此过程中，根据哈希桶超时时间T_bucket设定，检查哈希桶上具有相同 哈希值的关键码，如果元素超时，即删除失效元素，同时根据哈希桶扫描策 略，检查哈希表其他哈希桶元素上的其他关键码值，并删除因超时失效的元 素。

本发明的有益效果：本发明通过为桶和关键码值增加超时失效时间，判 定关键码值何时可以被删除。同时对相同桶上的关键码值排序，让最新访问 的关键码值放置到最新位置，最旧的关键码值放置到末尾，当删除元素时， 快速定位该删除的元素。同时，采用扫描的方法，及时删除其他未访问的桶 上的元素，保证哈希表中元素最新，提高存储效率。

具体实施方式

本发明通过为每个哈希桶提供超时时间T_bucket，为每个关键码提供超时时 间T_key，两个时间粒度可不同元素插入、查询时，更新每个关键码值T_key，并 将最新访问的关键码值放置到桶最优先访问的位置上，在此过程中，根据桶 超时时间T_bucket设定，检查桶上具有相同哈希值的关键码，如果元素超时，即 删除失效元素，同时根据桶扫描策略，检查哈希表其他桶元素上的其他关键 码值，并删除因超时失效的元素。

下面使用具体实施例对本发明提供哈希表插入、查询、删除进行详细描述。

哈希表插入操作如下：

（1）根据关键码计算哈希值，从而得到哈希桶位置。

（2）遍历哈希桶上具有相同哈希值的关键码。对于每个关键码值：

①检查关键码值是否超时失效，如果失效，执行②。否则执行③。

②删除该关键码值，并更新之后关键码值的关系，继续执行③。

③判定当前关键码值和即将插入的关键码值是否相同。如果相同，返 回插入失败，结束。如果不同，继续执行①。

（3）将即将插入的关键码值放置到该桶的最优先访问位置，并设置关键码 值的超时时间。

（4）执行哈希表扫描操作。

哈希表查询操作如下：

（1）根据关键码计算哈希值，从而得到哈希桶位置。

（2）遍历哈希桶上具有相同哈希值的关键码。对于每个关键码值：

①检查关键码值是否超时失效，如果失效，执行②。否则执行③。

②删除该关键码值，并更新之后关键码值的关系，继续执行③。

③判定当前关键码值和查询的关键码值是否相同。如果相同，返回关 键码值对应的信息，结束。如果不同，继续执行①。

（3）将查询的关键码值放置到该桶的最优先访问位置，并更新关键码值的 超时时间。

（4）执行哈希表扫描操作。

哈希表删除操作如下：

（1）根据关键码计算哈希值，从而得到哈希桶位置。

（2）遍历哈希桶上具有相同哈希值的关键码。对于每个关键码值：

①检查关键码值是否超时失效，如果失效，执行②。否则执行③。

②删除该关键码值，并更新之后关键码值的关系，继续执行③。

③判定当前关键码值和即将插入的关键码值是否相同。如果相同，删 除该元素，并更新具有相同哈希值的关键码的相对关系。如果不同， 继续执行①。

（3）执行哈希表扫描操作。

哈希表超时扫描操作：

（1）获取上次哈希失效扫描的下一个桶位置，桶计数设定为零。

（2）如果当前桶还未失效，继续（1），否则执行（3）。

（3）遍历当前桶上所有关键码值。

①检查关键码值是否超时失效，如果失效，执行②。否则执行③。

②删除该关键码值，并更新之后关键码值的关系，继续执行③。

③获取下一个关键码值。

（4）桶计数加一。

（5）如果桶计数超过某个阈值，结束。否则，继续执行（1）。