企业官网建设流程全解析

•前言哈希表别名 散序表哈希表可以理解 “加强的数组”数组利用下标可以在 O1的时间复杂度情况下实现查找哈希表则可以 利用 “key” 查找到其 对应的 “value”值“key”可以是 数字、字符串等等。•核心原理•“key”通俗来讲 就是像你存东西时用的“编号”或“标签”通过它能快速找到你存的那个“值”。key是唯一的类比于数组来理解 数组中每一个索引都是唯一的key类似于数组中的下标 是唯一的但是数组的数据无人在意 注意 key 和 数组下标还是有一定差别的有什么差别请往下看• 哈希函数作用就是把 任意长度输入的 “key” 转换 成固定长度的 下标数组下标增删改查的时候都会调用到 “哈希函数”因此哈希函数的设计 影响了性能注意 哈希函数要保证 输入同一个 key 输出的 下标也是同一个 下标同一个key 对应 一个 同一个下标。 ps 不同key可能会出现得到同一个下标的情况那么哈希函数是如何保证索引的合法性的呢正常来说 哈希函数返回的数 是int类型 int 类型 的 最小数是-2^31 但是 最大数却是2^31 - 1那么-h 2^31就会超出 int 类型的最大值这叫做整型溢出因此我们不能直接对 负数直接取反///假设h是哈希函数计算得出的数h h 0x7fffffff// 0x7fffffff 的 二进制表示 是01111111 11111111 11111111 11111111共 31 个 1最高位为 0// 按位与 是 两个都为1 结果为1否则结果为0 所以首位结果会取反为0代表为正h h % table.size() // table.size() 代表表的长度这里利用取余的思想对取余有疑问的读者 可以看看这一篇文章从零开始的数据结构学习-----环形数组-CSDN博客•哈希函数储存的两种常见方法1. 直接定址法 适用于关键字连续的情况2.除留余数法 求余操作可以把 不连续的关键字 映射到连续的地址空间里面H(key) key % p (p 自己定一般取 小于等于 表长的最大质数)•哈希冲突在哈希函数将 key转换成 下表的时候 可能会出现 两个 或者 多个 不相同的 key得到同一个下标的情况那么这个issue被称为 “哈希冲突”。• 解决哈希冲突的两种方法1.拉链法纵向储存重复的 value哈希表不直接储存一个 value 元素每一个节点 都是 一条单链表的头节点2.开放寻址法 / 线性寻址法 本质上横向储存如果一个格子满了就找下一个格子直到找到空格子。• 负载因子和扩容频繁出现哈希冲突有主要两个原因1. 哈希函数设计效果差使得要么key映射的 value 分配不均衡 要么 多个key 的映射 到 同一个下标上2. 哈希表中已经装了 很多 key_elem。 这种情况下即使 哈希表设计得再完美也无法避免哈希冲突。第一个问题我们可以踩在巨人的肩膀上选择调用 “标准库”对于第二种情况引出了我们本节要讲的东西-------“负载因子”负载因子是一个比较哈希表装满程度的度量负载因子越大那么哈希表装得越满那么发生哈希冲突的概率越大。负载因子计算公式 size / table.size这里的size指的是哈希表中 key--elem映射的对数table.size是哈希表底层数组的容量负载因子默认定义是0.75当哈希表内元素靠近负载因子那么就会触发扩容操作----跟动态数组的原理相同从零开始的数据结构学习----数组-CSDN博客----数组容量扩大把旧的数据搬到新的空间里面size不变table.szie()扩大负载因子自然就缩小了•哈希表中key的遍历是无序的原本哈希函数把key映射到数组中本来就是随机的再扩容之后table.size()会发生变化此时就要重新把key映射到数组中这个时候key对应的下标可能会发生变化此时遍历的结果就会与之前发生变化。