前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏在上篇博客中解析了二叉搜索树的特征和实现二叉搜索树在理想状态下查找元素的时间复杂度为O(logN)Map和Set的还可以基于哈希表来实现哈希表的特点就是查找删除添加元素的时间复杂度都是O(1)是不是特别的神奇这篇博客就会解析哈希表的底层原理并用代码模拟实现我们自己的HashMap这篇博客中涉及链表的头插有兴趣的铁汁可以看数据专栏中之前的博客来复习这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1哈希表简介哈希表这个数据结构查找插入删除的时间复杂度都是O(1)假设这样一个场景给定一个整型数组约定这个数组中的元素的范围是0-99一共有100个数字现在要统计这个数组中每个数字出现的次数要怎么搞呢可以通过键值对的方法来搞把每个要统计的数字作为“键key”把数字出现的次数作为“值value)”就可以创建个长度为100的数组count元素i就出现了count[i]次i就表示keycount[i]就表示valuepublicclassTest2{publicstaticvoidmain(String[]args){int[]arr{1,1,3,2,42,35,6,64,3,7,47,44,57,5,4,57,3,6,4,5,5,3,2,6,4};int[]countnewint[100];for(inti0;iarr.length;i){count[arr[i]];}//输出统计结果for(inti0;icount.length;i){if(count[i]0){System.out.println(i出现了count[i]次);}}}}在这道题中arr数组的范围是[0,99]这是个比较简单的情况①那如果这个数据的范围更大呢②如果这个数据里面存在负数/小数呢③如果这个数据里面存在字符串呢首先是第一种如果数组中是任意的int类型-21亿 —— 21亿要知道这个数组中每个数字出现的频率肯定是不能创建一个长度为42亿的数组的开销太大了那这时候就需要有一系列的手段把要表示的元素转化到数组的下标上比如说转化到一个长度为10000的数组上那么这个转换的过程就称为“哈希函数”哈希表O(1)的奥秘就在于是数组访问下标哈希函数原始的值 下标转换过程O(1)根据下标进行增删改查也是 O(1)可能铁汁们看这部分内容还是不明白哈希表是什么东西这里只是一个引入直接往后看就可以看完第3部分的代码实现就很清楚了2哈希函数设计假设key0 — 21亿哈希表的数组的长度是1w通常采用求余数的方法这里一般余的数是哈希表数组的长度哈希函数 key % 10000哈希函数中肯定会存在“空间不对等”的问题就比如说42亿个元素搞了一个长度为10000的元素来转化那么肯定会存在重复就是两个或者多个不同的数据映射到同一个数组下标了这个也称为“哈希冲突”。如果key中有10001、20001、30001这三个数字那么他们的映射都是下标1那么下标1的位置只能存一个这就是哈希冲突解决哈希冲突有两个方案闭散列和开散列。1闭散列假设在10001前 余上10000等于1的数字 在原数组中没有那么就是从10001开始10001 % 10000 1 那10001就映射到了哈希表数组下标为1的位置20001 % 10000 1这里本来也应该映射到下标为1的位置但是1这里被占了那就往后找发现2这个位置还没被占那么20001就映射到下标为2的位置30001 % 10000 1 这里本来应该映射到下标为1的位置但是发现这里被占了接着往后找想放到下标为2的位置但是还是被占了继续往后找发现下标为3的地方是空的就放到下标为3的位置后面key的值为3000230002 % 10000 2 发现2已经被占了从2开始往后找就找到了下标为4的位置映射到下标为4的位置这就是线性探测线性探测其实有多种方法可以一个一个往后去找空闲位置当然也可以进行二次探测那就是如果第一次探测发现后面被占了那后面直接跳4个发现4个后也被占了那就往后面跳9个跳9个发现还被占了那就跳16个。也就是每次探测的顺序1 4 9 16 25 …这样就能很大程度上减少元素的聚集可能有的铁汁会想这种闭散列的话一旦起冲突那就是往其他的地方存最后可能有很多数据存的都是驴嘴不对马尾那这找数据的时候不是很难找吗是这样的因此闭散列在实际的开发中是基本上不用的用的比较多的还是开散列2开散列开散列就能保证哈希函数计算出的下标是准确的位置。它是使用一个链表来保存冲突的元素相当于数组的每个元素都是一个链表元素都是存在这个链表中这时候就不存在哈希冲突了。那哈希表中查找数据的时间复杂度是O1是因为操作是在数组中进行的这里又加了个链表还要遍历链表查找/删除数据那时间复杂度还是O1吗其实这里链表的长度是很短的有个这样的概念叫负载因子负载因子 整个哈希表保存的元素的个数/数组的长度这个负载因子也就是链表平均的长度在实际操作中我们可以控制负载因子的大小比如当负载因子增加到一定程度时对数组进行扩容进而降低负载因子控制当负载因子比较小的时候平均每个链表上挂的元素也比较少这样查找删除的时间复杂度就近似为O1。总结一下哈希表本质上就是利用数组下标操作比较高效的特点来实现的一个数据结构通过哈希函数把要保存的内容映射到数组下标上如果出现冲突再通过开散列的方式来解决冲突同时也引入负载因子来限制链表的平均长度保证最后的时间复杂度仍是O(1)级别。3优化Java标准库中的HashMap还有一些额外的优化手段前面提到当一个链表的长度较大时可以通过扩容来降低链表的负载因子进而保证哈希表的查找删除的时间复杂度近似为O(1)但扩容本身也是有一定的开销的要新创建数组再逐个元素复制过去而且也会出现整体链表的平均长度很小但是其中一个链表上挂了特别多的元素特别长小概率这也会影响查找删除的时间复杂度。Java标准库中的HashMap会在元素往链表上插入的时候做一个判定如果这时候链表已经很长了达到一定值了那就把链表转化为红黑树一个相对平衡的二叉搜索树在Java标准库中一般要求负载因子超过0.75就进行扩容这个要求是比较严格的在实际工作中一般自己设置的都比这个要大。4示例哈希函数有很多的计算方法最常用的就是前面提到的除留余数法对于小数负数字符串可以先转化下再使用除留余数法对于小数可以扩大一定倍数变成整数对于负数可以整体加上一个比较大的正数对于字符串可以使用各种的编码规则把字符串用数字去表示当然具体的计算过程程序员不需要考虑是数学家们的事情感兴趣的铁汁可以大概看一下在main函数中使用hashCode()然后按住ctrl键点击hashCode()就会进入到内部的哈希函数这里的判断是比较复杂的先判断是不是拉丁文进而判断使用哪种方法转换这是经过数学家研究的这样转化哈希冲突比较少integer就是直接返回原数的值如下所示Double要通过二进制进行一系列的转化3代码实现我们就模拟实现个自己的HashMap类1框架先创建出一个基本的框架包括链表节点的定义每个节点存储的数据有key、value、next哈希表数组的创建哈希函数扩容操作获取操作以及删除键值对的操作。publicclassMyHashMap{//使用Node表示哈希表中的链表节点staticclassNode{publicintkey;publicintvalue;publicNodenext;publicNode(intkey,intvalue){this.keykey;this.valuevalue;}}//一般数组的初始长度设置为素数这样哈希冲突就会比较少privateNode[]tablenewNode[1001];privateintsize;//设置哈希函数把key转为数组下标privateinthashCode(intkey){returnkey%table.length;}//哈希表的核心操作//插入/修改键值对publicvoidput(intkey,intvalue){}//扩容操作publicvoidresize(){}//根据键获取值publicIntegerget(intkey){}//删除键值对publicvoidremove(){}}2put操作1.put函数就是传入key和value的值创建键值对的首先用hashCode方法计算出这个节点在数组中的下标位置取出这个地方链表的头部节点head2.在这个位置的链表中找key是不是已经在链表中存在了如果存在就修改value即可如果不存在就用头插的方法把newNode插入到链表中3. 稍微解析下头插head是链表的头节点用新创建的节点指向原来的头节点再更新链表的头节点即可table[index]表示的就是链表的头节点代码就是table[index] newNode4. 插入完成后size并计算负载因子如果超了就进行自动扩容。因为size和table.length都是整数因此要转为double来计算publicvoidput(intkey,intvalue){//1,根据key,来计算出下标的位置intindexhashCode(key);//2,遍历链表看一下key是否在链表中已经存在了//如果存在就修改对应的valueNodeheadtable[index];for(Nodecurhead;cur!null;curcur.next){if(cur.keykey){cur.valuevalue;return;}}//3,如果不存在就直接插入按照头插的方式NodenewNodenewNode(key,value);newNode.nexthead;table[index]newNode;//4,插入完成后size就要加1size;if((double)size/table.length0.75){resize();}}3resize操作扩容这里扩容就是直接数组长度扩大两倍哈希数组的长度最好是质数能减少哈希冲突这里乘以2肯定不是质数了在工作中通常就是找比乘以2后大的质数这里我们就不再那样搞了铁汁们了解下即可搞两个for循环把节点一个一个搞到新的哈希数组中去最后用让table等于newTable用新的数组替换旧的数组在新数组的链表中插入节点采用的是头插如下图先让newNode.next newTable[newIndex]数组中存储的是头节点的位置直接修改数组的存储即可newTable[newIndex] newNode代码如下//扩容操作publicvoidresize(){Node[]newTablenewNode[table.length*2];//搬运把原来table中所有的链表都搬运过来for(inti0;itable.length;i){for(Nodecurtable[i];cur!null;curcur.next){//根据原有节点创建新节点插入到数组中去NodenewNodenewNode(cur.key,cur.value);intnewIndexcur.key%newTable.length;//把新结点头插到新的链表中去newNode.nextnewTable[newIndex];newTable[newIndex]newNode;}}//用新的数组替换旧的tablenewTable;}4get操作根据键获取值get操作就是先根据key找出下标再遍历链表找到key就返回它的value遍历完链表还是找不到key的话就说明key不存在返回null。publicIntegerget(intkey){//1根据key值计算出下标intindexhashCode(key);//2,在对应的链表上找到该key的value值for(Nodecurtable[index];cur!null;curcur.next){if(cur.keykey){returncur.value;}}//通过上述循环如果没有找到就返回null.returnnull;}5remove操作删除操作删除操作分为三种情况按key查找到index发现链表是空的那就说明这个key在哈希表中不存在直接return即可要删除的节点是头节点如果是的话就需要修改这个地方数组中存的节点的地址可以参照resize操作中的那张图来理解节点在链表中并且也不是头节点先通过while循环来找到这个节点然后修改其上个节点prev的指向没有引用指向该节点这个节点就删除了//删除键值对publicvoidremove(intkey){//1,根据key找到下标intindexhashCode(key);//2,针对链表删除key的节点//a)先考虑链表为空的情况if(table[index]null){//链表为空就直接返回不需要删除return;}//b)再考虑是否是头节点的情况if(table[index].keykey){table[index]table[index].next;size--;return;}//c)一般情况下我们遍历链表的时候把该节点的前一个节点也记录一下Nodeprevtable[index];Nodecurtable[index].next;while(cur!null){if(cur.keykey){//触发删除操作prev.nextcur.next;size--;//由于hash表中的key是唯一的,在插入操作中也判断过了因此只需删除一次即可return;}prevcur;curcur.next;}这里我们增加元素时会进行扩容操作但是删除元素时却不需要进行缩容操作因为现在的内存的代价并不高浪费一点其实是无所谓的但是要是在20年前内存比较珍贵的时候那就可能还需要有缩容操作结语二叉搜索树的特征就是能对元素进行排序如果需要进行排序就用TreeMap/TreeSet使用迭代器/foreach 对 TreeMap/TreeSet 进行遍历本质上就是对二叉搜索树进行中序遍历中序遍历二叉搜素树的结果就是从小到大哈希表的特征就是效率高是插入、删除、查询的时间复杂度都是O(1)如果没有对元素进行排序的需求就建议用HashMap/HashSet日常情况下大多数还是用哈希表的这篇博客也是数据结构专栏的最后一篇博客感谢铁汁们对该专栏的支持现在已经更新完成的专栏还有数据库专栏、JavaSE专栏接下来博主会全力更新JavaEE专栏和算法专栏也希望铁汁们能够多多支持铁汁们如果有博客改进的建议或者有其他知识上的问题都可以私信博主博主看到后一定会回复专栏完结撒花