号码算法 关于快速查找与匹配(4)

但是随之而来的是第二个问题：冲突

即关键字的值集中在某一较小区间内，（依据散列函数而定），有可能使不同的键值得到相同的哈希值（例如体校，可能百分之九十的人都身高一米八），这时候会导致查找时可能找到不正确的元素，例如7-16，我们从实际入手，号的意义为1,2位为省，自治区直辖市代码，3,4位为地级市，5,6位为县级代码，7~14位为出生年月日，15~17位为顺序号，最后一位为校验码，那么我们可以得出如下结论（数学证明部分略去不计，数字分析法），可以发现若人员集中在某一地区，或出生年月为某一时间段内，会导致1~14位的数字分布不均匀，较容易产生冲突，这时我们就容易联想到最后几位顺序码，该字段的冲突概率最低，那么我们不妨就取号的最后数位作为键值，并进行散列处理，当然这只是其中一种方式，也是最简单的方式，你仍可以在号中任取数位作为键值（前提是不相邻的数位），依实际情况而定。

实际上在散列中，冲突是大概率事件，那么较为直接有效的方式就是拉链法，即我们得到相同函数值时，不直接将其存储在对应地址，而是在该地址的基础上，向下延伸（用链式存储），这样我们就解决了不同元素抢占地址的问题，在查找时，我们先得到该地址（缩小范围），再向下查找，直到得到要查找的值（或未找到），当然这种方式也有弊端，即堆积问题，若大多数数据的函数值都集中在该地址上，则其查找效率有可能退化为顺序查找的效率，这时我们可以考虑使用哈希树，在此就不过多展开，拉链法对于这两道例题已经足够。

对于散列的讨论就先到这里，其他的一些常用的查找方式刚才也提到过，例如二分查找，插值搜索等，这些方法会在有较好的例题时拿来分析，关于方法的选择，并没有最优，只有相对最优（主要还是依据数据规模以及类型而定），这次先到这里，若有问题，还望指正。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-86698-4.html