KarpRabin Hash 用于 字符串查找
搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万 要统计最热门的10条查询串. 内存<1G. 字符串长 0-255 (1) 主要解决思路 //具体用词和原题不大一样 (2) 算法及其复杂度分析 说下我的思路吧： 为一千万条查询字符串简历trie树，读一条插一条. typedef struct trienode{ char c; struct trienode *str[256]; int count;//表示该字符串的数目 }trienode; 每插入一个查询串，如果最后一个tr...
by xiaozhu2007 - C/C++ - 2008-09-22 20:59:39 阅读（4674） 回复（12）
字符串hash算法比较 链表查找的时间效率为O(N)，二分法为log2N，B+ Tree为log2N，但hash链表查找的时间效率为O(1)。设计高效算法往往需要使用hash链表，常数级的查找速度是任何别的算法无法比拟的，hash链表的构造和冲突的不同实现方法对效率当然有一定的影响，然而hash函数是hash链表最核心的部分，本文尝试分析一些经典软件中使用到的字符串hash函数在执行效率、离散性、空间利用率等方面的性能问题。 1 概述 链表查找的时间效...
字符串hash算法比较 1 概述 链表查找的时间效率为O(N)，二分法为log2N，B+ Tree为log2N，但hash链表查找的时间效率为O(1)。设计高效算法往往需要使用hash链表，常数级的查找速度是任何别的算法无法比拟的，hash链表的构造和冲突的不同实现方法对效率当然有一定的影响，然 而hash函数是hash链表最核心的部分，本文尝试分析一些经典软件中使用到的字符串hash函数在执行效率、离散性、空间利用率等方面的性能问题。 2 经典字...
2.1 PHP中出现的字符串hash函数 [code] static unsigned long hashpjw(char *arKey, unsigned int nKeyLength) { unsigned long h = 0, g; char *arEnd=arKey+nKeyLength; while (arKey < arEnd) { h = (h << 4) + *arKey++; if ((g = (h & 0xF0000000))) { h = h ^ (g >> 24); h = h ^ g; } } return h; } [/code] 小弟不...
有几万个基于某字符集的字符串，长度为30。为了便于另外几万个字符串和这个集合的比较，想把这个字符集合建立一个hash表，但是建立字符串集合的hash表，用什么来做hash函数呢？ 比如拿前10个字符的ASCII码等来做，各位有什么好的办法来建立hash表以使得这个比较操作更快，谢谢！
请教： 如果有好多的字符串（包括汉字）要去匹配一个字符串（即检查有没有在字符串中包括），为了实现效率上的提高，我想使用hash 算法，请问有什么好的办法？这个也算是一种检索吧？
假设a为表原始数据： array a={ #编号 姓名 '05' , '赵七'; '04' , '周六'; '01' , '张三'; '02' , '李四'; '03' , '王五'; ...... } 对'编号'进行hash索引后得到a_i： array a_i={ #Rid 编号 姓名 1=> '01' , '张三'; 2=> '02' , '李四'; 3=> '03' , '王五'; 4=> '04' , '周六'; 5=> '05' , '赵七'; ...... } 当我们查询: select * from a where 编号 between ('0...
假设需要对某个表的字符串类型的列进行索引，并且字符串的长度较长。生成的索引体积就会比较大，同时影响插入及搜索的性能。 这种情况下可以考虑使用对字符串进行hash计算，然后对hash值进行索引。可选的hash函数有crc32(),SHA1,MD5()等等。对于数据量在几十万的数据推荐crc32（）； 下面的本机mysql上进行了以下实验： 测试数据源： 将/var/share/dict/word的文件导入到数据库中。 测试过程： 建立测试表crctest； 创建trigger be...
这是一个函数，实现查找功能 struct _data * lookup_pcb(__u32 saddr,__u16 sport,__u32 index) { struct _data *pcb_p; if( data_hash[index] != NULL ) { pcb_p = data_hash[index]; while( pcb_p != NULL ) { if( pcb_p->saddr==saddr && pcb_p->sport==sport ) { return pcb_p; } else { pcb_p = pcb_p->cl_next; } } } return NULL; } 以下是main函数中的一部分 for(...
