现在的位置: 首页 > 综合 > 正文

如何建立英文字符的哈希表

2018年11月06日 ⁄ 综合 ⁄ 共 510字 ⁄ 字号 评论关闭

       经常会遇到需要建立字符串哈希表的问题,例如strtok,或者删除指定字符串的中一些字符等等,可见的字符有256个,那么很容易想到建立一个哈希表,但是其中有一些技巧,可以节省空间,其实可以使用bitmap的形式实现,但是c语言中没有现成的东西,所以需要自己实现。下面就是实现方式:

char hash[32] = {0};
do
{
    hash[*str >> 3] |=  (1 << (*str & 7));
}while(*str++)

      以上就建立了一个可以容纳256个字符的hash表,首先解释一下为什么只用32个char的数组就可以表示给256个字符打点标记,因为32个字符的数据内存上是连续的,每个字符是8个bit,所以char hash[32]总共有256和bit,也就能够表示指定的字符是否出现过。接下来就是如何置位了,*str >> 3表示 *str / 8,也就是计算该字符应该在第几个char上打点标记,*str & 7表示*str % 7,可以计算出应该在该char上的哪个bit打点标记。至于为什么用位操作实现,是因为位操作很快。

     下面是如何查找字符是否在哈希表中的代码:

if((map[*str >> 3]) &  (1<< (*str & 7)))

抱歉!评论已关闭.