英雄联盟投注,英雄联盟,英雄联盟下注,LOL投注官网,英雄联盟赛事投注,英雄联盟下注,英雄联盟电竞,英雄联盟投注网站,LOL,英雄联盟赛事,LOL投注,LOL赛事下注,LOL投注网站,lol下注平台
现代游戏内容越来越丰富，相应的资源规模也越来越庞大，在游戏运行时加载这些资源的所需的内存也会增加。对于拥有海量资源的游戏来说，仅仅是存储这些资源路径所需的内存都已经达到了数十兆。一种优化资源路径内存占用的方法是将路转换成hash，但同时也带来了Hash冲突，本文将讲述如何解决资源路径的Hash冲突。
使用Hash索引可以将路径的内存占用降低一个数量级。例如10万个资源，假设平均每个资源的路径长度为100个字符，在c#中，存储这些路径索引所需要的内存为(20+2*100)*100000 /1024/1024 = 20M,如果换成int32 hash值索引，那么所占用的内存为4*100000/1024/1024 = 0.38M。
将路径换成hash值，能有效的降低路径的内存占用，但也会引入一个新问题，当两个不同的路径映射到了相同的hash值，产生冲突。
Hash冲突的的本质是将k个资源路径通过hash算映射到hash值表达范围(0-n)，至少有两个资源被映射到同了一个hash值上。Hash冲突的概率等价于从n个数中有放回的取出k个数，取到相同数的概率。应用高中的数学可以得冲突的概率p为:
上述hash冲突概率是资源平均映射hash值域计算出来的，是比较理想的情况，实际项目中资源是否能平均映射到hash的值域呢？
我们随机取10万个资源路径，使用不同的算法计算出32位Hash值，然后将Int32范围内平均分成8个区间，统计每一个区间内hash值的数量的分布情况如下：
理论上分布在每一个区间的hash值平均数量是1.25万，可以看到三种算法的hash值在8个区间上分布比较均匀，概率分布基本符合理想的hash值均匀分布情况。
除了冲突概率外，另外一个值得考虑的因素是Hash算法的时间消耗，不过在资源加载的过程中hash值计算的时间消耗基本可以忽略不计，因此我们对此并未做深入的研究，这个网站上列出了多种不同hash算法运行效率的benchmark,可以看到，在输入的数据量很小的情况下，计算效率差距并不是很大。
一般情况下，在构建时都我们能提前计算出所有游戏资源的hash值，当检测到冲突时，可以通过更改资源路径名的方式来解决冲突，再重新打包。
另一种行方法是给路径加盐，当hash冲突时，比如 hash(A) 和 hash(B) 都是 H ，在文件索引表中，就不应该在 H 名下记录数据，而是记录一个冲突标记，并引用一个 salt ，然后，无论在打包阶段还是运行阶段，碰到 hash(A) 或 hash(B) 时，先查询到 H ，再重新计算一次 hash(A, salt) 或 hash(B,salt) ，这样就可以得到两个不一样的 hash 值了。如果有多于两个资源映射到同一个hash值，则执行多次加盐hash，直到没有冲突为止。Hash在加盐一次后冲突的概率为：
可见，加盐后可以有效的降低冲突的概率，当资源规模达100万个时，冲突概率仅为2%。
但加盐解重新计算Hash解决冲突的方式不能解决一个问题，即当构建时资源Hash值无冲突，但在运行时加载了一个不存在的资源与构建时的资源Hash冲突了，本来应该返回空，但会加载出一个错误的资源。这可以会导致出现一些奇怪的显示bug，比如一个英雄在释放技能时，他的技能特效里出现一个不相关的怪物模型，看起来很诡异。
另外可以通过将资源成几个大类型，不同的类型放到不同的Hash池里，也可以降低了冲突概率。但这要求我们在加载时能提前知道资源的类型，先按类型找到Hash池，再从池里查找到对应的资源。假设10万个资源Hash能平均的分到10个不同的池里，根据上面的公式(1)，可以将资源冲突的概率从68%降低到1.2%。但这样做也会遇到几个问题：
那使用64位的hash值能不能降低hash冲突的概率呢？ 根据公式(1),我们列出32位、32位加盐与64位及64位加盐冲突的概率：
我们可以看到，在20万个资源时，32位hash冲突概率已经接近100%，32位hash加盐的冲突概率为01.%，而64位hash冲突概率仅为0.0000001%，比被闪电击中的概率还要低100倍。就算资源规模达到千万级别，64位冲突概率仅为100万分之一，仍在一个比较安全的范围内。当资源规模达到10亿级别，64位hash冲突的概率是2.67%，而在加盐后的64位Hash冲突的概率为百亿分之一。当资源规模达到100亿级别时，64位hash冲突概率已经达93%，而在加盐后的64位Hash冲突的概率仅为千万分之一。
Hash冲突是一个不可忽视的问题，降低Hash冲突的概率有多种不同的方法，首次，将资源分类不同的Hash池，是一种简单有效的降低hash冲突的概率方式。其次，加盐也是降低Hash冲突的一种有效方法，但这种方法只能解决构建时静态资源的冲突（通常在构建时发现冲突，通过加盐或者改名处理），而不能解决查动态的运行时冲突（例如判断文件是否存在）。最后使用更大范围的hash值能更有效的降低hash冲突的概率，但也会消耗更多的内存和计算时间。在实践中，我们可以根据项目的资源的规模选择合适的Hash值范围（虽然前面只提到了32位与64位hash，但它们并不是唯一的选择，例如可以将64位Int的其中的48位作为Hash值，另外16位作为资源的类型）同时结合资源分类，加盐等多种方式来降低Hash冲突的概率。
