引擎搜索网站,wordpress去除标志,小程序订单管理系统,闽侯做网站哈希概念
线性表、树结构的查找方式都是以关键字的比较为基础#xff0c;查找效率比较低#xff0c;顺序表的时间复杂度是O#xff08;n#xff09;#xff0c;平衡树中为树的高度#xff0c;即O#xff08;logn#xff09;#xff0c;搜素的效率取决于搜索过程的元素…哈希概念
线性表、树结构的查找方式都是以关键字的比较为基础查找效率比较低顺序表的时间复杂度是On平衡树中为树的高度即Ologn搜素的效率取决于搜索过程的元素比较次数。
理想的搜素方法可以用不经过比较一次直接从表中得到要搜素的元素。如果构造一种存储结构通过某种函数hashFunc使元素的存储位置与他的关键字之间能够建立一一映射的关系那么在查找元素的时候,就可以很快寻找到该元素这就是哈希的思想.
哈希函数
插入元素 根据待插入的元素的关键字码以此函数计算出该元素的存储位置并且按照此位置进行存放
搜素元素 对元素的关键字码进行同样的计算把求得函数值当做元素的存储位置在结构中按此位置取元素比较若关键字码相同则搜素成功。
此方法即为哈希散列方法哈希散列方法中使用的转换函数称之为哈希散列函数构造出来的结构就是哈希表hashTable或者散列表。
例如数据集合{176459}
哈希函数设置为hashkey key%capacity;(capacity代表的是底层空间总大小可以理解成元素个数) 用该方法进行搜素的时候不必多次进行比较可以直接找到想找的关键字但是我们就会出现一个问题如果再次插入一个44怎么办呢这就会引出下面的部分哈希冲突。
哈希冲突
概念
对于两个关键字ki,kji ! j有ki ! kj,但是有Hashki Hashkj即不同的关键字通过哈希函数计算出相同的哈希地址这种现象称之为哈希冲突。
冲突的避免
首先我们要明确疑点由于我们哈希表底层数组容量往往小于实际要存储的数量这就导致了一个问题冲突是必然的但是我们可以降低冲突率。
哈希函数的设计
1、直接定制法
取关键字的某个线性函数为散列地址HashkeyA*keyB 即是一个yaxb的函数如计数排序数字91存储在91-90的下标上优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况。
2、除留余数法
这个就是我们上面所介绍的方法标准的官方说法是设散列表中允许的地址数为m如果10个数据m的范围就是0-9取一个不大于m的数但是最接近或者等于m的质数p作为除数按照哈希函数Hashkey key%ppm将关键字码转换为哈希地址。
还有很多的方法但是使用的很少所以这里不过多介绍。
负载因子调节
散列表的载荷因子定义为填入表格的元素/散列表的长度
在java系统库中限制载荷因子为0.75如果大于这个数字就需要降低载荷因子。
哈希冲突的解决
哈希冲突的常见的两种解决方案就是闭散列和开散列。
闭散列也叫开放定址法当哈希表没有被填满说明哈希表还有空位置那么可以把key存放到冲突位置的下一个空位置去。那么如何寻找下一个空位置呢
1、线性探测
比如上面的场景现在需要插入元素44先通过哈希函数计算哈希地址下标是4所以理论上应该插入到4的位置但是该位置已经存放了元素4即发生了哈希冲突。
线性探测从发生冲突的位置开始一次向后探测直到寻找到下一个空位置为止。 采用闭散列处理哈希冲突的时候不能随便物理删除哈希表已经有的元素若直接删除元素会影响其他元素的搜索。比如删除4如果直接删除4那么在查找44的时候就会受到影响。因此线性探测采用标记的伪元素来删除一个元素。
2、二次探测
线性探测的缺陷是产生冲突的元素堆积到一块这与其找下一个元素位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免这样的问题找下一个空位置的方法为Hi(H0i²%m或者Hi(H0-i²%m其中i123....H0是通过哈希函数计算出元素所在位置m是表的大小。
因此闭散列表的最大缺陷就是空间利用率低这也是哈希的缺陷。
开散列/哈希桶重点
开散列开散列又叫链地址法开链法首先对关键码集合用哈希函数计算出哈希地址具有相同的地址的关键码归于同一子集合每一个子集称作一个桶各个桶中的元素通过一个单链表连接器起来各链表的头节点都存储在哈希表中。 开散列可以认为把一个大集合中的搜素问题转化到小集合中进行。
代码实现
public class Hashbucket {static class Node{private int key;private int value;private Node next;public Node(int key, int value) {this.key key;this.value value;}}public Node[] array;public int useSize;private static final float DEFAULT_LOAD_FACTOR 0.75f;public Hashbucket() {arraynew Node[10];}public void put(int key,int value){Node nodenew Node(key,value);int index node.key%array.length;Node curarray[index];//java1.8之后采用的是尾插法 这里采用头插法while(cur!null){if(cur.keykey){cur.valuevalue;return;}curcur.next;}node.nextarray[index];array[index]node;useSize;if(loadFactor()DEFAULT_LOAD_FACTOR){resize();}}public void resize(){//二倍扩容Node[] tmpArraynew Node[array.length*2];for (Node node : array) {Node cur node;while (cur ! null) {Node curNext cur.next;int index cur.key % tmpArray.length;//头插法cur.next tmpArray[index];tmpArray[index] cur;cur curNext;}}arraytmpArray;}public float loadFactor(){return array.length*1.0f/useSize;}public int get(int key){int indexkey%array.length;Node curarray[index];while(cur!null){if(cur.keykey){return cur.value;}curcur.next;}return -1;}
}这个代码中这个扩容部分我们要仔细的说一说但负载因子大于0.75的时候我们需要降低哈希冲突因为我们的元素个数是一定的所以我们就需要增大散列表的大小但是当我们扩容的时候我们会打乱原来的散列表比如原来4和14都是在节点4的位置当我们二倍扩容的时候我们就需要将14放到节点14的位置。
