| 主权项 |
一种基于主动哈希和布隆过滤器的高效缓存方法，其特征在于：该方法的具体步骤如下：步骤一：计算待查找关键词的哈希值，定位对应的哈希链表；步骤二：计算布隆过滤表标记位的坐标，查找到对应的布隆过滤表中标记位值；即由高效查找模块中的标记生成单元完成，结果保存到全局存储模块中的过滤表数组单元中；步骤三：检测所有标记位的值，若全为1，则无法过滤，进行步骤四，只要有一位为0，即判断出关键词不存在，进行过滤，进行步骤十一；步骤四：遍历链表的下一个节点；步骤五：判断该节点的数据是否与关键词匹配，“是”进行步骤六，“否”进行步骤七；步骤六：查询已经命中，读取该节点访问次数，判断该节点访问次数是否超过该节点所述链表的最大访问次数，“是”进行步骤八，“否”进行步骤十；所述的“读取该节点访问次数，判断该节点访问次数是否超过该节点所述链表的最大访问次数”是由高效查找模块中的阈值判断单元完成，其读取的数据来源于全局存储模块中的全局统计量单元；步骤七：判断下一个节点是否为空，“是”回到步骤四，“否”进行步骤十一；步骤八：判断节点是否已经处于链表头部，“是”进行步骤十，“否”进行步骤九；步骤九：移动链表至表头，先将链表从表中摘下，再插入到表头即可；步骤十：更新表头最大访问次数；步骤十一：返回查询失败；其中，在步骤一中所述的计算定位对应的哈希链表节点，是由哈希寻址模块中的ELF哈希单元和寻址定位单元完成，结果保存到全局存储模块中的哈希表数组单元中；哈希寻址模块中所用的ELF哈希算法是一种适合字符串型数据的均匀哈希算法；其算法把字符串的每个字符依次相加，每次将加的结果向左移动4位，即把当前字符ASCII存入哈希结果低四位；如果加的结果大于28位，对结果向右移动24位与原值取异或；如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出；其中，在步骤二中所述的计算布隆过滤表标记位的坐标，查找对应的布隆过滤表中标记位值，是由高效查找模块中的标记生成单元完成，结果保存到全局存储模块中的过滤表数组单元中；标记管理模块具体实施方式为：布隆过滤表后半区下标对应连续三个字符的ASCII码之和，元素为三字符中的第一个；前半区记录所有合法字符0‑9，a‑z，A‑Z,在各桶中的使用情况；将出现下述几种情形：(1)连续三字符ASCII之和第一次出现：后半区对应位赋值为三字符的第一个字符；(2)连续三字符ASCII之和重复出现：由于后半区对应位已被赋值，所以需要用到前半区进行标记；若三字符中第一个字符大于对应位数值，则用标记区的高四位进行标记；0x10：表示此字符在三字符中为第一个；0x20：表示此字符在三字符中为第二个；0x40：表示此字符在三字符中为第三个；若三字符中第一个字符小于对应位数值，则用标记区的低四位进行标记；0x01：表示此字符在三字符中为第一个；0x02：表示此字符在三字符中为第二个；0x04：表示此字符在三字符中为第三个；其中，在步骤三中所述的检测所有标记位的值由高效查找模块中的布隆过滤单元完成，其读取的数据来源于全局存储模块中的过滤表数组单元；为节省空间，哈希表数组与过滤器数组单元用一个二维数组实现；其中第一维对应每一个哈希链表，第二维作为布隆过滤表使用；全局统计量单元由链表结构体中的“链表长度”成员进行记录；其中，在步骤四中所述的遍历链表的下一个节点为计算机的基本链表操作，直接对全局存储模块中的哈希表数组单元进行操作；其中，在步骤五中所述的判断该节点的数据是否与关键词匹配，由高效查找模块的查询匹配单元完成，直接对全局存储模块中的哈希表数组单元进行操作；其中，在步骤六中所述的读取该节点访问次数，判断该节点访问次数是否超过该节点所述链表的最大访问次数由高效查找模块中的阈值判断单元完成，其读取的数据来源于全局存储模块中的全局统计量单元；高效查找模块进行布隆过滤时判断方法为：(1)若后半区对应位为0，则说明该关键词一定不存在，直接返回“查找失败”结果；(2)若后半区对应位不为0，再到前半区读取对应的标记位进行判断；如果标记位有一个为0的，则说明该关键词一定不存在，直接返回“查找失败”结果；其中，在步骤七中所述的判断下一个节点是否为空为计算机的基本链表操作，直接对全局存储模块中的哈希链头数组单元进行判断操作；其中，在步骤八中所述的判断节点是否已经处于链表头部，为计算机的基本链表操作，直接对全局存储模块中的哈希链头数组单元进行判断操作；其中，在步骤九中所述的移动链表至表头，先将链表从表中摘下，再插入到表头即由高效查找模块中的主动哈希单元完成，该功能为基本链表操作的组合；其中，在步骤十中所述的更新表头最大访问次数由高效查找模块中的更新信息单元完成，结果保存到全局存储模块中的全局统计量单元中；其中，在步骤十一中所述的返回查询失败，由高效查找模块的布隆过滤单元，如果为理想过滤器时，全部由布隆过滤单元完成。 |
