讯享网

 <p id="34LFNA9G">书接上回，我们继续来聊散列表的代码实现。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fj00sm3wlx001nd000m400qtp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="34LFNA9J">相信通过前面两章对散列表的学习，大家应该已经掌握了散列表的基础知识，今天我们就选用简单的取模方式构建散列函数，分别实现链式法和开放寻址法中的线性探测法来解决碰撞问题，而再散列法则以方法的形式分别在两种实现方法中实现。</p><p><h5>01、链式法实现</h5><h5>1、元素定义</h5></p><p id="34LFNA9M">通过前面链式法的详细讲解，我们知道链式法需要构建散列桶，每个桶又指向一个链表，所以首先需要定义一个链表节点对象用来存储散列表的记，而记录中包括key、value以及指向下个节点的指针，代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F8e22beebj00sm3wlz003td0011s00s0p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>2、初始化 Init</h5></p><p id="34LFNA9P">定义好链表，我们还需要定义散列桶，其实就是定义一个数组，同时我们在定义两个私有变量分别维护桶的数量和散列表总的元素个数。</p><p id="34LFNA9Q">而初始化方法主要就是根据指定初始容量来初始化这些变量，如果不指定初始容量则默认为16，具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F4afb57b7j00sm3wko004vd0011s00s0p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>3、获取散列元素数量 Count</h5></p><p id="34LFNA9T">获取散列表元素数量只需返回维护元素数量的私有字段即可，实现如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Ffea683e6j00sm3wkq0021d0011s00iqp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>4、插入 Insert</h5></p><p id="34LFNAA0">插入方法相对比较复杂，我们可以大致分为以下几步：</p><p id="34LFNAA1">（1）检测负载因子是否达到阈值，超过则触发再散列动作；</p><p id="34LFNAA2">（2）构建好新的键值对象；</p><p id="34LFNAA3">（3）检测新的键所在的桶是否有元素，没有元素则直接插入新对象；</p><p id="34LFNAA4">（4）如果键所在桶有元素，则遍历桶中链表，已存在相同key则更新value，否则插入新对象；</p><p id="34LFNAA5">（5）维护元素数量；</p><p id="34LFNAA6">具体代码实现如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F0cba8edej00sm3wku00d1d0011s021kp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>5、删除 Remove</h5></p><p id="34LFNAA9">删除逻辑和插入逻辑类似，都需要先计算key所在的散列桶，然后再处理桶中链表，只需要把链表上相应的节点删除即可，具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Ff5j00sm3wkz008td0011s01gup.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>6、查找 Find</h5></p><p id="34LFNAAC">查找逻辑和插入、删除逻辑类似，都是先计算key所在桶位置，然后处理桶中链表，直至找到相应的元素，代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Faj00sm3wl2006id0011s00zap.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>7、获取所有键 GetKeys</h5></p><p id="34LFNAAF">获取所有键，是遍历所有散列桶即桶中链表上的所有元素，最后取出所有key。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fad9a32b6j00sm3wl5005qd0011s010ap.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>8、获取所有值 GetValues</h5></p><p id="34LFNAAI">获取所有值，是遍历所有散列桶即桶中链表上的所有元素，最后取出所有value。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F03b1717ej00sm3wl7005qd0011s010ap.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>9、再散列 Rehash</h5></p><p id="34LFNAAL">再散列也是比较有挑战的一个方法，这里并没有像上一篇文章中说的去实现分批次迁移老数据，而是一次性迁移，对分批次迁移感兴趣的可用自己实现试试。</p><p id="34LFNAAM">这里的实现是非常简单的，就是遍历所有老数据，然后对每个老数据重新执行一次插入操作，具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fdj00sm3wlc007xd0011s01cqp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>02、开放寻址法实现</h5><h5>1、元素定义</h5></p><p id="34LFNAAQ">该元素的定义和链式法实现的元素定义略有不同，首先不需要指向下一个节点的指针，其次需要一个标记位用来标记空位或被删除。因为如果删除后直接置空则可能会导致后续查找过程中出现误判，因为如果置空，而后面还有相同散列值元素，但是探测方法探测到空值后会停止探测后续元素，从而引发错误，具体实现代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fdj00sm3wle0031d0011s00ksp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>2、初始化 Init</h5></p><p id="34LFNAAT">初始化方法主要就是根据指定初始容量来初始化散列表以及其大小和总的元素数量，如果不指定初始容量则默认为16，具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F9e21988bj00sm3wlg0052d0011s00t2p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>3、获取散列元素数量 Count</h5></p><p id="34LFNAB0">获取散列表元素数量只需返回维护元素数量的私有字段即可，实现如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Ffea683e6j00sm3wkq0021d0011s00iqp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>4、插入 Insert</h5></p><p id="34LFNAB3">此插入方法和链式法实现整体思路相差不大具体实现上略有差别，我们可以大致分为以下几步：</p><p id="34LFNAB4">（1）检测负载因子是否达到阈值，超过则触发再散列动作；</p><p id="34LFNAB5">（2）检测新的键所在的位置是否有元素，没有元素或位置非被占用则直接插入新对象；</p><p id="34LFNAB6">（4）如果键所在位置有元素并且位置被占用，则线性探测后续位置，已存在相同key则更新value，否则插入新对象；</p><p id="34LFNAB7">（5）维护元素数量；</p><p id="34LFNAB8">具体代码实现如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fe2a5378cj00sm3wlj009jd0011s01iyp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>5、删除 Remove</h5></p><p id="34LFNABB">删除逻辑和插入逻辑类似，都需要先计算key所在的散列表中的索引，循环探测后续位置元素如果发现相同的key，则标记元素为非占用状态，具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fb84cb227j00sm3wlm006ud0011s00zap.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>6、查找 Find</h5></p><p id="34LFNABE">查找逻辑和插入、删除逻辑类似，都是先计算key所在索引，如果有元素并且位置标记为被占用且key相同则返回此元素，否则线性探测后续元素，如果最后未找到则报错，代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Ff678f068j00sm3wlp005sd0011s00v4p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>7、获取所有键 GetKeys</h5></p><p id="34LFNABH">获取所有键，是遍历所有散列表所有元素，最后取出标记为被占用状态的所有key。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Ff73945bej00sm3wlr003gd0011s00nwp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>8、获取所有值 GetValues</h5></p><p id="34LFNABK">获取所有值，是遍历所有散列表所有元素，最后取出标记为被占用状态的所有value。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fa12f4e2cj00sm3wlt003gd0011s00nwp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>9、再散列 Rehash</h5></p><p id="34LFNABN">这里的实现和链式法实现思路一样，就是遍历所有老数据，然后对每个老数据重新执行一次插入操作，具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F49ac0edfj00sm3wlv006bd0011s010ap.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="34LFNABP"><strong>注</strong>：测试方法代码以及示例源码都已经上传至代码库，有兴趣的可以看看。https://gitee.com/hugogoos/Planner</p>