企业官网建设流程全解析

现代锦州网站建设,宣传推广方式有哪些,做网站除了有服务器还需要什么软件,ui设计的定义使用链地址法#xff08;拉链法#xff09;解决哈希冲突时#xff0c;每个哈希地址对应一个链表#xff0c;所有哈希到该地址的关键字按链表形式存储。下面以题目给出的参数进行详细构造和分析。 1. 链地址法构造哈希表 哈希表长度#xff1a;11#xff08;地址从 0 到 …使用链地址法拉链法解决哈希冲突时每个哈希地址对应一个链表所有哈希到该地址的关键字按链表形式存储。下面以题目给出的参数进行详细构造和分析。1. 链地址法构造哈希表哈希表长度11地址从 0 到 10哈希函数H(key) key mod 11关键字序列47, 34, 13, 12, 52, 38, 33, 27, 3逐个计算哈希地址并插入keyH(key) key mod 11插入位置链表4747 mod 11 3地址 33434 mod 11 1地址 11313 mod 11 2地址 21212 mod 11 1地址 1 → 冲突链入 34 后5252 mod 11 8地址 83838 mod 11 5地址 53333 mod 11 0地址 02727 mod 11 5地址 5 → 冲突链入 38 后33 mod 11 3地址 3 → 冲突链入 47 后最终哈希表结构如下链表顺序为插入顺序地址 0: [33] 地址 1: [34] → [12] 地址 2: [13] 地址 3: [47] → [3] 地址 4: 空 地址 5: [38] → [27] 地址 6: 空 地址 7: 空 地址 8: [52] 地址 9: 空 地址10: 空2. 成功查找的平均查找长度ASL成功查找对每个元素查找时需比较的次数等于其在链表中的位置从头开始比较。地址 0: 33 → 1 次比较地址 1: 34第1个→ 1 次12第2个→ 2 次地址 2: 13 → 1 次地址 3: 47第1个→ 1 次3第2个→ 2 次地址 5: 38第1个→ 1 次27第2个→ 2 次地址 8: 52 → 1 次统计1 次比较的元素33, 34, 13, 47, 38, 52 → 共 6 个2 次比较的元素12, 27, 3 → 共 3 个总比较次数 6×1 3×2 6 6 12元素总数 9因此ASL 12 / 9 ≈1.33注原题中写 ASL ≈ 1.34 可能是四舍五入误差正确值为 1.33即 4/33. 其他哈希冲突解决方法再哈希法双重哈希冲突时使用另一个哈希函数重新计算地址如H_i (H1(key) i×H2(key)) mod table_size直到找到空位。✅ 优点减少聚集现象尤其是线性探测导致的“堆积”❌ 缺点计算开销大需多个哈希函数公共溢出区法设主表和一个溢出表如数组或链表主表存放无冲突元素冲突元素统一放入溢出区。查找时先查主表若冲突则查溢出区。✅ 优点结构清晰便于管理❌ 缺点溢出区可能变慢查找效率下降4. 哈希表的查找特点必须使用与插入时相同的哈希函数和冲突处理策略来定位地址。实际查找过程中仍需进行关键字比较因为哈希值相同不一定关键字相同。查找效率用平均查找长度ASL衡量。影响因素哈希函数的好坏是否均匀分布冲突处理方法链地址 vs 开放寻址装填因子 α 元素个数 / 表长α 越小冲突越少性能越好使用开放地址法中的线性探测Linear Probing处理哈希冲突时当发生冲突会顺序向后查找下一个空闲位置直到找到空槽为止。其基本公式为H_i(key) (H(key) i) mod m其中H(key) key mod m是初始哈希值i 0, 1, 2, ..., m-1是探测次数m是哈希表长度本例中为 11 参数回顾哈希表长度11地址 0 ~ 10哈希函数H(key) key mod 11关键字序列47, 34, 13, 12, 52, 38, 33, 27, 3我们逐个插入并在线性探测下解决冲突。 插入过程详解keyH(key)探测过程最终位置说明4747 mod 11 3地址 3 空 → 插入3成功3434 mod 11 1地址 1 空 → 插入1成功1313 mod 11 2地址 2 空 → 插入2成功1212 mod 11 1地址 1 已被占 → 检查 2 → 被占 → 检查 3 → 被占 → 检查 44探测 i3: (13)4空插入5252 mod 11 8地址 8 空 → 插入8成功3838 mod 11 5地址 5 空 → 插入5成功3333 mod 11 0地址 0 空 → 插入0成功2727 mod 11 5地址 5 占 → 6 空是 → 插入6探测 i1: (51)633 mod 11 3地址 3 占 → 4 占12→ 5 占 → 6 占27→ 7 空 → 插入7探测 i4: (34)7✅ 构造完成后的哈希表索引 0~10地址012345678910内容33341347123827352空空 成功查找的平均查找长度ASL每次查找从初始地址开始探测直到找到目标元素比较次数 探测次数 1每探一次算一次比较key初始地址实际位置探测步数i比较次数4733013411011322011214从1→2→3→4第3步成功4检查1,2,3,45288013855013300012756第1次探测成功5→62337从3→4→5→6→7共4步5注意线性探测中“比较次数”是指在查找路径上逐个比对关键字的次数。总比较次数 111411125 17元素个数 9 ASL 17 / 9 ≈1.89⚠️ 特点与问题优点实现简单缓存友好连续访问内存缺点容易产生“聚集现象”如地址1~4连续被占形成“主集团”插入和查找效率随装填因子升高急剧下降删除操作复杂不能直接清空需标记为“已删除”