puppy居
puppy居士
posts - 41,comments - 27,trackbacks - 0
经典字符串常用的Hash函数有:BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等。BKDRHash和APHash是比较优秀的算法。具体要根据应用,是中文、英文还是混合的字符串,选择合适的Hash算法。

代码实现如下:/**
 * FileName: allHash.cpp
 * Author: ACb0y
 * Create Time: 2011年3月20日21:55:53
 * Last Modify Time: 2001年3月21日0:00:22
 */
#include <iostream>
using namespace std;
typedef unsigned int uint;
typedef struct node
{
 char * str;
 struct node * pNext;
}node;
node * d[1000000];
/**
 * 函数名:uint hashValue(char * str, uint hashFunction(char *str));
 * 功能:用指定的hash函数求字符串的hash值
 * 参数:
 *   输入:
 *   str (char *): 字符串
 *   hashFunction (uint (char * str)): hash函数指针
 *  输出:无
 * 返回值:得到的hash值
 */
uint getHashValue(char * str, uint hashFunction(char * str))
{
 return hashFunction(str) % 1000000;
}
/**
 * 函数名: uint SDBM_Hash(char * str);
 * 功能:获取字符串的SDBM哈希值
 * 参数:
 *  输入:str (char *): 字符串
 *      输出:无
 * 返回值:字符串的SDBM哈希值
 */
uint SDBM_Hash(char * str)
{
 uint hash = 0;
 while (*str)
 {
  hash = (*str++) + (hash << 6) + (hash << 16) - hash;
 }
 return (hash & 0x7FFFFFFF);
}
/**
 * 函数名: uint RS_Hash(char * str);
 * 功能:获取字符串的RS哈希值
 * 参数:
 *  输入:str (char *): 字符串
 *      输出:无
 * 返回值:字符串的RS哈希值
 */
uint RS_Hash(char * str)
{
 uint a = 63689;
 uint b = 378551;
 uint hash = 0;
 while (*str)
 {
  hash = hash * a + (*str++);
  a *= b;
 }
 return (hash & 0x7FFFFFFF);
}
/**
 * 函数名: uint JS_Hash(char * str);
 * 功能:获取字符串的RS哈希值
 * 参数:
 *  输入:str (char *): 字符串
 *      输出:无
 * 返回值:字符串的JS哈希值
 */
uint JS_Hash(char * str)
{
 uint hash = 1315423911;
 while (*str)
 {
  hash ^= ((hash << 5) + (*str++) + (hash >> 2));
 }
 return (hash & 0x7FFFFFFF);
}
/**
 * 函数名: uint PJW_Hash(char * str);
 * 功能:获取字符串的RS哈希值
 * 参数:
 *  输入:str (char *): 字符串
 *      输出:无
 * 返回值:字符串的PJW哈希值
 */
uint PJW_Hash(char * str)
{
 uint BitsInUnignedInt = (uint)(sizeof(uint) * 8);
 uint ThreeQuarters = (uint)((BitsInUnignedInt * 3) / 4);
 uint OneEighth = (uint)(BitsInUnignedInt / 8);
 uint HighBits = (uint)(0x7FFFFFFF) << (BitsInUnignedInt - OneEighth);
 uint hash = 0;
 uint test = 0;
 while (*str)
 {
  hash = (hash << OneEighth) + (*str++);
  if ((test = hash & HighBits) != 0)
  {
   hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
  }
 }
 return (hash & 0x7FFFFFFF);
}
/**
 * 函数名: uint ELF_Hash(char * str);
 * 功能:获取字符串的RS哈希值
 * 参数:
 *  输入:str (char *): 字符串
 *      输出:无
 * 返回值:字符串的ELF哈希值
 */
uint ELF_Hash(char * str)
{
 uint hash = 0;
 uint x = 0; 
 while (*str)
 {
  hash = (hash << 4) + (*str++);
  if ((x = hash & 0xF0000000L) != 0)
  {
   hash ^= (x >> 24);
   hash &= ~x;
  }
 }
 return (hash & 0x7FFFFFFF);
}
/**
 * 函数名: uint BKDR_Hash(char * str);
 * 功能:获取字符串的RS哈希值
 * 参数:
 *  输入:str (char *): 字符串
 *      输出:无
 * 返回值:字符串的BKDR哈希值
 */
uint BKDR_Hash(char * str)
{
 uint seed = 131; //31, 131, 1313, 13131, 131313 etc...
 uint hash = 0;
 while (*str)
 {
  hash = hash * seed + (*str++);
 }
 return (hash & 0x7FFFFFFF);
}
/**
 * 函数名: uint BKDR_Hash(char * str);
 * 功能:获取字符串的RS哈希值
 * 参数:
 *  输入:str (char *): 字符串
 *      输出:无
 * 返回值:字符串的BKDR哈希值
 */
uint DJB_Hash(char * str)
{
 uint hash = 5381;
 while (*str)
 {
  hash += (hash << 5) + (*str++);
 }
 return (hash & 0x7FFFFFFF);
}
/**
 * 函数名: uint BKDR_Hash(char * str);
 * 功能:获取字符串的RS哈希值
 * 参数:
 *  输入:str (char *): 字符串
 *      输出:无
 * 返回值:字符串的BKDR哈希值
 */
uint AP_Hash(char * str)
{
 uint hash = 0;
 int i;
 for (i = 0; *str; ++i)
 {
  if ((i & 1) == 0)
  {
   hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
  }
  else
  {
   hash ^= (~((hash) << 11 ^ (*str++) ^ (hash >> 5)));
  }
 }
 return (hash & 0x7FFFFFFF);
}
/**
 * GCC中的字符串Hash函数ext/hash_fun.h
 * 函数名: size_t __stl_hash_string(const char * __s);
 * 功能:获取字符串的RS哈希值
 * 参数:
 *  输入:__s (const char *): 字符串
 *      输出:无
 * 返回值:字符串的哈希值
 */
inline size_t __stl_hash_string(const char * __s)
{
 unsigned long __h = 0;
 for (; *__s; ++__s)
 {
  __h = 5 * __h + *__s;
 }
 return size_t(__h);
}
/**
 * 函数名: void init();
 * 功能:初始化node * d数组
 * 参数:
 *  输入:无
 *      输出:无
 * 返回值:无
 */
void init()
{
 memset(d, 0, sizeof(d));
}
/**
 * 函数名: node * getNode();
 * 功能:获取一个新的节点的指针
 * 参数:
 *  输入:无
 *      输出:无
 * 返回值:新申请的节点的指针
 */
node * getNode()
{
 node * pNew = (node *)malloc(sizeof(node));
 pNew->pNext = NULL;
 pNew->str = NULL;
 return pNew;
}
/**
 * 函数名: bool insert(char * str, uint hashFunction(char * str));
 * 功能:把字符串插入hash容器中
 * 参数:
 *  输入:
 *    str (char *): 字符串
   uint hashFunction(char * str): hash函数
 *      输出:无
 * 返回值:
 *    false: 插入失败
 *   true: 插入成功
 */
bool insert(char * str, uint hashFunction(char * str))
{
 node * pNew;
 pNew = getNode();
 if (NULL == pNew)
 {
  return false;
 }
 pNew->str = (char *)malloc(strlen(str) + 1);
 strcpy(pNew->str, str);
 
 uint hashValue = getHashValue(str, hashFunction);
 if (NULL == d[hashValue])
 {
  d[hashValue] = pNew;
 }
 else
 {
  pNew->pNext = d[hashValue];
  d[hashValue]->pNext = pNew;
 }
 return true;
}
/**
 * 函数名:bool query(char * str, uint hashFunction(char * str));
 * 功能:hash容器中查找字符串
 * 参数:
 *  输入:
 *    str (char *): 字符串
   uint hashFunction(char * str): hash函数
 *      输出:无
 * 返回值:
 *    查找到的指向str的指针。
 */
char * query(char * str, uint hashFunction(char * str))
{
 uint hashValue = getHashValue(str, hashFunction);
 if (NULL == d[hashValue])
 {
  return NULL;
 }
 node * pCur = d[hashValue];
 while (NULL != pCur)
 {
  if (strcmp(pCur->str, str) == 0)
  {
   return pCur->str;
  }
  pCur = pCur->pNext;
 }
 return NULL;
}
int main()
{
 init();
 freopen("in.txt", "r", stdin);
 int n, k;
 char str[1000];
 scanf("%d%d/n", &n, &k);
 cout << n << " " << k << endl;
 
 while (n--)
 {
  gets(str);
  insert(str, BKDR_Hash);
 }
 
 while (k--)
 {
  gets(str);
  char * pStr = query(str, BKDR_Hash);
  if (NULL == pStr)
  {
   printf("not found!/n");
  }
  else
  {
   printf("find the string = %s/n", pStr);
  }
 }
 return 0;
}

posted on 2013-03-29 17:53 puppy 阅读(201) 评论(0)  编辑 收藏 引用
只有注册用户登录后才能发表评论。