算法系列15天速成 第五天 五大经典查找【中】
|
哈希查找： 对的，他就是哈希查找，说到哈希，大家肯定要提到哈希函数，呵呵，这东西已经在我们脑子里面形成 固有思维了。大家一定要知道“哈希“中的对应关系。 比如说： ”5“是一个要保存的数，然后我丢给哈希函数，哈希函数给我返回一个”2"，那么此时的”5“ 和“2”就建立一种对应关系，这种关系就是所谓的“哈希关系”，在实际应用中也就形成了”2“是key，”5“是value。 那么有的朋友就会问如何做哈希，首先做哈希必须要遵守两点原则： ①: key尽可能的分散，也就是我丢一个“6”和“5”给你，你都返回一个“2”，那么这样的哈希函数不尽完美。 ②： 哈希函数尽可能的简单，也就是说丢一个“6”给你，你哈希函数要搞1小时才能给我，这样也是不好的。 其实常用的做哈希的手法有“五种”： 第一种：”直接定址法“。 很容易理解，key=Value+C； 这个“C"是常量。Value+C其实就是一个简单的哈希函数。 第二种：“除法取余法”。 很容易理解， key=value%C;解释同上。 第三种：“数字分析法”。 这种蛮有意思，比如有一组value1=112233，value2=112633，value3=119033， 针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是 key1=22,key2=26,key3=90。 第四种：“平方取中法”。此处忽略，见名识意。 第五种：“折叠法”。 这种蛮有意思,比如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160， 然后去掉高位“1”,此时key=60，哈哈，这就是他们的哈希关系，这样做的目的就是key与每一位value都相 关，来做到“散列地址”尽可能分散的目地。 正所谓常在河边走，哪有不湿鞋。哈希也一样，你哈希函数设计的再好，搞不好哪一次就撞楼了，那么抛给我们的问题 就是如果来解决“散列地址“的冲突。 其实解决冲突常用的手法也就2种： 第一种： “开放地址法“。 所谓”开放地址“，其实就是数组中未使用的地址。也就是说，在发生冲突的地方，后到的那个元素（可采用两种方式 :①线性探测，②函数探测）向数组后寻找"开放地址“然后把自己插进入。 第二种：”链接法“。 这个大家暂时不懂也没关系，我就先介绍一下原理，就是在每个元素上放一个”指针域“，在发生冲突的地方，后到的那 个元素将自己的数据域抛给冲突中的元素，此时冲突的地方就形成了一个链表。 上面啰嗦了那么多，也就是想让大家在”设计哈希“和”解决冲突“这两个方面提一点参考和手段。 那么下面就上代码了， 设计函数采用：”除法取余法“。 冲突方面采用:”开放地址线性探测法"。 复制代码 代码如下:
namespace HashSearch //原数据 //哈希表长度 static void Main(string[] args) Console.WriteLine("Hash数据：" + string.Join(",", hash)); while (true) （编辑：焦作站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
