Liuw's Thinkpad

很久都没有写点技术相关的文章了，是不是说明自己越来越懒了呢，呵呵。

突然想起那天 TX 的笔试题，最后一题附加题是要求判断一个 vector<string> letter 中的元素是否存在于另一个 vector<string> news 中。第一下给出了一个很锉的算法——双循环。用屁股想想都知道，这个 O(m*n) 的算法是最笨的方法了。多想了一下，记得以前考虑过一个单词统计的问题，用的是 Hash 的方法。其实这里用 Hash 也是比较好的，给 news 做一个 Hash Table，然后 letter 中的元素经过 Hash 之后看是否在 Table 中，这样的复杂度是 O(m+n)，好多了。

当然，现在要讲的也不是这么小儿科的问题。Hash 倒是用得不少了，但是具体怎么实现，却没有去了解过。那么今天就忙里偷闲做一下功课吧。

我这里谈的 Hash，意义在于提供一种快速存取数据的方法，即是要通过一种算法建立键值和真实值的关系。一个真实值只可以对应一个键值，但是一个键值却可能对应多个真实值（亦即是发生碰撞）。熟悉 Python、Perl 等语言的同学，应该对 key pair 不陌生，呵呵。对一个值 value 进行 Hash，实质上就是创建一种 （key, value）的二元组关系。其中 key 最坏情况下是可以在 O(n) 复杂度内进行查找的，这样就可以大大加快搜索的过程。设计得好的话，key 可以在 O(1) 内找到。

挺出名的一个 Hash 函数

unsigned long hashpjw(register CONST char *str,
                      register unsigned long int size)
{
    register CONST char *p;
    register unsigned long h=0,g;

    asc_assert((NULL != str) && (size > 0));

    for(p = str; *p != ''; p++) {
        h = (h << 4) + (*p);
        if (0 != (g = h&0xf0000000)) {
          h = h ^ (g >> 24);
          h = h ^ g;
        }
    }
    return h % size;
}

OpenSSL 中的 Hash 函数

unsigned long lh_strhash(char *str)
{
    int i,l;
    unsigned long ret=0;
    unsigned short *s;

    if (str == NULL) return(0);
    l=(strlen(str)+1)/2;
    s=(unsigned short *)str;

    for (i=0; i < l; ++i)
        ret^=(s[i]<<(i & 0x0f));
    return(ret);
}

/* The following hash seems to work very well on normal text strings
* no collisions on /usr/dict/words and it distributes on %2^n quite
* well, not as good as MD5, but still good.
*/
unsigned long lh_strhash(const char *c)
{
    unsigned long ret=0;
    long n;
    unsigned long v;
    int r;

    if ((c == NULL) || (*c == 0))
    return(ret);
/*
unsigned char b[16];
MD5(c,strlen(c),b);
return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
*/

    n=0x100;
    while (*c)
    {
        v=n|(*c);
        n+=0x100;
        r= (int)((v>>2)^v) & 0x0f;
        ret=(ret(32-r));
        ret & = 0xFFFFFFFFL;
        ret^=v*v;
        c++;
    }

    return((ret>>16)^ret);
}

看到代码，觉得其实做一个 Hash 函数，关键不在于代码有多长，更多是分布的计算和碰撞的处理。现在暂时没有时间去深究。改日看了《算法导论》再来深入。