# Hash模板 个人模板

/**
* Hash模板
* Based: 0
* template<unsigned long _SZ,class _T, unsigned long *pFun(_T _Off)>
* class _My_Hash_ToInt
* 传入数据大小_SZ,传入类型_T,Hash函数
* 传入类型_T必须重载 = 和 == 符号
* 收录了ELFHash函数
* 主要是为了判重的简化些的模板
* Hash算法性能比较见 http://www.cnblogs.com/lonelycatcher/archive/2011/08/23/2150587.html
*/

const long hashsize = 51071; //Hash表大小(注意修改)
// 各种Hash算法
unsigned int SDBMHash(char *str)
{
unsigned int hash = hashsize;

while (*str)
{
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash << 6) + (hash << 16) - hash;
}

return (hash & 0x7FFFFFFF);
}

// RS Hash Function
unsigned int RSHash(char *str)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = hashsize;

while (*str)
{
hash = hash * a + (*str++);
a *= b;
}

return (hash & 0x7FFFFFFF);
}

// JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash = 1315423911;

while (*str)
{
hash ^= ((hash << 5) + (*str++) + (hash >> 2));
}

return (hash & 0x7FFFFFFF);
}

// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
unsigned int hash             = hashsize;
unsigned int test             = 0;

while (*str)
{
hash = (hash << OneEighth) + (*str++);
if ((test = hash & HighBits) != 0)
{
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}

return (hash & 0x7FFFFFFF);
}

// ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash = hashsize;
unsigned int x    = 0;

while (*str)
{
hash = (hash << 4) + (*str++);
if ((x = hash & 0xF0000000L) != 0)
{
hash ^= (x >> 24);
hash &= ~x;
}
}

return (hash & 0x7FFFFFFF);
}

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = hashsize;

while (*str)
{
hash = hash * seed + (*str++);
}

return (hash & 0x7FFFFFFF);
}

// DJB Hash Function
unsigned int DJBHash(char *str)
{
unsigned int hash = 5381;

while (*str)
{
hash += (hash << 5) + (*str++);
}

return (hash & 0x7FFFFFFF);
}

// AP Hash Function
unsigned int APHash(char *str)
{
unsigned int hash = hashsize;
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);
}

// 程序模板
template<typename _T>
class _My_Hash_ToInt_Data
{
public:
_My_Hash_ToInt_Data()
{
times = 0;
next = -1;
}
_T data;
long times;
long next;
};
template<long _SZ,class _T, unsigned long pFun(_T& _Off)>
class _My_Hash_ToInt
{
public:
_My_Hash_ToInt()
{
memset(hash, -1, sizeof(hash));
length = 0;
};
~_My_Hash_ToInt(){};
long find(_T _Off)
{
long pos = hash[pFun(_Off)];
while(pos >= 0)
{
if(data[pos].data == _Off)
return pos;
else
pos = data[pos].next;
}
return -1;
}
long insert(_T _Off)
{
long oldPos = pFun(_Off);
long pos = hash[oldPos];
while(pos >= 0)
{
if(data[pos].data == _Off)
{
data[pos].times ++;
return pos;
}
else
pos = data[pos].next;
}
data[length].data = _Off;
data[length].times = 1;
data[length].next = hash[oldPos];
hash[oldPos] = length ;
return length ++;
}
void clear()
{
length = 0;
memset(hash, -1, sizeof(hash));
memset(data, -1, sizeof(data));
}
//Member
long length;
_My_Hash_ToInt_Data<_T> data[_SZ];
long hash[hashsize];
};

//节点类（注意修改）
class node
{
public:
char str[60];
bool operator == (node &strin)
{
return !strcmp(str, strin.str);
}
node& operator = (node &strin)
{
strcpy(str, strin.str);
return (*this);
}
};
//扩展Hash函数（注意修改）
unsigned long ELFHashEx(node &strIn)
{
return ELFHash(strIn.str);
}
_My_Hash_ToInt<10005, node, ELFHashEx>hash;//Hash类例子

0 条评论

• ### ZOJ 3309 Search New Posts 解题报告

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3309

• ### 数论模板（个人模板）

若a与n互质（即GCD（a，n） = 1），则a^Ψ（n） = 1 （mod n）a^{\varphi(n)} \equiv 1 \pmod n

• ### ECUST 09年 校赛个人赛第八场（最后一场）总结

这次我只AC了一题（在结束的那一刻，另一题在题目来源地网站上AC了，我们的OJ上仍然WA，我们OJ的Special Judge真是—_—!）

• ### 一致性hash算法及java实现

典型的应用场景是：有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。

• ### 面试题，如何在千万级的数据中判断一个值是否存在？

当你看到这个标题的时候，你也许会想我可以使用hashmap之类的来存储值，然后get就是了。又或者把数据存在数据库里然后去判断就可以了。

• ### hash散列 introduction

hash散列是在记录的存储位置与他的关键字之间建立的对应关系f, 使得每个key都对应一个存储位置, 查找时根据key的hash去查找.

• ### 纸上谈兵: 哈希表 (hash table)

HASH 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系，而且集合A的某个元素只能对应集合B中的一个元素...

• ### djb2 hash算法

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就...

• ### 如果世界上只有一种数据结构，那么我选择哈希！

来源：blog.csdn.net/liweisnake/article/details/104779497

• ### 【专业技术】STL hash_map使用（一）

今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。 hash_map类在头文件hash_map中，和所有其...