北京做网站建设公司哪家好,杭州企业云网站建设,网站建设 ppt,公司网页监控先看数组存储数据是怎么样的。
现在有一个数组#xff0c;它里面每个单元存储的是数据的地址
这叫指针数组吧#xff0c;假设它有100个单元
我们称他为p[100]
现在我想把一百个数据#xff08;地址#xff09;放到里面
我们想把某个数据放到p的第几个单元完全是由
我…先看数组存储数据是怎么样的。
现在有一个数组它里面每个单元存储的是数据的地址
这叫指针数组吧假设它有100个单元
我们称他为p[100]
现在我想把一百个数据地址放到里面
我们想把某个数据放到p的第几个单元完全是由
我们决定的可以说想怎么放就怎么放
是一种乱放既然是乱放那么查找起来就比较耗时。 哈希表是怎么存储数据的呢
哈希表同样是一个指针数组。
同样需要存储100个数据需要的就不是100个单元了因为哈希表要把某个数据存放在某个单元不是随机的一个过程而是算出来的这个算法叫哈希函数
比如要存储一个数据对
张三 1882356
李四 23456789
王五 58856456
张三经过哈希函数算出来的值是138那么哈希表最少需要138个单元因为张三对应的数据1882356要存储在指针数组的p[138]的位置上。
李四经过哈希函数算出来的值是500那么2356789这个数据就要存放在p[500]这个位置上。
所以你明白了数据的地址放在指针数组的哪个单元格是算出来的是有迹可寻的并不是想放在哪里就放在哪里
那查找的时候就好查找了你要查找张三对应的数据
直接把张三用哈希函数算一下得到138哦 张三的数据就在p[138]这个位置上所以一下就找到了。 哈希表是一个key- value的数据对p是一个指针数组用来存放value的地址那么key和value的关系是下面这样的。
p[f(key)]value 可以看出哈希表有时候会浪费很大空间的比如上面张三 李四 王五那个例子 如果按照哈希表存储要定义一个500个大小的指针数组。怎么解决这个问题呢我再看看书。 HASH的理性认识
8/03 为什么会有哈希表人们存储数据时想找到一种查找插入和删除、更新复杂度都不是很大的方法于是哈希表应运而生。 数组存储空间是连续的占用内存严重占用空间很大但数组的二分查找时间复杂度小。 寻址容易插入和删除困难。 链表存储区间离散占用内存小空间复杂度小但是时间复杂度很大。 寻址困难插入和删除容易。 哈希表 寻址容易 插入和删除也容易的数据结构
hash table的实现最常用的是拉链法可以理解为“链表的数组 从上图我们可以发现哈希表是由数组链表组成的一个长度为16的数组中每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中12%1612,28%1612,108%1612,140%1612。所以12、28、108以及140都存储在数组下标为12的位置。
HashMap的存取 HashMap的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下HashMap存数据的基本流程 1、 当调用put(key,value)时首先获取key的hashcodeint hash key.hashCode(); 2、 再把hash通过一下运算得到一个int h.
hash ^ (hash 20) ^ (hash 12); // 是无符号的右移运算 高位直接补零低位移除。表示带符号的右移运算 高位如果符号位为正补零符号位负补一低位直接移除
hash hash ^ (hash 20) ^ (hash 12) ^代表异或运算
int h hash ^ (hash 7) ^ (hash 4);
为什么要经过这样的运算呢这就是HashMap的高明之处。先看个例子一个十进制数32768(二进制1000 0000 0000 0000)经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗或许这样还看不出什么再举个数字61440(二进制1111 0000 0000 0000)运算结果是65263(二进制1111 1110 1110 1111)现在应该很明显了它的目的是让“1”变的均匀一点散列的本意就是要尽量均匀分布。那这样有什么意义呢看第3步。 3、 得到h之后把h与HashMap的承载量HashMap的默认承载量length是16可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。进行逻辑与运算即 h (length-1)这样得到的结果就是一个比length小的正数我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index这是HashTable的改进HashTable中的算法只是把key的 hashcode与length相除取余即hash % length这样有可能会造成index分布不均匀。还有一点需要说明HashMap的键可以为null它的值是放在数组的第一个位置。 4、 我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素这个元素是HashMap内部定义的一个类Entity 基本结构它包含三个类keyvalue和指向下一个Entity的next,没有的话就创建一个EntityK,V对象在 table[index]位置上插入这样插入结束如果有的话通过链表的遍历方式去逐个遍历看看有没有已经存在的key有的话用新的value替 换老的value如果没有则在table[index]插入该Entity把原来在table[index]位置上的Entity赋值给新的 Entity的next这样插入结束。
大学学过记忆最深刻的是除留余数发
假设哈希表长为mp为小于等于m的最大素数则哈希函数为
hkk % p 其中%为模p取余运算。
例如已知待散列元素为18756043549046表长m10p7则有 h(18)18 % 74 h(75)75 % 75 h(60)60 % 74 h(43)43 % 71 h(54)54 % 75 h(90)90 % 76 h(46)46 % 74
此时冲突较多。为减少冲突可取较大的m值和p值如mp13结果如下 h(18)18 % 135 h(75)75 % 1310 h(60)60 % 138 h(43)43 % 134 h(54)54 % 132 h(90)90 % 1312 h(46)46 % 137 解决hash冲突的办法
最常用的方法链地址法
我们先复习数据结构里的一个知识点在一个长度为n假设是10000的线性表假设是ArrayList里存放着无序的数字如果我们要找一个指定的数字就不得不通过从头到尾依次遍历来查找这样的平均查找次数是n除以2这里是5000。
我们再来观察Hash表这里的Hash表纯粹是数据结构上的概念和Java无关。它的平均查找次数接近于1代价相当小关键是在Hash表里存放在其中的数据和它的存储位置是用Hash函数关联的。
我们假设一个Hash函数是x*x%5,( * %的优先级是从左至右)当然实际情况里不可能用这么简单的Hash函数我们这里纯粹为了说明方便而Hash表是一个长度是11的线性表。如果我们要把6放入其中那么我们首先会对6用Hash函数计算一下结果是1所以我们就把6放入到索引号是1这个位置。同样如果我们要放数字7经过Hash函数计算7的结果是4那么它将被放入索引是4的这个位置。这个效果如下图所示。 这样做的好处非常明显。比如我们要从中找6这个元素我们可以先通过Hash函数计算6的索引位置然后直接从1号索引里找到它了。
不过我们会遇到“Hash值冲突”这个问题。比如经过Hash函数计算后7和8会有相同的Hash值对此Java的HashMap对象采用的是”链地址法“的解决方案。效果如下图所示。 具体的做法是为所有Hash值是i的对象建立一个同义词链表。假设我们在放入8的时候发现4号位置已经被占那么就会新建一个链表结点放入8。同样如果我们要找8那么发现4号索引里不是8那会沿着链表依次查找。
虽然我们还是无法彻底避免Hash值冲突的问题但是Hash函数设计合理仍能保证同义词链表的长度被控制在一个合理的范围里。
