wordpress模板建站教程视频,wordpress5.1更新,陕西省城乡建设网站,合肥商业网站建设费用文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
1散列表的由来
从数组随机访问特性说起。 数组的随机访问特性是#xff1a;数组a,a[5]可以直接访问到数组的第6个元素。这就类似于在下标和数组对应的值之间建立…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
1散列表的由来
从数组随机访问特性说起。 数组的随机访问特性是数组a,a[5]可以直接访问到数组的第6个元素。这就类似于在下标和数组对应的值之间建立了映射关系。 散列表用的是数组支持按照下标随机访问数据的特性所以散列表其实就是数组的一种扩展由数组演化而来。没有数组就没有散列表。 应用在实践中。例如有100名学生每个学生有一个学号学号是从0到99数组score存放每个学生的成绩score[0]表示学号是0的学生的成绩score[1]表示学号是1的学生的成绩… 学号-数组下标-学生成绩。f1(学号)数组下标。 现在更进一步学号的规则是“年级班级数字”例如“50137”表示5年级1班37还是和上面的含义一样。那么我们就可以写函数把学号和数组下标映射起来查找学生成绩。依然是学号-数组下标-学生成绩。f2(学号)数组下标。f1与f2不同。 这里的学号就是key学生成绩是valuef1、f2是散列函数。散列函数计算得到的值是哈希值。
2散列函数
散列函数一般表示为hash(key) 散列函数的三点要求。 1 散列值是非负的。 2 如果key1key2那么hash(key1)hash(key2)。 3 如果key1̸key2key1\not key2key1̸key2,那么hash(key1)̸hash(key2)hash(key1)\nothash(key2)hash(key1)̸hash(key2)。
3散列冲突
定义 在实际中因为数组存储空间的限制要想做到key值不同的时候哈希值不同几乎很难满足。这个时候就产生了散列冲突也要哈希冲突。换句话说就是数组只有10个下标学生有5个人但学号是随机的怎么映射能够快速访问到学生成绩。
3.1开放寻址法
开放寻址法可以改变哈希值的解决方法 开放寻址法的核心思想是如果发生了散列冲突就重新找一个空闲位置插入数据。怎么找呢三种方法线性探测、平方探测、再哈希。
线性探测
如果hash(key)7且数组score[7]已经被占用那就探测8的位置是不是被占用9的位置是不是被占用0的位置是不是被占用…一直找到空闲位置。探测顺序是(hash(key)0)%size,(hash(key)1)%size,(hash(key)2)%size,(hash(key)3)%size…
平方探测
如果hash(key)7且数组score[7]已经被占用那就探测8的位置是不是被占用1的位置是不是被占用8的位置是不是被占用…一直找到空闲位置。探测顺序是(hash(key)0)%size,(hash(key)1)%size,(hash(key)4)%size,(hash(key)9)%size… 数组大小是有限的再探测的时候一定要对数组大小size取余。
再哈希
再哈希是指当发生冲突的时候再找一个散列函数计算探测空间是不是被占用如果被占用继续再找一个散列函数计算。 线性探测和平方探测其实是再哈希的特殊形式。再哈希的函数f(x)x,或者 f(x)x2f(x)x^2f(x)x2
查找 查找过程和插入过程类似。我们通过散列函数求出要查找元素key值的哈希值然后比较数组中下标为散列值的key和要查找的元素key值。如果相等则查找到否则继续探测查找直到数组中出现空闲位置。 我的思考:散列表中存储的是value值。例如最上面的例子学号就是数组下标的时候散列表就是数组存储的是学生成绩。当学号变成随机的时候散列表中存储的是学生实体。包含学号和学生成绩。查找的时候 比对的是key值是否相同。学号-哈希值-学生成绩。
删除操作
当需要删除数据的时候需要注意不能直接将数组的值置为空。因为在查找过程中出现空闲位置就停止不找了。这样查找就不准确了。可以将该位置放置删除标记。
3.2 链表法 所有哈希值相同的元素放在同一个槽(slot)或者链表内形成一个链表。 当插入的时候只需要计算插入元素key值的哈希值找到对应的slot添加到链表中即可。时间复杂度O(1)。 当查找或者删除的时候同样计算哈希值添加或者删除链表中的元素。时间复杂度与链表的长度k成正比所以是O(k)。所以更希望哈希值的分布式均匀的。
4散列函数与内存
4.1 散列函数的设计要求
散列函数需要满足
1 设计简单高效计算时间短。
2 生成的值要随机且均匀。数据分析法设计散列函数。例如学号复杂的例子我们分析学号的特征设计散列函数。 key为字符串类型的可以使用字符串进位相加的方法然后再跟散列表大小取余。例如nice的哈希值为
hash(nice)((n - a) * 26*26*26 (i - a)*26*26 (c - a)*26 (e-a)) / 78978
还有其他设计函数的方法。例如直接寻址法、平方取中法、随机数法等。
4.2动态装载因子
散列表中元素个数m与散列表长度的比值就是装在因子
装载因子元素个数长度装载因子\dfrac{元素个数}{长度}装载因子长度元素个数 散列表中随着数据的插入和删除状态因子发生变化成为动态装载因子。
4.3 扩容、缩容
当加载因子不断变大的时候发生散列冲突的概率就会增加操作就会变慢。这时候可以像动态数组一样做扩容。 一般散列表扩容会在在当前长度的基础上再扩一倍。扩容之前装载因子是0.8扩容之后就是0.4。散列表扩容与数组扩容不同的地方是扩容之后因为散列表大小发生变化散列值也可能发生变化。例如原来key6的元素哈希值是1扩容后哈希值是10。 支持动态扩容散列表的插入操作的平均时间复杂度按照摊还分析法是O1。 当散列表随着删除操作装载因子会越来越小。如果对内存不敏感浪费一些也可以可以不采取操作。如果要求内存尽可能小可以对散列表缩容。 装载因子需要权衡时间和空间。操作时间优先可以允许浪费一定的空间。
4.4避免低效扩容
低效扩容是因为一次扩容重新计算哈希值搬移数据导致的。如果原来的数据有1G大小这一次搬移操作就很费劲。 我们可以采集的策略是将原始n个数据的搬移工作分配到n次插入操作中。每次插入只将原来散列表中的一个值搬移到新散列表。这样在任何时候插入操作的时间复杂度都是O1。
5 如何选择冲突解决方法
开放寻址法 优点底层结构是数组可以充分利用CPU缓存加快查询速度;利于序列化。 缺点删除数据需要标记比较麻烦所有数据在同一个数组冲突的代价更大所以会浪费更多的内存空间。 当数据量比较小、装载因子比较小的时候选择开放寻址法。例如Java的ThreadLocalMap。
链表法 优点内存利用率比开放寻址法高因为节点可以在需要的时候才创建而不是提前创建。 可以容忍装载因子大于1。当装载因子大于1查找速度与每个槽对应的链表长度有关但是比全链表查询效果要高。我们可以将链表改为跳表或者红黑树这样即便出现散列冲突的极端情况时间复杂度也是O(logn)。 当数据对象比较大、数据量比较大的时候使用链表法。
6工业级散列表举例分析
6.1 Java的HashMap
1 初始大小16可以指定。 2 装载因子0.75当装载因子大于0.75的时候动态扩容。 3 冲突解决方法链表法。当链表长度超过8使用红黑树。 4 hash函数
int hash(Object key) {int h key.hashCode()return (h ^ (h 16)) (capitity -1); //capicity 表示散列表的大小
}
hashcode返回的是key的hash code。
6.2 工业级散列表应该具有的特征
1 支持快速查询、插入、删除 2 内存占用合理 3 性能稳定在极端情况下也不会出现速度不可接受的情况。
6.3 工业级散列表设计思路
1 散列函数设计合适。 2 装载因子设置合理不过多浪费空间动态扩容策略合适。 2 散列冲突解决策略。
7散列表的应用
7.1 word中错误单词提示功能
把英文单词加载到内存中用散列表存储。当用户输入一个词的时候在散列表中查找是否存在 常用因为单词20万假设单词平均长度10个字母。一个单词占用10个字节的内存所有单词加载大约是2M内存。放大10倍20M。内存可用。
7.2 假设有10条url访问记录怎么按照访问次数给url排序
对url取哈希值在散列表存储每个hash值的访问次数。最后再排序。
