抵押网站建设方案,深圳网站建设服务器,鄂州市 网站建设,t字型布局的网站在dw怎么做概念 顺序结构以及平衡树 中#xff0c;元素关键码与其存储位置之间没有对应的关系#xff0c;因此在 查找一个元素时#xff0c;必须要经过关键 码的多次比较 。 顺序查找时间复杂度为 O(N) #xff0c;平衡树中为树的高度#xff0c;即 O( log2N ) #xff0c;搜索的效…概念 顺序结构以及平衡树 中元素关键码与其存储位置之间没有对应的关系因此在 查找一个元素时必须要经过关键 码的多次比较 。 顺序查找时间复杂度为 O(N) 平衡树中为树的高度即 O( log2N ) 搜索的效率取决于搜索过程中 元素的比较次数。 理想的搜索方法可以 不经过任何比较一次直接从表中得到要搜索的元素 。 如果构造一种存储结构通过某种函 数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快 找到该元素 。 当向该结构之中插入元素时根据该元素的关键码和特定的函数计算出该元素应存放的位置并且按此位置存放而在取元素时按同样方式计算出所处位置。这样的话存储和查找的时间复杂度就可以达到O(1)。 该方式即为哈希散列方法用到的函数称为哈希散列函数。构造出来的结构称为哈希表或散列表 哈希函数设置为 hash(key) key % capacity ; capacity 为存储元素底层空间总的大小。 比如一个长度为10的数组 如果要放13hash(13)13%103所以放在3下标但如果要放14会出现什么问题 冲突碰撞 1.概念 对于两个数据元素的关键字 和 (i ! j) 有ki ! kj 但有 Hash(ki ) Hash( kj) 即 不同关键字通过相同哈 希函数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞 。 2.冲突的发生是必然的我们要做的就是降低冲突率 3.冲突的避免--哈希函数的设计 引起哈希冲突的一个原因可能是 哈希函数设计不够合理 。 希函数设计原则 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有 m 个地址时其值域必须在 0 到 m-1 之间 哈希函数计算出来的地址能均匀分布在整个空间中 哈希函数应该比较简单 1.直接定制法常用 取关键字的某个线性函数为散列地址 Hash Key A*Key B。优点简单均匀缺点需要事先知道关键字的分布情况使用场景适合于查找比较小且连续的情况。 例如Hash(key)key-minval;对于数据9795919396minval是91所以将97放到6下标95放到4下标…… 2.除留余数法 散列表中允许的地址数是m就是下标从0到m注意哈希表的底层首先是一个数组那么就取小于等于m接近于m的质数p作为除数用函数 hash(key) key %p来求得地址 3. 平方取中法 --( 了解 ) 假设关键字为 1234 对它平方就是 1522756 抽取中间的 3 位 227 作为哈希地址 再比如关键字为 4321 对 、它平方就是18671041 抽取中间的 3 位 671( 或 710) 作为哈希地址 平方取中法比较适合不知道关键字的分 布而位数又不是很大的情况 4. 折叠法 --( 了解 ) 折叠法是将关键字从左到右分割成位数相等的几部分( 最后一部分位数可以短些 ) 然后将这几部分叠加求和 并按散列表表长取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况 5. 随机数法 --( 了解 ) 选择一个随机函数取关键字的随机函数值为它的哈希地址即 H(key) random(key), 其中 random 为随机数函数。 通常应用于关键字长度不等时采用此法 6. 数学分析法 --( 了解 ) 设有 n 个 d 位数每一位可能有 r 种不同的符号这 r 种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。 注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突 4.冲突的避免--负载因子调节 散列表的载荷因子负载因子填入表中的元素/散列表的长度 由于表长是定值所以填入的元素越多负载因子越大产生冲突的可能性就越大。一般要将载荷因子控制在0.75以下当超过0.75时就应该对哈希表中的数组进行扩容 5.冲突的解决之闭散列 闭散列也叫开放地址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以 把 key 存放到冲突位置中的 “ 下一个 ” 空位置中去。那么如何找到下一个空位置呢 法一线性探测 从发生冲突的位置开始依次向后进行探测直到找到下一个空位置。缺陷是产生冲突的元素会堆积在一块例如 想要插入11213141就会依次放到2380下标 法二二次探测 找下一个空位置的方法为Hi (H0 i^2)% m, 或者 Hi (H0-i^2 )% m。其中H0是通过哈希函数计算出的下标 i 1,2,3… 表示的是发生冲突的次数例如 想要放21通过哈希函数计算出来是1即H01这是第一次发生冲突所以i1所以 Hi (H0i^2 )% m即Hi(11)%102。 6.冲突的解决之开散列哈希桶 开散列法又叫链地址法 ( 开链法 ) 首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子 集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 比如要放11通过散列函数计算出下标为1所以可以通过头插法或者尾插法将11查到对应的链表里 这就是我们所说的哈希表实际上是数组链表红黑树当数组长度64链表长度8以后就会将其变成一棵红黑树 java的HashMap就是用这种哈希表的方式来解决哈希冲突的 7.哈希桶的实现 首先注意哈希桶是一个数组数组的元素其实就是每个链表的头节点 放置元素 首先要找到对应链表然后遍历该链表如果某个结点的key等于待插入结点的key就更新该节点的value值然后结束该方法即可如果没有对应的key就通过头插法或者尾插法插入该节点代码如下 但这样是有缺陷的我们之前提到了负载因子最好不超过0.75所以我们再加一个方法返回当前的负载因子如果大于0.75就进行扩容代码如下 首先添加一个成员变量即默认最大负载因子 然后是计算负载因子 最后是在put方法的最后进行扩容。 但这样的扩容不对因为数组长度变了对应的key所在的下标就会变所以代码应为我用的头插法扩容 获得value HashMapHasSet的实现 1.Map不支持迭代器遍历因为它没有实现Iterable接口要想用迭代器就必须将Map转化成Set 2.Map中的对象不需要必须可比较因为他是通过Hash函数来计算所处位置而不是通过大小比较。并且key或value可以是null如下 3.HashMap和HashSet一样是可以天然去重的TreeSetTreeMap也一样如下 4.HashMap,HashSet对象不一定可比较key也不一定是一个整数那么系统是怎么找到对应的下标从而将键值对放进去的呢这就用到了HashCode方法来生成一个整数。看源码 当key不是null时就会调用key的hashCode方法如果key本身没有hashCode方法就会调用Object类的方法 这段话的意思是在合理情况下不同的对象会返回不同的整数这通常是将对象的内部地址转换为整数实现的所以下面的情况即使Student的id是相同的产生的hashCode也是不同的如下 要想产生同样的整数就可以重写hashCode方法 这是我们根据上面的源码自己重写的方法调用了hash方法传参时直接传入id但最好是通过编译器直接生成hashCode方法同时一并重写equals方法 如果不重写equals方法相同id的对象jinxingequals方法后产生的结果是false因为源码中equals是根据对象的地址比较的 哈希桶的优化代码 我们将哈希桶写成一个泛型类并让其可以通过各种类型的key生成对应的整数代码如下 1.放置键值对 2.根据key得到对应的value 看下面的一段代码 student1和student2的id是一样的而且我们重写了hashCode方法所以说虽然我们只在哈希桶里面放置了student1但在根据student2取元素时得到的也应该是10但结果却如下 这是因为put函数和getval函数有一句是错的即if(cur.keykey)应该用equals方法代码如下
