- 浏览: 984250 次
- 性别:
- 来自: 杭州
文章分类
- 全部博客 (826)
- 硬件 (8)
- 软件 (24)
- 软件工程 (34)
- JAVA (229)
- C/C++/C# (77)
- JavaScript (8)
- PHP (1)
- Ruby (3)
- MySQL (14)
- 数据库 (19)
- 心情记事 (12)
- 团队管理 (19)
- Hadoop (1)
- spring (22)
- mybatis(ibatis) (7)
- tomcat (16)
- velocity (0)
- 系统架构 (6)
- JMX (8)
- proxool (1)
- 开发工具 (16)
- python (10)
- JVM (27)
- servlet (5)
- JMS (26)
- ant (2)
- 设计模式 (5)
- 智力题 (2)
- 面试题收集 (1)
- 孙子兵法 (16)
- 测试 (1)
- 数据结构 (7)
- 算法 (22)
- Android (11)
- 汽车驾驶 (1)
- lucene (1)
- memcache (12)
- 技术架构 (7)
- OTP-Erlang (7)
- memcached (17)
- redis (20)
- 浏览器插件 (3)
- sqlite (3)
- Heritrix (9)
- Java线程 (1)
- scala (0)
- Mina (6)
- 汇编 (2)
- Netty (15)
- libevent (0)
- CentOS (12)
- mongod (5)
- mac os (0)
最新评论
-
kingasdfg:
你这里面存在一个错误添加多个任务 应该是这样的 /** * ...
Quartz的任务的临时启动和暂停和恢复【转】 -
kyzeng:
纠正一个错误,long型对应的符号是J,不是L。
Jni中C++和Java的参数传递 -
zhaohaolin:
抱歉,兄弟,只是留下作记录,方便学习,如果觉得资料不好,可以到 ...
netty的个人使用心得【转】 -
cccoooccooco:
谢谢!自己一直以为虚机得使用网线才可以与主机连接呢。。
主机网卡无网线连接与虚拟机通信 -
yuqilin001:
要转别人的东西,请转清楚点嘛,少了这么多类,误人子弟
netty的个人使用心得【转】
先提一个简单的问题,如果有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做? 有一个方法最简单,老老实实从头查到尾,一个一个比较,直到找到为止,我想只要学过程序设计的人都能把这样一个程序作出来,但要是有程序员把这样的程序交给用户,我只能用无语来评价,或许它真的能工作,但...也只能如此了。 最合适的算法自然是使用HashTable(哈希表),先介绍介绍其中的基本知识,所谓Hash,一般是一个整数,通过某种算法,可以把一个字符串"压缩" 成一个整数,这个数称为Hash,当然,无论如何,一个32位整数是无法对应回一个字符串的,但在程序中,两个字符串计算出的Hash值相等的可能非常小,下面看看在MPQ中的Hash算法 unsigned long HashString(char *lpszFileName, unsigned long dwHashType) while(*key != 0) seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2); Blizzard的这个算法是非常高效的,被称为"One-Way Hash",举个例子,字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。 if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString)) 看到此,我想大家都在想一个很严重的问题:"如果两个字符串在哈希表中对应的位置相同怎么办?",毕竟一个数组容量是有限的,这种可能性很大。解决该问题的方法很多,我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝,我遇到的很多算法都可以转化成链表来解决,只要在哈希表的每个入口挂一个链表,保存所有对应的字符串就OK了。 事情到此似乎有了完美的结局,如果是把问题独自交给我解决,此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是:他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。 中国有句古话"再一再二不能再三再四",看来Blizzard也深得此话的精髓,如果说两个不同的字符串经过一个哈希算法得到的入口点一致有可能,但用三个不同的哈希算法算出的入口点都一致,那几乎可以肯定是不可能的事了,这个几率是1:18889465931478580854784,大概是10的 22.3次方分之一,对一个游戏程序来说足够安全了。 现在再回到数据结构上,Blizzard使用的哈希表没有使用链表,而采用"顺延"的方式来解决问题,看看这个算法: while (lpTable[nHashPos].bExists) return -1; //Error value 1. 计算出字符串的三个哈希值(一个用来确定位置,另外两个用来校验)
{
unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;
{
ch = toupper(*key++);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
return seed1;
}
是不是把第一个算法改进一下,改成逐个比较字符串的Hash值就可以了呢,答案是,远远不够,要想得到最快的算法,就不能进行逐个的比较,通常是构造一个哈希表(Hash Table)来解决问题,哈希表是一个大数组,这个数组的容量根据程序的要求来定义,例如1024,每一个Hash值通过取模运算 (mod)对应到数组中的一个位置,这样,只要比较这个字符串的哈希值对应的位置又没有被占用,就可以得到最后的结果了,想想这是什么速度?是的,是最快的O(1),现在仔细看看这个算法吧
int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
{
int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;
return nHashPos;
else
return -1; //Error value
}
int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
{
const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
int nHash = HashString(lpszString, HASH_OFFSET);
int nHashA = HashString(lpszString, HASH_A);
int nHashB = HashString(lpszString, HASH_B);
int nHashStart = nHash % nTableSize, nHashPos = nHashStart;
{
if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
return nHashPos;
else
nHashPos = (nHashPos + 1) % nTableSize;
if (nHashPos == nHashStart)
break;
}
}
2. 察看哈希表中的这个位置
3. 哈希表中这个位置为空吗?如果为空,则肯定该字符串不存在,返回
4. 如果存在,则检查其他两个哈希值是否也匹配,如果匹配,则表示找到了该字符串,返回
5. 移到下一个位置,如果已经越界,则表示没有找到,返回
6. 看看是不是又回到了原来的位置,如果是,则返回没找到
7. 回到3
Blizzard被称为最卓越的游戏制作公司,不愧于此。
http://blog.blogchina.com/article_85296.361466.html
发表评论
-
一致性 hash 算法( consistent hashing )<转>
2013-05-23 23:53 830consistent hashing 算法早在 1997 年 ... -
【转】几种经典的hash算法
2013-05-23 23:51 3449文章出处:http://hunteagl ... -
常用hash算法及评测[转]
2013-05-23 23:27 1059RS hash 算法 unsigned int RSHas ... -
在Linux上开发网络服务器的一些相关细节:poll与epoll(转)
2011-05-04 16:23 1083随 ... -
Hash算法大全(java实现)【转】
2011-04-16 13:40 1022Hash算法有很多很多种类。具体的可以参考之前我写的Hash算 ... -
打造最快的Hash表[转]
2011-04-16 00:58 783打造最快的Hash表(暴雪用的MPQ文件) ... -
哈希算法(Hash Algorithm)初探[转载]
2011-04-16 00:35 1118不约而同的,几乎所有的流行的hash map都采用了DJB h ... -
暴雪的哈希算法 - [转载]
2011-04-16 00:28 835暴雪公司有个经典的字 ... -
哈希算法
2011-04-15 23:37 898哈希算法将任意长度的 ... -
三种简单排序算法及其对比
2011-04-01 13:32 855三种简单排序算法及其对比 代码: class ... -
递归算法
2011-04-01 13:28 971用三角数字问题说明递归 Int triangle(int ... -
高级排序
2011-04-01 13:27 770希尔排序: 插入排序的缺点是复制的次数太多,如果数据开始 ... -
冒泡排序算法的JAVA实现
2011-04-01 13:25 697package Utils.Sort; ... -
常用的各种排序算法的JAVA实现
2011-04-01 13:24 821用JAVA把《Data Structure a ... -
快速排序算法的JAVA实现
2011-04-01 13:23 697package Utils.Sort; / ... -
希尔排序算法的JAVA实现
2011-04-01 13:21 809package Utils.Sort; / ... -
插入排序算法的JAVA实现
2011-04-01 13:21 1036package Utils.Sort; / ... -
选择排序算法的JAVA实现
2011-04-01 13:19 681package Utils.Sort; / ... -
归并排序算法的JAVA实现
2011-04-01 13:18 808package Utils.Sort; / ... -
二分查找算法分析实现
2011-04-01 13:01 1236二分查找又称折半查找,它是一种效率较高的查找方法。 ...
相关推荐
高手打造最快的Hash表源码(和Blizzard的对话)
打造最快的Hash表(和Blizzard的对话)
这是传说中异常强悍的暴雪公司研究的哈希算法,采用三个哈希表来防止冲突,代码简练自成一体,无论是思想还是代码风格都非常值得大家学习!
是不是把第一个算法改进一下,改成逐个比较字符串的Hash值就可以了呢,答案是,远远不够,要想得到最快的算法,就不能进行逐个的比较,通常是构造一个哈希表(Hash Table)来解决问题,哈希表是一个大数组,这个数组的...
C++小游戏 Blizzard (VisualCPP代码作业)C++小游戏 Blizzard (VisualCPP代码作业)C++小游戏 Blizzard (VisualCPP代码作业)C++小游戏 Blizzard (VisualCPP代码作业)C++小游戏 Blizzard (VisualCPP代码作业)C++小游戏 ...
比 PL.SQL.Developer.v5.1.6.747 好注册机
VC++渲染生成雪花效果,学习游戏和渲染图像时候觉得比较有用,更多实现原理与细节请需要者下载源码查看。
改进的BlizzardUI:对Blizzard UI的常规改进
Blizzard rat 1.2 for windows only
Veritas Backup Exec v9.0 by Blizzard 算号器
Api-blizzard.js.zip,暴雪战网社区平台apiblizzard.js的基于promise的node.js库,一个api可以被认为是多个软件设备之间通信的指导手册。例如,api可用于web应用程序之间的数据库通信。通过提取实现并将数据放弃到对象...
seo-for-wordpress-blogs-blizzard-internet-marketing 原著
blizzard_hash_for_android降低暴雪哈希的内存消耗(理论上牺牲碰撞率),千万量级别以内的数据,碰撞率和内存消耗都优与bloom filternode 结点存放两个属性:1)nHashA, nHashA取byte的前7位(1~127),用以存储Hash...
暴雪测试用例包含用于测试 Blizzard Item API 和 Item Set API 的驱动程序和测试用例
暴风雪 作为Ring中间件提供的Flake ID生成服务。... 在独立或中间件用例中,Ring应用程序都将提供/ flake和/ flake /:n这两个路由,分别生成一个薄片和N个薄片。 消费者 请注意,暴风雪会产生以编码的响应。
:snowflake: 暴雪前端该项目包含暴雪应用程序的主要功能。 如果您想贡献,请参考该项目的。
暴风雪 象棋引擎。 很冷。 Heatwave的潜在前身。
Blizzard.js Blizzard.js是... 暗黑破坏神3 : d3 炉石: hs 星际争霸2 : sc2 魔兽世界(零售) : wow 魔兽世界(经典) : wow.classic 带有TypeScript和ES模块import { wow } from 'blizzard.js'const wowClient =
但是仍然会跟踪拉取请求和出现的问题。 目前,我没有重新访问它的计划,但我可能会在将来的某个时间回来并正确更新它。初学者友好由于我也是开源项目的新手,因此我希望尽可能使该项目对初学者友好。 不要害怕尝试...
暴风雪哇经典API 暴雪WOW经典API的实现