安徽网站建设网站运营营销策划公司经营范围包括哪些

当前位置： 首页 > news >正文

安徽网站建设网站运营,营销策划公司经营范围包括哪些,wordpress技术类模板下载,seo关键词推广多少钱注#xff1a;本文同步发布于稀土掘金。 8 散列表查找#xff08;哈希表#xff09; 8.1 定义 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f#xff0c;使得每个关键字key对应一个存储位置f(key)。查找时#xff0c;根据这个确定的对应关系找到给…注本文同步发布于稀土掘金。 8 散列表查找哈希表 8.1 定义 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f使得每个关键字key对应一个存储位置f(key)。查找时根据这个确定的对应关系找到给定值key的映射f(key)若查找集合中存在这个记录则必定在f(key)的位置上。 这种对应关系f称为散列函数又称为哈希hash函数。采用散列技术将记录存储在一块连续的存储空间中这块连续存储空间称为散列表或哈希表Hash table关键字对应的记录存储位置称为散列地址。 散列技术既是一种存储方法也是一种查找方法与线性表、树、图等结构不同散列技术的记录之间不存在什么逻辑关系它只与关键字有关联因此散列主要是面向查找的存储结构。 散列技术最适合的求解问题是查找与给定值相等的记录。但散列技术不适用于有同样关键字的情况也不适合于范围查找。 设计一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题而另一个需要解决的问题是冲突——在理想情况下每一个关键字通过散列函数计算出来的地址都是不一样的但很多情况下会出现两个关键字key1key2但f(key1)f(key2)的情况这种现象称为冲突collisionkey1和key2称为这个散列函数的同义词synonym。 8.2 散列函数的构造方法 8.2.1 直接定址法 如果我们现在要对0~100岁的人口数字统计表那么我们对年龄这个关键字就可以直接用年龄的数字作为地址此时f(key)key 如果我们现在要统计的是80后出生年份的人口数那么我们对出生年份这个关键字可以用年份减去1980来作为地址此时f(key)key-1980 也就是说我们可以取关键字的某个线性函数值作为散列地址即 f ( k e y ) a ∗ k e y b f(key)a * key b f(key)a∗keyb   a 、 b 为常数 a、b为常数 a、b为常数 这样的散列函数优点就是简单、均匀也不会产生冲突但问题是这需要事先知道关键字的分布情况适合查找表较小且连续的情况。由于这样的限制在现实应用中此方法虽然简单但却并不常用。 8.2.2 数字分析法 如果关键字是位数较多的数字比如11位手机号“130xxx1234”其中前三位是接入号一般对应不同运营商公司的子品牌如130是联通如意通、136是移动神州行、153是电信等中间四位是HLR识别号表示用户号的归属地后四位才是真正的用户号 若现在要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前7位都是相同的因此选择后面的四位成为散列地址。 如果这样的抽取工作还是容易出现冲突问题还可以对抽取出来的数字再进行反转如1234改成4321、右环位移如1234改成4123、左环位移、甚至前现数与后两数叠加如1234改成123446等方法。 抽取方法是使用关键字的一部分来计算散列存储位置的方法这在散列函数中是常常用到的手段。 数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布比较均匀就可以考虑使用数字分析法。 8.2.3 平方取中法 假设关键字是1234那么它的平方就是1234*12341522756再抽取中间的3位就是227用做散列地址而如果关键字是4321那么它的平方就是18671041抽取中间的3位就可以是671也可以是710用做散列地址。 平方取中法比较适合于不知道关键字的分布而位数又不是很大的情况。 8.2.4 折叠法 折叠法是将关键字从左到右分割成位数相等的几部分注意最后一部分位数不够时可以短些然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。 比如关键字是9876543210散列表表长为3位那么它会被分成“987”、“654”、“321”、“0”四部分然后将它们叠加求和98765432101962然后根据散列表长3位取后3位即962作为散列地址。 如果还不能够保证分布均匀则可以对某些被分割成的部分进行反转再相加例如将“987”反转成“789”将“321”反转成“123”再相加78965412301566再取后3位为566。 折叠法事先不需要知道关键字的分布适合关键字位数较多的情况。 8.2.5 除留余数法 除留余数法是最常用的构造散列函数方法对于散列表长为m的散列函数公式为 \(f(key) key \mod p \)   ( p m ) (p m) (pm) 例如对一个有12个记录的数据我们取p11得到如下散列表 通常情况下若散列表长度为m则p一般定义为小于或等于m最好接近m的最小质数或不包含小于20质因子的合数。 8.2.6 随机数法 选择一个随机数取关键字的随机函数值为它的散列地址即 f ( k e y ) r a n d o m ( k e y ) f(key)random(key) f(key)random(key) 当关键字的长度不等时采用随机数法构造散列函数是比较合适的。 8.2.7 总结 上文描述的构造散列函数的方法如下所示 构造方法描述适用场景直接定址法f(key) a * key b a、b为常数事先知道关键字的分布情况表较小且连续的情况数学分析法观察数据找到数据中不重复或重复度较小的部分抽取出来直接作为散列函数或者将抽取出来的数字进行反转如1234改成4321、右环位移如1234改成4123、左环位移、甚至前现数与后两数叠加如1234改成123446等形成散列函数如取电话号码中代表真正用户号的后四位作为散列函数适合事先知道关键字的分布且关键字的若干位分布比较均匀且关键字位数比较大的情况平方取中法将关键字取平方然后取中间的散列表长度数量的数字作为散列函数例如假设关键字是1234那么它的平方就是123412341522756再抽取中间的3位就是227用做散列地址而如果关键字是4321那么它的平方就是18671041抽取中间的3位就可以是671也可以是710用做散列地址适合于不知道关键字的分布而位数又不是很大的情况折叠法将关键字从左到右分割成位数相等的几部分注意最后一部分位数不够时可以短些然后将这几部分叠加求和并按散列表表长取后几位作为散列地址比如关键字是9876543210散列表表长为3位那么它会被分成“987”、“654”、“321”、“0”四部分然后将它们叠加求和98765432101962然后根据散列表长3位取后3位即962作为散列地址事先不需要知道关键字的分布适合关键字位数较多的情况除留余数法f(key) key mod p   (p m)若散列表长度为m则p一般定义为小于或等于m最好接近m的最小质数或不包含小于20质因子的合数最常用的构建散列函数的方法随机数法f(key)random(key)当关键字的长度不等时采用随机数法构造散列函数是比较合适的 8.3 处理散列冲突的方法 8.3.1 开放定址法 所谓开放定址法就是一旦发生了冲突就去寻找下一个空的散列地址只要散列表足够大空的散列地址总能找到并将记录存入公式是 f i ( k e y ) ( f ( k e y ) d i ) m o d m f_i(key) (f(key) d_i) \mod m fi​(key)(f(key)di​)modm   ( d i 1 , 2 , 3…… , m − 1 ) (d_i1,2,3……,m-1) (di​1,2,3……,m−1) 例如关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}表长为m12因此公式是f(key) key mod 12。 对于关键字{12, 67, 56, 16, 25}f(key)都不会冲突因此直接插入 计算key37时发现f(37)37%121与25所在的位置冲突于是应用公式f(37)(f(37) d 1 d_1 d1​) mod 12(11)%122%122将37插入到地址2 计算key22时发现f(22)22%1210直接插入到地址10 计算key29时f(29)29%125插入到地址5 计算key15时f(15)15%123插入到地址3 计算key47时f(47)47%1211直接插入地址11 计算key48时f(48)48%120与12所在的位置冲突于是应用公式f(48)(f(48) d 2 d_2 d2​) mod 12(02)%122%122冲突应用公式f(48)(f(48) d 3 d_3 d3​) mod 12(23)%125%125冲突应用公式f(48)(f(48) d 4 d_4 d4​) mod 12(54)%128%129将48插入到地址9 计算key34时f(34)34%1210冲突应用公式f(34)(f(34) d 5 d_5 d5​) mod 12(105)%1215%123冲突应用公式f(34)(f(34) d 6 d_6 d6​) mod 12(36)%129%129冲突应用公式f(34)(f(34) d 7 d_7 d7​) mod 12(97)%1216%123冲突应用公式f(34)(f(34) d 8 d_8 d8​) mod 12(38)%1211%1211冲突应用公式f(34)(f(34) d 9 d_9 d9​) mod 12(119)%1220%128冲突应用公式f(34)(f(34) d 1 0 d_10 d1​0) mod 12(810)%1218%126插入到地址6 散列表插入结束。 代码实现比较简单 /** generate open addressing hash table** param array to insert array* return inserted array* author Korbin* date 2023-12-06 09:10:53/ public int[] openAddressing(int[] array) {if (null array || array.length 1) {return array;}int length array.length;int[] result new int[length];SetInteger usedAddressSet new HashSet();int data 1;for (int a : array) {int mod a % length;if (usedAddressSet.contains(mod)) {mod (mod data) % length;while (usedAddressSet.contains(mod)) {mod (mod data) % length;}}usedAddressSet.add(mod);result[mod] a;}return result; }8.3.2 再散列函数法 事先准备好除留余数法、直接定址法、数学分析法、平方取中法、折叠法等等在出现冲突时随机选择一个函数重新计算地址的方式称为再散列函数法。 8.3.3 链地址法 链地址法的实现是存储地址存储的是单链表当出现冲突时把冲突的关键字存储到链表中即可将所有关键字为同义词的记录存储在一个单链表中的表称为同义词表。 仍以关键字集合{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}为例。 对于关键字{12, 67, 56, 16, 25}f(key)都不会冲突因此直接插入 对于关键字37f(37)37%121与25所在的地址冲突因此将它作为25的后继结点 对于关键字22、29、15、47由于没有冲突直接插入 对于关键字48f(48)48%120与12所在的地址冲突因此将它作为12的后继结点 对于关键字34f(34)34%1210与22所在的地址冲突因此将它作为22的后继结点 插入结束。 单链表的结点定义在大话数据结构-线性表中已有描述链地址法的实现逻辑如下所示 /* generate link list addressing hash table** param array to insert array* return inserted array* author Korbin* date 2023-12-06 09:51:33/ SuppressWarnings(unchecked) public LinkListNodeInteger[] linkAddressing(int[] array) {if (null array || array.length 1) {return null;}int length array.length;LinkListNodeInteger firstNode new LinkListNode(array[0]);LinkListNodeInteger[] result (LinkListNodeInteger[]) Array.newInstance(firstNode.getClass(), length);for (int a : array) {int mod a % length;if (null ! result[mod]) {result[mod].setNext(new LinkListNode(a));} else {result[mod] new LinkListNode(a);}}return result; } 8.3.4 公共溢出区法 公共溢出区法即定义多个地址表当出现冲突时将冲突的关键字存储到溢出表中如下所示 可见公共溢出区法较适用于冲突较少的关键字存储若冲突较多则需要定义多个溢出表导致大量的存储浪费。 8.4 散列表查找实现 我们只针对开放定址法和链地址法两种散列表进行查找。 对于链地址法由于关键字存储在单链表中因此直接使用f(key)key%m在查找到的单链表中查询关键字是否存在即可若存在则返回f(key)否则返回-1表示未查找到。 对于开放定址法仍然先使用f(key)key%m进行定位若该地址上的关键字与要查询的关键字不同则令f(key)(f(key)1)%m继续进行查找但也不能无限查找下去因此使用count计数当整个地址表被查找过一次后停止查找。 /* find address of key** param addresses addresses* param key key to find address* return address of key* author Korbin* date 2023-12-06 10:24:18/ public int findAddress(LinkListNodeInteger[] addresses, int key) {if (null addresses || addresses.length 0) {return -1;}int length addresses.length;int mod key % length;LinkListNodeInteger address addresses[mod];while (null ! address) {if (address.getData() key) {return mod;}address address.getNext();}return -1; }/* find address of key** param addresses addresses* param key key to find address* return address of key* author Korbin* date 2023-12-06 10:18:19**/ public int findAddress(int[] addresses, int key) {if (null addresses || addresses.length 0) {return -1;}int length addresses.length;int mod key % length;int count 0;while (count 2) {if (addresses[mod] key) {return mod;}mod (mod 1) % length;if (mod 0) {// iterate from mod to mod - 1count;}}return -1; }