当前访客身份:游客 [ 登录 | 加入 OSCHINA ]

代码分享

当前位置:
代码分享 » C/C++  » 常用工具方法
RyanLee

暴雪的hash算法

RyanLee 发布于 2010年10月31日 23时, 5评/10143阅
分享到: 
收藏 +0
1
据说是暴雪公司的经典hash算法
详细请看:
打造最快的Hash表(和Blizzard的对话)
http://blog.csdn.net/angelo_yz/archive/2005/10/15/504452.aspx
魔兽哈希算法封装和测试
http://blog.csdn.net/eaglewood2005/archive/2009/07/30/4394583.aspx

我修改整理一下,只有两个接口:Hash Hashed


标签: <无>

代码片段(3) [全屏查看所有代码]

1. [代码]StringHash     跳至 [1] [2] [3] [全屏预览]

/************************************************************************/
/*函数名:Hashed
/*功  能:检测一个字符串是否被hash过
/*返回值:如果存在,返回位置;否则,返回-1
/************************************************************************/
unsigned long StringHash::Hashed(string lpszString)  

{   
	const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;  
	//不同的字符串三次hash还会碰撞的几率无限接近于不可能
	unsigned long nHash = HashString(lpszString, HASH_OFFSET);  
	unsigned long nHashA = HashString(lpszString, HASH_A);  
	unsigned long nHashB = HashString(lpszString, HASH_B);  
	unsigned long nHashStart = nHash % m_tablelength,  
	nHashPos = nHashStart;  

	while ( m_HashIndexTable[nHashPos].bExists)  
	{   
		if (m_HashIndexTable[nHashPos].nHashA == nHashA && m_HashIndexTable[nHashPos].nHashB == nHashB)   
			return nHashPos;   
		else   
			nHashPos = (nHashPos + 1) % m_tablelength;  

		if (nHashPos == nHashStart)   
			break;   
	}  

	return -1; //没有找到  
}  

/************************************************************************/
/*函数名:Hash
/*功  能:hash一个字符串 
/*返回值:成功,返回true;失败,返回false
/************************************************************************/
bool StringHash::Hash(string lpszString)
{  
	const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;  
	unsigned long nHash = HashString(lpszString, HASH_OFFSET);  
	unsigned long nHashA = HashString(lpszString, HASH_A);  
	unsigned long nHashB = HashString(lpszString, HASH_B);  
	unsigned long nHashStart = nHash % m_tablelength, 
		nHashPos = nHashStart;  
        //你得自己保证此字符串没有被hash过,否则hash表中就会存在完全相同的元素
	while ( m_HashIndexTable[nHashPos].bExists)  
	{   
                //如果发生碰撞,就在相邻位置插入
		nHashPos = (nHashPos + 1) % m_tablelength;  
		if (nHashPos == nHashStart) //一个轮回  
		{  
			//hash表中没有空余的位置了,无法完成hash
			return false;   
		}  
	}  
	m_HashIndexTable[nHashPos].bExists = true;  
	m_HashIndexTable[nHashPos].nHashA = nHashA;  
	m_HashIndexTable[nHashPos].nHashB = nHashB;  

	return true;  
}  

2. [文件] StringHash.h ~ 828B     下载(171)     跳至 [1] [2] [3] [全屏预览]

#pragma once

#define MAXTABLELEN 1024    // 默认哈希索引表大小 
//////////////////////////////////////////////////////////////////////////  
// 哈希索引表定义  
typedef struct  _HASHTABLE
{  
	long nHashA;  
	long nHashB;  
	bool bExists;  
}HASHTABLE, *PHASHTABLE ;  

class StringHash
{
public:
	StringHash(const long nTableLength = MAXTABLELEN);
	~StringHash(void);
private:  
	unsigned long cryptTable[0x500];  
	unsigned long m_tablelength;    // 哈希索引表长度  
	HASHTABLE *m_HashIndexTable; 
private:
	void InitCryptTable();                                               // 对哈希索引表预处理 
	unsigned long HashString(const string& lpszString, unsigned long dwHashType); // 求取哈希值      
public:
	bool Hash(string url);
	unsigned long Hashed(string url);    // 检测url是否被hash过
};

3. [文件] StringHash.cpp ~ 4KB     下载(164)     跳至 [1] [2] [3] [全屏预览]

#include "StdAfx.h"
#include "StringHash.h"

StringHash::StringHash(const long nTableLength /*= MAXTABLELEN*/)
{
	InitCryptTable();  
	m_tablelength = nTableLength;  
	//初始化hash表
	m_HashIndexTable = new HASHTABLE[nTableLength];  
	for ( int i = 0; i < nTableLength; i++ )  
	{  
		m_HashIndexTable[i].nHashA = -1;  
		m_HashIndexTable[i].nHashB = -1;  
		m_HashIndexTable[i].bExists = false;  
	}          
}

StringHash::~StringHash(void)
{
	//清理内存
	if ( NULL != m_HashIndexTable )  
	{  
		delete []m_HashIndexTable;  
		m_HashIndexTable = NULL;  
		m_tablelength = 0;  
	}  
}

/************************************************************************/
/*函数名:InitCryptTable
/*功  能:对哈希索引表预处理  
/*返回值:无
/************************************************************************/
void StringHash::InitCryptTable()  
{   
	unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;  

	for( index1 = 0; index1 < 0x100; index1++ )  
	{   
		for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )  
		{   
			unsigned long temp1, temp2;  
			seed = (seed * 125 + 3) % 0x2AAAAB;  
			temp1 = (seed & 0xFFFF) << 0x10;  
			seed = (seed * 125 + 3) % 0x2AAAAB;  
			temp2 = (seed & 0xFFFF);  
			cryptTable[index2] = ( temp1 | temp2 );   
		}   
	}   
}  

/************************************************************************/
/*函数名:HashString
/*功  能:求取哈希值   
/*返回值:返回hash值
/************************************************************************/
unsigned long StringHash::HashString(const string& lpszString, unsigned long dwHashType)  
{   
	unsigned char *key = (unsigned char *)(const_cast<char*>(lpszString.c_str()));  
	unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;  
	int ch;  

	while(*key != 0)  
	{   
		ch = toupper(*key++);  

		seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);  
		seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;   
	}  
	return seed1;   
}  

/************************************************************************/
/*函数名:Hashed
/*功  能:检测一个字符串是否被hash过
/*返回值:如果存在,返回位置;否则,返回-1
/************************************************************************/
unsigned long StringHash::Hashed(string lpszString)  

{   
	const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;  
	//不同的字符串三次hash还会碰撞的几率无限接近于不可能
	unsigned long nHash = HashString(lpszString, HASH_OFFSET);  
	unsigned long nHashA = HashString(lpszString, HASH_A);  
	unsigned long nHashB = HashString(lpszString, HASH_B);  
	unsigned long nHashStart = nHash % m_tablelength,  
	nHashPos = nHashStart;  

	while ( m_HashIndexTable[nHashPos].bExists)  
	{   
		if (m_HashIndexTable[nHashPos].nHashA == nHashA && m_HashIndexTable[nHashPos].nHashB == nHashB)   
			return nHashPos;   
		else   
			nHashPos = (nHashPos + 1) % m_tablelength;  

		if (nHashPos == nHashStart)   
			break;   
	}  

	return -1; //没有找到  
}  

/************************************************************************/
/*函数名:Hash
/*功  能:hash一个字符串 
/*返回值:成功,返回true;失败,返回false
/************************************************************************/
bool StringHash::Hash(string lpszString)
{  
	const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;  
	unsigned long nHash = HashString(lpszString, HASH_OFFSET);  
	unsigned long nHashA = HashString(lpszString, HASH_A);  
	unsigned long nHashB = HashString(lpszString, HASH_B);  
	unsigned long nHashStart = nHash % m_tablelength, 
		nHashPos = nHashStart;  

	while ( m_HashIndexTable[nHashPos].bExists)  
	{   
		nHashPos = (nHashPos + 1) % m_tablelength;  
		if (nHashPos == nHashStart) //一个轮回  
		{  
			//hash表中没有空余的位置了,无法完成hash
			return false;   
		}  
	}  
	m_HashIndexTable[nHashPos].bExists = true;  
	m_HashIndexTable[nHashPos].nHashA = nHashA;  
	m_HashIndexTable[nHashPos].nHashB = nHashB;  

	return true;  
}  


开源中国-程序员在线工具:Git代码托管 API文档大全(120+) JS在线编辑演示 二维码 更多»

发表评论 回到顶部 网友评论(5)

  • 1楼:你条草 发表于 2012-04-11 17:33 回复此评论
    很不错!!想请教一下大牛,我想基于这个来实现一个可扩展的hash表,想到的就只有通过链表链接新增的hash表啦,关于插入新的hash值,可以通过一个当前hash表的空余空间计数值来确定是否存在空间写入。但查找数据的时候,就无可避免地要在链表头开始进行搜索。
    后来想到了个方法,每个hash表带一个数据校验码,该校验码能够验证只能验证该hash表内的所有hash值,当某个hash值进行删除时,校验码需要更新。因此查找数据时,可通过查找的hash值与每个hash表的校验码进行校验,确定所在位置……但这个校验方式能否实现,估计我就无能为力啦
  • 2楼:山哥 发表于 2013-01-29 10:58 回复此评论
    请问有 Java 版的吗?
  • 3楼:可观 发表于 2013-01-29 11:32 回复此评论
    能把你的乱码注释修改一下吗,看着太蛋疼了
  • 4楼:scott-zhai 发表于 2015-05-07 18:03 回复此评论

    引用来自“山哥”的评论

    请问有 Java 版的吗?
  • 5楼:xinranli 发表于 2017-10-30 21:37 回复此评论
    想要matlab版本的
开源从代码分享开始 分享代码
RyanLee的其它代码 全部(9)...