精华内容
下载资源
问答
  • 这是个在暴雪字符串哈希...使用单向散列函数,从概率上认为,不同字符串的3种不同的种子的3个哈希值不会是都是相同的。(计算的是10的22.3次方分之一的概率) 3)每个节点有3个hash值(hash1,hash2,hash3),hash1 是寻

    这是个在暴雪字符串哈希算法基础上实现的哈希表。在代码实现上有一定优化。

    设计上:
    1)加密表是足够长的(unsigned long)无符号型数组。数组的值是由算法计算的固定的一些值。加密表是用来计算字符串(在某种子的情况下)的哈希值。
    2)哈希值是字符串(大写)的所有的字符的ascii码相关的。使用单向散列函数,从概率上认为,不同字符串的3种不同的种子的3个哈希值不会是都是相同的。(计算的是10的22.3次方分之一的概率)
    3)每个节点有3个hash值(hash1,hash2,hash3),hash1 是寻位的基准,hash2,hash3 是判断节点是否相同的标准。
    4)hash1值冲突的解决方式是,从hash1开始遍历表并获取空位(顺延方式)
    5)把表查找字符串键优化为比较三个整形键值(先使用折半方式,然后顺延方式查找。因为表内存不够时是会拓展一倍内存的)
    6)表长度是2的次幂,最小是16。表内存不够时可以拓展一倍,由空闲位置计数器来判断


    特点:

    (1)插入

    使用顺延方式查找空位,没有使用链表。节省内存空间。

    (2)查找

    1)先使用折半方式,然后顺延方式查找。

    因为表内存不够时是会拓展一倍内存的 。先通过hash1不断去掉高位的方式来检查能适应表内存拓展方式和哈希取余方式

    2)三哈希值比较方式来检查:

    比较键值是比较3个整形数,而不是字符串,可以提高查找比较效率

    (3)移除

    查找到节点后,设置该节点的哈希值为0,并显式调用节点的值对象的析构函数

    1、hash算法理论

    1)hash值

    从字符串数组中查找匹配的字符串最合适的算法自然是使用哈希表。所谓Hash,一般是一个整数,通过某种算法,可以把一个字符串"压缩" 成一个整数,这个数称为Hash,当然,无论如何,一个32位整数是无法对应回一个字符串的,但如果有合适的校验方式,两个字符串计算出的Hash值相等的可能非常小。

    2)hash函数(单向散列函数

    Blizzard的哈希算法是非常高效的(代码实现可参考 章节 1-2 由加密表随机种子(bzhashstr)),使用的是单向散列函数(One-Way Hash),举个例子,字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。

    通常是构造一个数组来作为哈希表,这个数组的容量根据程序的要求来定义(如1024),每一个Hash值通过位与运算对应到数组中的一个位置,只要检查这个字符串的哈希值对的位置有没有被占用。最快的复杂度是 O(1)。算法计算代码实现参考章节 3-2 哈希表定义 (函数 T* put(const char* sKey)加入字符串到哈希表)。

    3)冲突解决(顺延方式

    假如两个字符串在哈希表中对应的位置相同怎么办?究竟一个数组容量是有限的,这种可能性很大。解决该问题的方法很多,很多算法都可以转化成链表来解决,只要在哈希表的每个入口挂一个链表,保存所有对应的字符串。

    然而Blizzard的哈希表没有使用链表,而采用"顺延"的方式来解决问题。具体算法计算代码实现,参考本文章节 2-2 哈希表实现 (函数 INT_PTR getIndex(const char* sKey) const)。

    4)校验方式(三个哈希值

    在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。假如说两个不同的字符串经过一个哈希算法得到的入口点一致有可能,但用三个不同的哈希算法算出的入口点都一致,几率是1:18889465931478580854784,大概是10的 22.3次方分之一(使用3次单向散列函数运算),对一个游戏程序来说足够安全了。


    2、哈希值计算

    (1)加密表

    哈希运算种子表是用来计算字符串对应的哈希整数的。

    加密表

    static unsigned long cryptTable[0x500];

    哈希种子表是否初始化

    static int cryptTableInited = 0;

    初始化加密表

    static void initCryptrTable()
    {    
    	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 );    //初始化加密表
    		}    
    	}    
    }   


    (2)字符串生成哈希值

    根据字符串返回哈希值(字符串地址,随机种子)。

    由加密表根据哈希算法和随机种子来计算哈希值。(随机数算法是按暴雪字符串哈希算法来计算)

     

    unsigned long bzhashstr(const char *str, unsigned long seed)   //字符串,随机种子
    {
    	unsigned char *key = (unsigned char *)str;   
    	unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;//种子1,2   
    	int ch;   
    
    	if (!cryptTableInited)
    	{
    		initCryptrTable();
    		cryptTableInited = 1;
    	}
    
    	while(*key != 0)   
    	{
    		ch = *key++;
    		ch = toupper(ch); 
    
    		seed1 = cryptTable[(seed << 8) + ch] ^ (seed1 + seed2);//由加密表计算出的数
    		seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; //修改种子2   
    	}   
    	return seed1;    
    }   


    其中:小写字母转成大写字母

    #define toupper(c) (((c) >= 'a' && (c) <= 'z') ? (c) ^ 0x20 : (c))


    3、哈希表

    (1)哈希表迭代器定义

    迭代器提供获取表头和遍历的接口。迭代器是容器类的友元类,方便访问。

    template <typename T>
    class CHashTableIterator
    {
    public:
    	CHashTableIterator()
    	{
    		m_pTable = NULL;
    		m_nIndex = 0;
    	}
    	CHashTableIterator(const CCustomHashTable<T> &table)
    	{
    		setTable(table);
    	}
    	inline void setTable(const CCustomHashTable<T> &table)
    	{
    		m_pTable = &table;
    		m_nIndex = 0;
    	}
    	inline T* first() //返回第一个有效哈希节点的值的地址
    	{
    		INT_PTR nLen = m_pTable->m_nLen;
    		typename CCustomHashTable<T>::template HashNode<T> *pNode;
    
    		m_nIndex = 0;
    		while (m_nIndex < nLen)
    		{
    			pNode = &m_pTable->m_pTable[m_nIndex]; 
    			m_nIndex++;
    			if (pNode->hash1)//检查是否是有效节点
    				return &pNode->value;
    		}
    		return NULL;
    	}
    	inline T* next()//返回下一个有效哈希节点的值的地址
    	{
    		INT_PTR nLen = m_pTable->m_nLen;
    		typename CCustomHashTable<T>::template HashNode<T> *pNode;
    
    		while (m_nIndex < nLen)
    		{
    			pNode = &m_pTable->m_pTable[m_nIndex];
    			m_nIndex++;
    			if (pNode->hash1)//检查是否是有效节点
    				return &pNode->value;
    		}
    		return NULL;
    	}
    private:
    	const CCustomHashTable<T>*m_pTable;
    	INT_PTR				m_nIndex;
    };
    


    (2)哈希表定义

    提供表对象的访问接口。
    管理表内对象的内存。移除和清除时会析构表内对象。
    template <typename T>
    class CCustomHashTable
    {
    	friend class CHashTableIterator<T>;
    public:
    	typedef CCustomHashTable<T> ClassType;
    
    public:
    	CCustomHashTable(size_t len = 0)
    	{
    		m_pTable = NULL;
    		m_nLen = m_nFree = 0;
    		m_nInitSize = len;
    		if (len > MiniSize)
    		{
    			//表的长度必须是2的次方数,否则哈希下标算法无法工作
    			size_t val;
    			for (int i=0; i<32; ++i)
    			{
    				val = size_t(1 << i);
    				if (len <= val)
    				{
    					m_nInitSize = val;//初始化长度为2的次方数,且大于等于需求的长度len
    					break;
    				}
    			}
    		}
    		else m_nInitSize = MiniSize;//限制长度必须是2的次方数,否则哈希下标算法无法工作
    	}
    	virtual ~CCustomHashTable()
    	{
    		clear();
    	}
    	//清空哈希表(这个接口会调用表中的对象的析构函数)
    	void clear()
    	{
    		//循环调用析构函数
    		for (INT_PTR i=m_nLen-1; i>-1; --i)
    		{
    			if (m_pTable[i].hash1)
    			{
    				m_pTable[i].value.~T();//析构哈希表中的所有的节点中对象的内存
    			}
    		}
    		//释放内存
    		if (m_pTable) realloc(m_pTable, 0);
    		m_pTable = NULL;
    		m_nLen = m_nFree = 0;
    	}
    	//获取有效对象数量
    	inline size_t count() const { return m_nLen - m_nFree; }
    protected:
    	/** 定义内部使用的哈希节点数据结构 **/
    	template <typename T1>
    	class HashNode
    	{
    	public:
    		unsigned int hash1;	//哈希值1
    		unsigned int hash2;	//哈希值2
    		unsigned int hash3;	//哈希值3
    		T1 value;		//数据值
    	};
    
    	typedef HashNode<T> NodeType;
    public:
    	//通过键查找值
    	inline T* get(const char* sKey)
    	{
    		INT_PTR idx = getIndex(sKey);//根据键获取哈希表下标
    		return (idx >= 0) ? &m_pTable[idx].value : NULL;
    	}
    	//通过键查找值
    	inline const T* get(const char* sKey) const
    	{
    		INT_PTR idx = getIndex(sKey);
    		return (idx >= 0) ? &m_pTable[idx].value : NULL;
    	}
    
    
    	/* 通过键添加值(返回合适的节点的地址)
    	* 如果一个hash索引被使用,则向后递推索引,到达最大索
    	* 引则从头开始查找空位,直到找到空位或完成一次表遍历。(顺延方式)
    	*/
    	inline T* put(const char* sKey)
    	{
    		unsigned int hash1, hash2, hash3, idx, start;
    		NodeType *pNode;
    	
    		//内存空间不足,增长内存空间(拓展一倍)
    		if (m_nFree <= 0)
    		{
    			size_t oldlen = m_nLen;
    			m_nLen = (oldlen <= 0) ? m_nInitSize : m_nLen << 1;//表长度必须是2的次方
    			m_nFree = m_nLen - oldlen;
    			m_pTable = (NodeType *)realloc(m_pTable, m_nLen * sizeof(m_pTable[0]));//重新分配哈希表(rehash)
    			memset(&m_pTable[oldlen], 0, m_nFree * sizeof(m_pTable[0]));
    		}
    	
    		hash1 = bzhashstr(sKey, 0);//由字符串和随机种子生成3个哈希值(只有3个哈希值都相等的才是相等的字符串)
    		hash2 = bzhashstr(sKey, 1);
    		hash3 = bzhashstr(sKey, 2);
    		start = idx = hash1 & (m_nLen - 1);//从hash1的位置开始检查空位(表的长度是2的次方,所以减一后可以位与运算)
    		do 
    		{
    			pNode = &m_pTable[idx];
    			//如果该位置没有值,则设置到该位置,否则向后找到一个空位置
    			if (!pNode->hash1)//没有hash1值则为空,则把节点对象设置在该空位
    			{
    				pNode->hash1 = hash1;
    				pNode->hash2 = hash2;//设置该点的哈希值2
    				pNode->hash3 = hash3;//设置该点的哈希值3
    				m_nFree--;
    				new (&pNode->value)T();//调用构造函数初始化该节点中的对象
    				return &pNode->value;//返回节点地址
    			}
    	#ifdef _DEBUG
    			//从概率上认为,3种哈希值都重复的就是认为是重复添加的
    			else if (pNode->hash1 == hash1 && pNode->hash2 == hash2 && pNode->hash3 == hash3)
    			{
    				//调用者重复添加,或者确实出现错误!
    				DebugBreak();
    			}
    	#endif
    			//从下一位继续寻找位置(遍历了整张表来找空位)
    			idx = (idx + 1) & (m_nLen - 1);//表长度必须是2的次方才能使用这种遍历方式,并避免超出长度
    		} 
    		while (start != idx);
    		return NULL;//遍历了一遍也没有找到合适位置则退出(这里实际上是不会出现的,因为空间不够时会拓展空间)
    	}
    	
    	//通过键更新值
    	inline INT_PTR update(const char* sKey, const T &value)
    	{
    		INT_PTR idx = getIndex(sKey);
    		if (idx >= 0)
    			m_pTable[idx].value = value;
    		return idx;
    	}
    	//通过键移除值,没有找到则返回-1
    	inline INT_PTR remove(const char* sKey)
    	{
    		INT_PTR idx = getIndex(sKey);
    		NodeType *pNode;
    		if (idx >= 0)
    		{
    			pNode = &m_pTable[idx];
    			pNode->hash1 = pNode->hash2 = pNode->hash3 = 0;
    			m_nFree++;//空位增加
    			pNode->value.~T();//调用析构函数处理该节点中的对象(与初始化时的构造函数相对应)
    			return idx;
    		}
    		return -1;
    	}
    	//根据哈希键获取在表中的索引(先用折半方式查找,后用顺延方式查找,根据三个哈希值检查)
    	INT_PTR getIndex(const char* sKey) const
    	{
    		unsigned int hash1, hash2, hash3;
    		unsigned int idx, start;
    		size_t len;
    		NodeType *pNode;
    
    		if (m_nLen <= 0)
    			return -1;
    		//根据键和种子获取哈希值
    		hash1 = bzhashstr(sKey, 0);//计算哈希值1
    		hash2 = bzhashstr(sKey, 1);//计算哈希值2
    		hash3 = bzhashstr(sKey, 2);//计算哈希值3
    
    		//首先开始折半查找(hash1不断去掉高位来查找)
    		len = m_nLen;
    		while (len >= m_nInitSize)
    		{
    			idx = hash1 & (len - 1);//表的长度是2的次方
    			pNode = &m_pTable[idx];
    			if (pNode->hash1 == hash1 && pNode->hash2 == hash2 && pNode->hash3 == hash3)
    			{
    				return idx;//获取哈希值对应的节点的下标
    			}
    			len >>= 1;
    		}
    
    		//折半查找不到则从hash1位置(hash1)开始遍历整个表(顺延获取)
    		start = idx = hash1 & (m_nLen - 1);//表长度必须是2的次方
    		do 
    		{
    			pNode = &m_pTable[idx];
    			if (pNode->hash1 == hash1 && pNode->hash2 == hash2 && pNode->hash3 == hash3)
    			{
    				return idx;
    			}
    			idx = (idx + 1) & (m_nLen - 1);//表长度必须是2的次方
    		}
    		while (start != idx);
    		return -1;
    	}
    
    protected:
    	//内存申请函数,作用与c函数中的realloc实现相同,实现申请、扩展以及释放内存
    	virtual void* realloc(void* p, size_t s)
    	{
    		return ::realloc(p, s);
    	}
    protected:
    	size_t		m_nInitSize;//表初始长度
    	size_t		m_nLen;		//哈希表的长度,必须是2的次方否则哈希下标算法无法工作
    	size_t		m_nFree;	//空闲节点数量
    	HashNode<T>	*m_pTable;	//哈希表
    public:
    	static const size_t MiniSize = 16;//哈希表最小长度,必须是2的次方否则哈希下标算法无法工作
    };




    展开全文
  • 最近小谭又被问了一个问题,编程语言中的字符串匹配函数是怎么实现的,是啥原理。看来大猫又要展示他靠才华吃面的大招了。小谭一边心里犯嘀咕,这还能有啥原理,直接用不就行了,管那么多干啥,一边对大猫说,今天又...

    最近小谭又被问了一个问题,编程语言中的字符串匹配函数是怎么实现的,是啥原理。

    看来大猫又要展示他靠才华吃面的大招了。

    小谭一边心里犯嘀咕,这还能有啥原理,直接用不就行了,管那么多干啥,一边对大猫说,今天又想要吃啥面了。

    大猫就是这样,经常问你一个问题,你要不会,然后让你请他吃碗面,他给你讲清楚。

    大猫腼腆一笑表示今天吃一碗拉面就行,估计是今天这个大招的技术含量不够高吧,一碗拉面就给应付了。

    果然,大猫仅用 5 个字就形容了他的大招,暴力匹配法,小谭一听暴力法,眉头一皱,貌似也想到了答案,大猫赶紧继续补充。

    暴力匹配就是用最原始、最笨的方法去匹配,把两个字符串分别称作目标字符串和模式字符串,然后要判断在目标字符串中能否匹配到模式字符串。

    小谭灵光一闪,迫不及待的说出了自己的思路,这个简单啊,不就是从目标串第一个字符和模式串的第一个字符开始比较,如果两个字符相同,则继续比较两者后面的字符,否则,将模式串移动到目标串的第二个字符重新开始比较

    a1b142e34889b0f5b30acde4b616ba65.png

    大猫有点着急了,眼看自己的大招已然被识破,赶紧顺势总结了一番。

    是哒,这就是最常规的思路,也是最简单的算法,这个暴力匹配算法被称作 BF (bure force) 算法。

    小谭依然追问到,这个算法没啥技术含量,就是用的笨方法,还有没有更好一点的,不然都不值这碗拉面。

    有,还真有比这更好一点的,不过要加个卤蛋才可以。看样子大猫早就准备好的了,满满的套路。

    我们可以使用哈希算法来优化 BF 算法,大猫看起来很得意的样子。

    为啥要用哈希呢,怎么用,小谭有点不太明白。

    你看在 BF 算法中,每次都是拿目标字符串和模式串一个字符一个字符的比较,这样很耗时间。

    如果目标串的长度为 a,模式串的长度为 b,那么目标串其实就可以拆成 (a-b+1) 个子串…

    等等,为啥是 (a-b+1) 呢,小谭有点疑惑。

    我给你画张图你就明白了,大猫边说边开始在手机上画起了图。

    60c7e78b858f1a5f6be56b2ca5956c42.png

    目标串长度为6,模式串长度为3,所以目标串一共有4个子串

    接下来其实就是把这 (a-b+1) 个子串和模式串挨个比较即可。

    那这里也没有特别的啊,也没用到哈希函数啊,小谭紧接着问大猫。

    别急啊,关键就在下面的哈希函数了,我们把目标字符串中的每个子串和模式串都使用一个哈希函数来获得哈希值,然后我们就可以直接比较其对应的哈希值就可以了,由于哈希值是一个数字,数字之间的比较是很快的。因此,判断模式串是否在目标串中,只需要比较两者是否有相等的哈希值就好了。

    这个思路有点巧妙啊,小谭有点茅塞顿开的感觉了。

    这其实只是一个思路,核心在于这个哈希函数的设计,比如如果存在哈希冲突怎么处理,怎么只遍历一次目标串即可算出所有子串的哈希值,这些都是这个哈希函数要解决的问题,另外这种算法叫做 RK 算法,是两位外国人名字的首字母组合而成。

    这碗拉面总算是值了,不过最后这个哈希函数的具体设计下回还得继续讲清楚啊。。。

    没问题啊,不过我也还得回去再查查资料重新学习下,争取下回给你讲明白,今天给你讲的就是个主要的思路。。。

    展开全文
  • 字符串哈希函数算法PHP 实现

    千次阅读 2008-01-04 14:08:00
    或许还有朋友不清楚字符串的哈希函数到底有什么用,这个用处呢,就是将字符串转换成数字,同时让所得数字尽量平均分布在容器中,换句话说就是让字符串得到相同数字这种情况尽可能少出现。当然咯...容器太小,...

    恩...或许还有朋友不清楚字符串的哈希函数到底有什么用,这个用处呢,就是将字符串转换成数字,同时让所得数字尽量平均的分布在容器中,换句话说就是让字符串得到相同数字这种情况尽可能少的出现。当然咯...容器太小,内容太多那么再好的算法也没法避免出现冲突 = =b

    从网上找到的哈希函数基本上都是C算法的...最后只好从C and Java 算法中整理 and 测试了这些 PHP中的实现方法。有几个经典的算法在 PHP 下会有问题,字符串一长就会全部取 0,那些我就没有再列出来了。代码就看下面咯:

    PHP:
    1. function DJBHash($str) // 0.22
    2. {
    3. $hash = 0;
    4. $n = strlen($str);
    5. for ($i = 0; $i <$n; $i++)
    6. {
    7. $hash += ($hash <<5 ) + ord($str[$i]);
    8. }
    9. return $hash % 701819;
    10. }
    11.  
    12. function ELFHash($str) // 0.35
    13. {
    14. $hash = $x = 0;
    15. $n = strlen($str);
    16.  
    17. for ($i = 0; $i <$n; $i++)
    18. {
    19. $hash = ($hash <<4) + ord($str[$i]);
    20. if(($x = $hash & 0xf0000000) != 0)
    21. {
    22. $hash ^= ($x>> 24);
    23. $hash &= ~$x;
    24. }
    25. }
    26. return $hash % 701819;
    27. }
    28.  
    29. function JSHash($str) // 0.23
    30. {
    31. $hash = 0;
    32. $n = strlen($str);
    33.  
    34. for ($i = 0; $i <$n; $i++)
    35. {
    36. $hash ^= (($hash <<5) + ord($str[$i]) + ($hash>> 2));
    37. }
    38. return $hash % 701819;
    39. }
    40.  
    41. function SDBMHash($str) // 0.23
    42. {
    43. $hash = 0 ;
    44. $n = strlen($str);
    45.  
    46. for ($i = 0; $i <$n; $i++)
    47. {
    48. $hash = ord($str[$i]) + ($hash <<6 ) + ($hash <<16 ) - $hash;
    49. }
    50. return $hash % 701819;
    51. }
    52.  
    53. function APHash($str) // 0.30
    54. {
    55. $hash = 0 ;
    56. $n = strlen($str);
    57.  
    58. for ($i = 0; $i <$n; $i++)
    59. {
    60. if (($i & 1 ) == 0 )
    61. {
    62. $hash ^= (($hash <<7 ) ^ ord($str[$i]) ^ ($hash>> 3 ));
    63. }
    64. else
    65. {
    66. $hash ^= ( ~ (($hash <<11 ) ^ ord($str[$i]) ^ ($hash>> 5)));
    67. }
    68. }
    69. return $hash % 701819;
    70. }
    71.  
    72. function DEKHash($str) // 0.23
    73. {
    74. $n = strlen($str);
    75. $hash = $n;
    76.  
    77. for ($i = 0; $i <$n; $i++)
    78. {
    79. $hash = (($hash <<5) ^ ($hash>> 27)) ^ ord($str[$i]);
    80. }
    81. return $hash % 701819;
    82. }
    83.  
    84. function FNVHash($str) // 0.31
    85. {
    86. $hash = 0;
    87. $n = strlen($str);
    88.  
    89. for ($i = 0; $i <$n; $i++)
    90. {
    91. $hash *= 0x811C9DC5;
    92. $hash ^= ord($str[$i]);
    93. }
    94.  
    95. return $hash % 701819;
    96. }
    97.  
    98. function PJWHash($str) // 0.33
    99. {
    100. $hash = $test = 0;
    101. $n = strlen($str);
    102.  
    103. for ($i = 0; $i <$n; $i++)
    104. {
    105. $hash = ($hash <<4) + ord($str[$i]);
    106.  
    107. if(($test = $hash & -268435456)  != 0)
    108. {
    109. $hash = (( $hash ^ ($test>> 24)) & (~-268435456));
    110. }
    111. }
    112.  
    113. return $hash % 701819;
    114. }
    115.  
    116. function PHPHash($str) // 0.34
    117. {
    118. $hash = 0;
    119. $n = strlen($str);
    120.  
    121. for ($i = 0; $i <$n; $i++)
    122. {
    123. $hash = ($hash <<4) + ord($str[$i]);
    124. if (($g = ($hash & 0xF0000000)))
    125. {
    126. $hash = $hash ^ ($g>> 24);
    127. $hash = $hash ^ $g;
    128. }
    129. }
    130. return $hash % 701819;
    131. }
    132.  
    133. function OpenSSLHash($str) // 0.22
    134. {
    135. $hash = 0;
    136. $n = strlen($str);
    137.  
    138. for ($i = 0; $i <$n; $i++)
    139. {
    140. $hash ^= (ord($str[$i]) <<($i & 0x0f));
    141. }
    142. return $hash % 701819;
    143. }
    144.  
    145. function MD5Hash($str) // 0.050
    146. {
    147. $hash = md5($str);
    148. $hash = $hash[0] | ($hash[1] <<8 ) | ($hash[2] <<16) | ($hash[3] <<24) | ($hash[4] <<32) | ($hash[5] <<40) | ($hash[6] <<48) | ($hash[7] <<56);
    149. return $hash % 701819;
    150. }

     

    算法的一些说明:

    1. 函数后面注释中是我本地测试的执行1000次的速度(单位:s),可以看出来MD5Hash是最快的,而且要比其他函数快很多很多...但是从这个函数的算法也可以看出来,它仅仅是依赖于md5后字符串的前7个字符,也就是说如果前7个字符相同的话那么获得的hash值是完全一样的,所以实际来说它的分布情况是不太令人信任的....如果按照32个字符来计算的话速度那就远远的慢于其他算法了...
    2. 除了MD5Hash,其他算法都会受到字符串长度的影响,越长越慢,我测试用的是10个字符的英文。
    3. 每个函数最后的 return $hash % 701819; 中 701819 表示是哈希的最大容积,也就是说这些哈希函数最后得到的数字范围是0~701819,这个数字是可以改的一般认为使用一个大的质数结果的分布会是比较均匀的,在 701819 附近的几个建议的值是:175447, 350899, 1403641, 2807303, 5614657。

      或许你又问了,这个到底可以用来做什么呢...
      呵呵,我来解释一下我为什么要整理 and 测试这些哈希算法,我在写多用户 Blog,恩...之前的日志里面也有提过,多用户 Blog 一般都有一个功能,那就是使用一个英文和数字组合的用户名来作为 Blog 的地址(二级域名或者目录)。那么就有一个问题了,如何根据用户名来获取用户的 ID,多一次查询吗?有了哈希函数就不用了,使用哈希函数处理用户名,得到一个数字,再对数字做一定的处理(我是按照2位分割成层次的目录,目的是防止一个目录下有太多的文件而影响磁盘检索速度),然后就形成了一个路径,把对应的ID保存在这个路径下的文件内(我个人推荐用户名做文件名),这样就可以根据用户名来直接获得用户的ID,不需要查询,用户名做文件名,所以即使最后结果相同也是在不同的文件中,所以可以不用担心出现碰撞。

      当然...如果你的系统完全是根据用户名来操作那当我前面这些都没说 = =b,悄悄的非议一句 SELECT 也是数字比字符串要快一些地。

      我选择的是DJB算法,等以后上线后如果测试MD5分布还算可以接受的话再考虑换用。

      从这里也可以看出来其实哈希对于分布还是很有用地,呵呵,可以用来作缓存,静态或者其他需要分布存储的东西上面,这都要看你怎么用了。

    展开全文
  • 我想跟着大家一起重新学习下关于哈希一切——哈希、哈希函数、哈希表。这三者有什么样爱恨情仇?为什么Object类中需要有一个hashCode()方法?它跟equals()方法有什么关系?如何编写一个高性能哈希表?Java中...

    b6b9a8a003959db18c6a40faa2d61f78.png

    我想跟着大家一起重新学习下关于哈希的一切——哈希、哈希函数、哈希表。

    这三者有什么样的爱恨情仇?

    为什么Object类中需要有一个hashCode()方法?它跟equals()方法有什么关系?

    如何编写一个高性能的哈希表?

    Java中的HashMap中的红黑树可以使用其它数据结构替换吗?

    何为哈希?

    Hash,是指把任意长度的输入通过一定的算法变成固定长度的输出的过程,这个输出称作Hash值,或者Hash码,这个算法叫做Hash算法,或者Hash函数,这个过程我们一般就称作Hash,或者计算Hash,Hash翻译为中文有哈希、散列、杂凑等。

    9ea6927d709de6d704577db6cb14bc42.png

    既然是固定长度的输出,那就意味着输入是无限多的,输出是有限的,必然会出现不同的输入可能会得到相同的输出的情况,所以,Hash算法一般来说也是不可逆的。

    那么,Hash算法有哪些用途呢?

    哈希算法的用途

    哈希算法,是一种广义的算法,或者说是一种思想,它没有一个固定的公式,只要满足上面定义的算法,都可以称作Hash算法。

    通常来说,它具有以下用途:

    1. 加密密码,比如,使用MD5+盐的方式来加密密码;
    2. 快速查询,比如,哈希表的使用,通过哈希表能够快速查询元素;
    3. 数字签名,比如,系统间调用加上签名,可以防止篡改数据;
    4. 文件检验,比如,下载腾讯游戏的时候通常都有有一个MD5值,安装包下载下来之后计算出来一个MD5值与官方的MD5值进行对比,就可知道下载过程中有没有文件损坏,有没有被篡改等;

    好了,说起Hash算法,或者Hash函数,在Java中,所有对象的父类Object都有一个Hash函数,即hashCode()方法,为什么Object类中需要定义这么一个方法呢?

    严格来说,Hash算法和Hash函数还是有点区别的,相信你能根据语境进行区分。

    让我们来看看JDK源码的注释怎么说:

    8c86f35aabc9d6bbcbad61931023b407.png

    请看红框的部分,翻译一下大致为:为这个对象返回一个Hash值,它是为了更好地支持哈希表而存在的,比如HashMap。简单点说,这个方法就是给HashMap等哈希表使用的。

    // 默认返回的是对象的内部地址 
    public native int hashCode();

    此时,我们不得不提起Object类中的另一个方法——equals()。

    // 默认是直接比较两个对象的地址是否相等
    public boolean equals(Object obj) {
        return (this == obj);
    }

    hashCode()和equals又有怎样的纠缠呢?

    通常来说,hashCode()可以看作是一种弱比较,回归Hash的本质,将不同的输入映射到固定长度的输出,那么,就会出现以下几种情况:

    1. 输入相同,输出必然相同;
    2. 输入不同,输出可能相同,也可能不同;
    3. 输出相同,输入可能相同,也可能不同;
    4. 输出不同,输入必然不同;

    而equals()是严格比较两个对象是否相等的方法,所以,如果两个对象equals()为true,那么,它们的hashCode()一定要相等,如果不相等会怎样呢?

    如果equals()返回true,而hashCode()不相等,那么,试想将这两个对象作为HashMap的key,它们很大可能会定位到HashMap不同的槽中,此时就会出现一个HashMap中插入了两个相等的对象,这是不允许的,这也是为什么重写了equals()方法一定要重写hashCode()方法的原因。

    比如,String这个类,我们都知道它的equals()方法是比较两个字符串的内容是否相等,而不是两个字符串的地址,下面是它的equals()方法:

    public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

    所以,对于下面这两个字符串对象,使用equals()比较它们是相等的,而它们的内存地址并不相同:

    String a = new String("123");
    String b = new String("123");
    System.out.println(a.equals(b)); // true
    System.out.println(a == b); // false

    此时,如果不重写hashCode()方法,那么,a和b将返回不同的hash码,对于我们常常使用String作为HashMap的key将造成巨大的干扰,所以,String重写的hashCode()方法:

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
    
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

    这个算法也很简单,用公式来表示为:s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]。

    好了,既然这里屡次提到哈希表,那我们就来看看哈希表是如何一步步进化的。

    哈希表进化史

    数组

    讲哈希表之前,我们先来看看数据结构的鼻祖——数组。

    数组比较简单,我就不多说了,大家都会都懂,见下图。

    ae516c0ce7ee63621169d64624eda4b1.png

    数组的下标一般从0开始,依次往后存储元素,查找指定元素也是一样,只能从头(或从尾)依次查找元素。

    比如,要查找4这个元素,从头开始查找的话需要查找3次。

    早期的哈希表

    上面讲了数组的缺点,查找某个元素只能从头或者从尾依次查找元素,直到匹配为止,它的均衡时间复杂是O(n)。

    那么,利用数组有没有什么方法可以快速的查找元素呢?

    聪明的程序员哥哥们想到一种方法,通过哈希函数计算元素的值,用这个值确定元素在数组中的位置,这样时间复杂度就能缩短到O(1)了。

    比如,有5个元素分别为3、5、4、1,把它们放入到数组之前先通过哈希函数计算位置,精确放置,而不是像简单数组那样依次放置元素(基于索引而不是元素值来查找位置)。

    假如,这里申请的数组长度为8,我们可以造这么一个哈希函数为hash(x) = x % 8,那么最后的元素就变成了下图这样:

    508d5c593fed27a15b47dacb9de0866c.png

    这时候我们再查找4这个元素,先算一下它的hash值为hash(4) = 4 % 8 = 4,所以直接返回4号位置的元素就可以了。

    进化的哈希表

    事情看着挺完美,但是,来了一个元素13,要插入的哈希表中,算了一下它的hash值为hash(13) = 13 % 8 = 5,纳尼,它计算的位置也是5,可是5号已经被人先一步占领了,怎么办呢?

    这就是哈希冲突

    为什么会出现哈希冲突呢?

    因为我们申请的数组是有限长度的,把无限的数字映射到有限的数组上早晚会出现冲突,即多个元素映射到同一个位置上。

    好吧,既然出现了哈希冲突,那么我们就要解决它,必须干!

    How to?

    线性探测法

    既然5号位置已经有主了,那我元素13认怂,我往后挪一位,我到6号位置去,这就是线性探测法,当出现冲突的时候依次往后挪直到找到空位置为止。

    55b53551bf6b10082df647d4f88d51bd.png

    然鹅,又来了个新元素12,算得其hash值为hash(12) = 12 % 8 = 4,What?按照这种方式,要往后移3次到7号位置才有空位置,这就导致了插入元素的效率很低,查找也是一样的道理,先定位的4号位置,发现不是我要找的人,再接着往后移,直到找到7号位置为止。

    二次探测法

    使用线性探测法有个很大的弊端,冲突的元素往往会堆积在一起,比如,12号放到7号位置,再来个14号一样冲突,接着往后再数组结尾了,再从头开始放到0号位置,你会发现冲突的元素有聚集现象,这就很不利于查找了,同样不利于插入新的元素。

    这时候又有聪明的程序员哥哥提出了新的想法——二次探测法,当出现冲突时,我不是往后一位一位这样来找空位置,而是使用原来的hash值加上i的二次方来寻找,i依次从1,2,3…这样,直到找到空位置为止。

    还是以上面的为例,插入12号元素,过程是这样的,本文来源于公主号彤哥读源码:

    5ff07a7b6aace2b3b36b835de1e42194.png

    这样就能很快地找到空位置放置新元素,而且不会出现冲突元素堆积的现象。

    然鹅,又来了新元素20,你瞅瞅放哪?

    发现放哪都放不进去了。

    研究表明,使用二次探测法的哈希表,当放置的元素超过一半时,就会出现新元素找不到位置的情况。

    所以又引出一个新的概念——扩容。

    什么是扩容?

    已放置元素达到总容量的x%时,就需要扩容了,这个x%时又叫作扩容因子

    很显然,扩容因子越大越好,表明哈希表的空间利用率越高。

    所以,很遗憾,二次探测法无法满足我们的目标,扩容因子太小了,只有0.5,一半的空间都是浪费的。

    这时候又到了程序员哥哥们发挥他们聪明特性的时候了,经过996头脑风暴后,又想出了一种新的哈希表实现方式——链表法。

    链表法

    不就是解决冲突嘛!出现冲突我就不往数组中去放了,我用一个链表把同一个数组下标位置的元素连接起来,这样不就可以充分利用空间了嘛,啊哈哈哈哈~~

    bf3ae6eaf5f42b9c102de93e65bb9dd2.png

    嘿嘿嘿嘿,完美。

    真的完美嘛,我是一名黑客,我一直往里面放*%8=4的元素,然后你就会发现几乎所有的元素都跑到同一个链表中去了,呵呵,最后的结果就是你的哈希表退化成了链表,查询插入元素的效率都变成了O(n)。

    81f5ef3052357f88c3a2f53cb90d21fe.png

    此时,当然有办法,扩容因子干啥滴?

    比如扩容因子设置为1,当元素个数达到8个时,扩容成两倍,一半的元素还在4号位置,一半的元素去到了12号位置,能缓解哈希表的压力。

    然鹅,依旧不是很完美,也只是从一个链表变成两个链表,本文来源于公主号彤哥读源码。

    聪明的程序员哥哥们这次开启了一次长大9127的头脑风暴,终于搞出了一种新的结构——链表树法。

    链表树法

    虽然上面的扩容在元素个数比较少的时候能解决一部分问题,整体的查找插入效率也不会太低,因为元素个数少嘛。

    但是,黑客还在攻击,元素个数还在持续增加,当增加到一定程度的时候,总会导致查找插入效率特别低。

    所以,换个思路,既然链表的效率低,我把它升级一下,当链表长的时候升级成红黑树怎么样?

    嗯,我看行,说干就干。

    8fc3cb3bb05f3d354bdabe58d9f42036.png

    嗯,不错不错,妈妈再也不怕我遭到黑客攻击了,红黑树的查询效率为O(log n),比链表的O(n)要高不少。

    所以,到这就结束了吗?

    你想多了,每次扩容还是要移动一半的元素好么,一颗树分化成两颗树,这样真的好么好么好么?

    程序员哥哥们太难了,这次经过了12127的头脑风暴,终于想出个新玩意——一致性Hash。

    一致性Hash

    一致性Hash更多地是运用在分布式系统中,比如说Redis集群部署了四个节点,我们把所有的hash值定义为0~2^32个,每个节点上放置四分之一的元素。

    此处只为举例,实际Redis集群的原理是这样的,具体数值不是这样的。

    此时,假设需要给Redis增加一个节点,比如node5,放在node3和node4中间,这样只需要把node3到node4中间的元素从node4移动到node5上面就行了,其它的元素保持不变。

    这样,就增加了扩容的速度,而且影响的元素比较少,大部分请求几乎无感知。

    cd3340bac2a44614fa710ce90f6a5741.png

    好了,到这里关于哈希表的进化历史就讲到这里了,你有没有Get到呢?

    作者:彤哥读源码

    链接:https://www.imooc.com/article/310032

    展开全文
  • 你好,我是彤哥。上一节,我们一起学习了...本节,我想跟着大家一起重新学习下关于哈希一切——哈希、哈希函数、哈希表。这三者有什么样爱恨情仇?为什么Object类中需要有一个hashCode()方法?它跟equals()方法...
  • 字符串哈希 模板

    2019-10-07 18:47:53
    我的理解是将字符当作某一进制的数来看,这样相同的字符串就会有一样的值,不相同的字符串的值就不同。但值得注意的是这个进制必须大于128,而且为减少哈希冲突,需要构建不同的哈希函数。 记录下我学的在竞赛中比.....
  • 哈希函数

    2020-11-03 01:04:21
    哈希函数的输入域可以是非常大范围,比如,任意一个字符串,但是输出域是固定范围(一定位数bit),假设为S(虽然S可能会很大,但是和输入域没法比),并具有如下性质: 典型的哈希函数都有无限输入值域。 ...
  • 哈希表对字符串的高效处理

    万次阅读 2012-09-27 21:45:51
    哈希表对字符串的高效处理  哈希表(散列表)是一种非常高效查找数据结构,在原理上也与其他查找不尽相同,它回避了关键字之间反复比较繁琐,而是直接一步到位查找结果。当然,这也带来了记录之间没有任何...
  • 哈希处理字符串

    2018-10-18 13:17:37
    平时可能已经听到过哈希函数,而哈希更常用在通信中,哈希原理就是通过对信息进行不可逆向处理,并且如果两个信息哪怕只有一个位信息不同,那最终值也是截然不同两个答案。由于不可逆向性,所以只能从...
  • 字符串哈希

    2019-07-04 11:13:33
    在字符串hash方法中,对只有大写字母的字符串,它将字符串当做26进制的数字,然后将其转换为十进制,也就是下面的式子,其中str[i]表示的是字符串的i号位置,index函数将A~Z转换为0~25,H[I]表...
  • 哈希函数的一些知识

    2020-12-10 06:44:46
    输入可以为任意大小的字符串; 其产生固定大小的输出; 对于特定的输入字符串,能在合理时间计算出结果。对应n位的字符串,其哈希值计算的复杂度为O(n)。 要使哈希函数达到密码安全,需要附加以下三个特性:碰撞...
  • 字符串哈希1

    2021-01-26 07:33:25
    一、字符串哈希简介 Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度输入(又叫做预映射pre-image)通过散列算法变换成固定长度输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值...
  • 认识哈希函数

    2019-06-20 12:35:54
    哈希函数的输入域可以是非常大的范围,比如,一个字符串,但是它的输出域是固定的范围。并具有以下性质: 典型的哈希函数都有无限的输入值域。 当给哈希函数传入相同的输入值时,返回值一样。 当给哈希函数传入...
  • Python中MD5哈希与md5相关功能示例1:在Python中打印等效于MD5哈希的字节示例2:在Python中打印MD5哈希的十六进制等效项示例3:Python MD5文件校验输出与说明示例4:使用Python在MD5中编码字符串输出与说明示例5...
  • 密码学哈希函数

    千次阅读 2017-08-22 21:52:24
    输入可以为任意大小的字符串;其产生固定大小的输出;对于特定的输入字符串,能在合理时间计算出结果。对应n位的字符串,其哈希值计算的复杂度为O(n)。 要使哈希函数达到密码安全,需要附加以下三个特性:碰撞...
  • 哈希函数(散列函数),哈希函数的输入域可以是非常大的范围,比如任意一个字符串,但是输出域是固定的范围,假设为S,并具有如下性质: 1、典型的哈希函数都有无限的输入值域 2、当给哈希函数传入相同的输入值时...
  • 2.6 单向哈希函数单向哈希函数是一种字符串转换算法。由于转换后的字符串不能通过哈希值计算获得原字符...对于给定的字符串,计算出的哈希函数始终相同。这里给出几个MD5算法实例。 单向哈希函数值看似是随机ASCII...
  • 哈希匹配算法原理是采用一种哈希函数字符串映射成一个数字,之后就演化为两种方法: 第一种:假如数字相同,则去遍历匹配两串; 第二种:采用两种哈希函数,假如两组不同哈希映射后得到数字相同则判断为字符...
  • 【模板】 字符串哈希

    千次阅读 2017-08-16 14:41:33
    哈希(Hash)算法,即散列函数。它是一种单向密码体制,即它是一个从明文到密文不可逆映射,只有加密过程...因为要使字符串的哈希值各不相同,所以要取一些奇奇怪怪质数进行MOD,比如19260817(逃) 常见质数 1e9+7
  • 哈希表(散列表)是一种非常高效查找数据结构,在原理上也与其他查找不尽相同,它回避了关键字之间反复比较繁琐,而是直接一步到位查找结果。当然,这也带来了记录之间没有任何关联弊端。应该说,散列表对于...
  • 哈希函数又叫散列函数,哈希函数的输入域可以是非常大范围,比如任意字符串,但是输出域是固定范围,假设为s。 哈希函数的性质: 1. 典型的哈希函数都拥有无限输入值域。 2. 输入值相同时,返回值相同,通常...
  • 但也有区别:数组以数字索引,而哈希则是以名字索引,哈希的索引值称之为键(key),属于任意唯一的字符串哈希的键可以是任意唯一字符串;但是对应的值是可以重复的数字、字符串、undef、或这些类型的组合; 哈希...
  • 哈希表(散列表)是一种非常高效查找数据结构,在原理上也与其他查找不尽相同,它回避了关键字之间反复比较繁琐,而是直接一步到位查找结果。当然,这也带来了记录之间没有任何关联弊端。应该说,散列表对于...
  • 当时想的时候以为是字典树,但是具体的不知道该怎么做,后来看别人AC的代码才知道用简单的字符串哈希,或者其他的比如字母个数的限制条件优化一下就能过了,确实挺简单的,当时没有想到。写这题也没找什么字符串哈希...
  • 字符串Hash函数

    2015-07-19 11:29:18
    这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的...
  • 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。(两个单词包含相同的字母,但是次序不同) 输入: s = "anagram", t = "nagaram" 输出: true 输入: s = "rat", t = "car" 输出: false 2. ...
  • * 哈希函数将任意长度的二进制字符串映射为固定长度的小型二进制字符串。 * 加密哈希函数有这样一个属性:在计算上不大可能找到散列为相同的值的两个 * 不同的输入;也就是说,两组数据的哈希值仅在对应的数据...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 209
精华内容 83
关键字:

哈希函数相同的字符串