1.本技术涉及哈希表技术领域，更具体地说，涉及一种哈希表遍历方法、系统、设备及计算机可读存储介质。
背景技术：2.在软件系统中，哈希表是一种支持快速查找、插入和删除操作的常见数据结构，这些操作的平均时间复杂度可以达到常数级。在哈希表的一般实现中，哈希表被组织成若干哈希桶形成的数组，每个哈希桶对应一个链表。插入操作时，首先通过哈希函数计算插入元素的哈希值，根据哈希值计算出哈希桶的索引，然后将其插入到哈希桶对应的链表中。查找过程也是先通过哈希函数得到查找元素的哈希桶索引，然后在其链表中查找。
3.对于一个具有m个哈希桶，存储了n个元素的哈希表，定义哈希表装载因子为n/m。随着哈希表的插入和删除，装载因子可能会变的很大或很小。装载因子过大，意味着过多的元素存储到同一个哈希桶中，这会影响查找效率；装载因子过小，意味着哈希桶利用率较低，造成空间浪费。因此，哈希表一般都有重哈希(rehash)操作，即在装载因子过大的情况下，扩展哈希表，使用更多的哈希桶存储元素；装载因子过小时，收缩哈希表，使用更少的哈希桶节约空间。哈希表的rehash过程一般较为耗时，如果一次性完成的话会影响程序运行效率，因此一般是将rehash均摊到哈希表的查找、插入和删除操作过程中。
4.哈希表一般还需要支持遍历操作，以便对其中所有元素进行特定的操作，特定的操作一般比较耗时，所以遍历哈希表也是分多次进行的。哈希表处于稳定状态时，哈希表的遍历很简单。但是如果哈希表在遍历期间发生了rehash，哈希表中的元素会重新分配哈希桶，很容易造成遍历时哈希桶被遗漏或者重复遍历的情况。
5.综上所述，如何准确对哈希表进行遍历是目前本领域技术人员亟待解决的问题。
技术实现要素：6.本技术的目的是提供一种哈希表遍历方法，其能在一定程度上解决如何准确对哈希表进行遍历的技术问题。本技术还提供了一种哈希表遍历系统、设备及计算机可读存储介质。
7.为了实现上述目的，本技术提供如下技术方案：
8.一种哈希表遍历方法，包括：
9.获取目标哈希表；
10.以二进制形式表示所述目标哈希表中每个哈希桶的游标；
11.将0作为当前时刻的遍历游标；
12.对当前时刻的遍历游标对应的所述哈希桶进行遍历；
13.将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标；
14.判断下一时刻的遍历游标是否为0，若否，则返回执行所述对当前时刻的遍历游标
对应的所述哈希桶进行遍历的步骤；若是，则结束遍历。
15.优选的，所述对当前时刻的遍历游标对应的所述哈希桶进行遍历，包括：
16.对当前时刻的遍历游标对应的所述哈希桶进行遍历，并在遍历过程中判断所述目标哈希表是否发生rehash；
17.若在遍历过程中所述目标哈希表发生rehash，则以二进制形式更新rehash后的所述目标哈希表中每个所述哈希桶的游标；
18.所述将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标，所述判断下一时刻的遍历游标是否为0之前，还包括：
19.按照保持遍历游标值不变的规则，基于所述哈希桶更新后的游标来更新下一时刻的遍历游标。
20.优选的，所述目标哈希表的大小为2n。
21.优选的，所述游标的位数为n。
22.一种哈希表遍历系统，包括：
23.第一获取模块，用于获取目标哈希表；
24.第一表示模块，用于以二进制形式表示所述目标哈希表中每个哈希桶的游标；
25.第一设置模块，用于将0作为当前时刻的遍历游标；
26.第一遍历模块，用于对当前时刻的遍历游标对应的所述哈希桶进行遍历；
27.第二设置模块，用于将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标；
28.第一判断模块，用于判断下一时刻的遍历游标是否为0，若否，则返回执行所述对当前时刻的遍历游标对应的所述哈希桶进行遍历的步骤；若是，则结束遍历。
29.优选的，所述第一遍历模块包括：
30.第一遍历单元，用于对当前时刻的遍历游标对应的所述哈希桶进行遍历，并在遍历过程中判断所述目标哈希表是否发生rehash；若在遍历过程中所述目标哈希表发生rehash，则以二进制形式更新rehash后的所述目标哈希表中每个所述哈希桶的游标；
31.还包括：
32.第一设置单元，用于所述第二设置模块将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标，所述第一判断模块判断下一时刻的遍历游标是否为0之前，按照保持遍历游标值不变的规则，基于所述哈希桶更新后的游标来更新下一时刻的遍历游标。
33.优选的，所述目标哈希表的大小为2n。
34.优选的，所述游标的位数为n。
35.一种哈希表遍历设备，包括：
36.存储器，用于存储计算机程序；
37.处理器，用于执行所述计算机程序时实现如上任一所述哈希表遍历方法的步骤。
38.一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机程序，所述计算机程序被处理器执行时实现如上任一所述哈希表遍历方法的步骤。
39.本技术提供的一种哈希表遍历方法，获取目标哈希表；以二进制形式表示目标哈希表中每个哈希桶的游标；将0作为当前时刻的遍历游标；对当前时刻的遍历游标对应的哈
希桶进行遍历；将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标；判断下一时刻的遍历游标是否为0，若否，则返回执行对当前时刻的遍历游标对应的哈希桶进行遍历的步骤；若是，则结束遍历。本技术中，基于二进制反向进位的方式生成哈希桶的游标，并据此对哈希表进行遍历，准确性高。本技术提供的一种哈希表遍历系统、设备及计算机可读存储介质也解决了相应技术问题。
附图说明
40.为了更清楚地说明本技术实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本技术的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。
41.图1为本技术实施例提供的一种哈希表遍历方法的流程图；
42.图2为本技术实施例提供的一种哈希表遍历系统的结构示意图；
43.图3为本技术实施例提供的一种哈希表遍历设备的结构示意图；
44.图4为本技术实施例提供的一种哈希表遍历设备的另一结构示意图。
具体实施方式
45.下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本技术一部分实施例，而不是全部的实施例。基于本技术中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本技术保护的范围。
46.请参阅图1，图1为本技术实施例提供的一种哈希表遍历方法的流程图。
47.本技术实施例提供的一种哈希表遍历方法，可以包括以下步骤：
48.步骤s101：获取目标哈希表。
49.实际应用中，可以先获取目标哈希表，目标哈希表的类型及大小等可以根据实际需要确定。
50.步骤s102：以二进制形式表示目标哈希表中每个哈希桶的游标。
51.实际应用中，在获取目标哈希表之后，需以二进制形式表示目标哈希表中每个哈希桶的游标，以便后续基于哈希桶的游标对目标哈希表进行遍历。
52.具体应用场景中，本技术中的目标哈希表的大小可以为2n，相应的，游标的位数可以为n。相应的，哈希桶索引可以是hashkey&mask，其中hashkey表示通过哈希函数计算出的元素哈希值，mask为2的n次方减1。
53.步骤s103：将0作为当前时刻的遍历游标。
54.步骤s104：对当前时刻的遍历游标对应的哈希桶进行遍历。
55.实际应用中，在以二进制形式表示目标哈希表中每个哈希桶的游标之后，便可以将0作为当前时刻的遍历游标，并对当前时刻的遍历游标对应的哈希桶进行遍历来对目标哈希表开始遍历。
56.步骤s105：将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标。
57.实际应用中，在对当前时刻的遍历游标对应的哈希桶进行遍历之后，便可以将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，也即以反向二进制的方式来基于当前时刻的遍历游标生成下一时刻的遍历游标。
58.为了便于理解，假设目标哈希表大小为8，此时n为3，初始情况下游标为000，游标按照二进制反向进位的方法进行演变反向进位，因此，游标的演变过程就是000,100,010,110,001,101,011,111,000，如果遍历期间没有发生rehash，则每次遍历都是以游标为索引遍历哈希桶，8次遍历后完成哈希表的遍历，期间没有哈希桶的遗漏和重复。相应的，假设目标哈希表大小为16，此时n为4，游标的演变过程就是0000，1000，0100，1100，0010，1010，0110，1110，0001，1001，0101，1101，0011，1011，0111，1111，0000。如果遍历期间没有发生rehash，则16次遍历后完成哈希表的遍历，期间没有哈希桶的遗漏和重复。
59.步骤s106：判断下一时刻的遍历游标是否为0，若否，则返回执行步骤s104。
60.实际应用中，在将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标之后，便可以判断下一时刻的遍历游标是否为0，若为0，则表示已完成对目标哈希表的遍历，此时可以结束遍历，若不为0，则表示未完成对目标哈希表的遍历，此时需将下一时刻作为当前时刻来返回执行对当前时刻的遍历游标对应的哈希桶进行遍历及以后的操作。
61.具体应用场景中，在对当前时刻的遍历游标对应的哈希桶进行遍历的过程中，可以对当前时刻的遍历游标对应的哈希桶进行遍历，并在遍历过程中判断目标哈希表是否发生rehash；若在遍历过程中目标哈希表发生rehash，则以二进制形式更新rehash后的目标哈希表中每个哈希桶的游标；
62.相应的，在将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标，判断下一时刻的遍历游标是否为0之前，还需按照保持遍历游标值不变的规则，基于哈希桶更新后的游标来更新下一时刻的遍历游标。
63.为了便于理解，假设目标哈希表大小从8扩展为16，则mask的值从111变为1111，同样的元素其哈希值保持不变，如果mask为111时计算得到的索引为abc，则mask扩展为1111后，计算得到的新索引值为0abc或1abc；假设rehash之前已经遍历完游标为010的哈希桶，按照游标演变顺序下一个游标为110，如果下一次遍历前发生扩展，则原来110这个游标，在长度为16的情况下，就成了0110，因此开始遍历索引为0110的哈希桶中的节点；也即大小为8时，已经遍历过的游标分别是：000，100，010，哈希表长度扩展到16后，在这些索引的哈希桶中的节点，分布到新的哈希桶中，新哈希桶的索引将会是：0000，1000，0100，1100，0010，1010，而这些正好是将要遍历的0110之前的索引，从0110开始，按照长度为16的哈希表游标变化过程遍历下去，这样既不会漏掉节点，也不会遍历重复的节点。
64.相应的，在目标哈希表长度为16时，假设已经遍历完0100的游标，下一个游标为1100，如果此时哈希表长度缩小为8，1100这个游标，在长度为8的情况下，就成了100，因此开始遍历索引为100的哈希桶中的节点；也即在长度为16时，已经遍历过的游标是：0000，1000，0100，哈希表缩小后，这些索引的哈希桶中的节点，分布到新的哈希桶中的索引将会是：000和100，现在要从索引为100的哈希桶开始遍历，这样不会漏掉节点，但是之前长度为16时索引为0100中的节点会被重复遍历，然而，也就仅0100这一个哈希桶中的节点会重复而已，稳定性和健壮性均较好。
65.本技术提供的一种哈希表遍历方法，获取目标哈希表；以二进制形式表示目标哈希表中每个哈希桶的游标；将0作为当前时刻的遍历游标；对当前时刻的遍历游标对应的哈希桶进行遍历；将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标；判断下一时刻的遍历游标是否为0，若否，则返回执行对当前时刻的遍历游标对应的哈希桶进行遍历的步骤；若是，则结束遍历。本技术中，基于二进制反向进位的方式生成哈希桶的游标，并据此对哈希表进行遍历，准确性高。
66.为了便于理解本技术提供的哈希表遍历方法，现结合常规顺序演变游标的方法来对本方案进行说明：
67.假设目标哈希表大小为8，按照常规顺序，游标的演变过程是000，001，010，011，100，101，110，111，000；哈希表大小为16，游标的演变过程是0000，0001，0010，0011，0100，0101，0110，0111，1000，1001，1010，1011，1100，1101，1110，1111，0000；
68.在目标哈希表大小为8时，假设已经遍历完游标为010的哈希桶，下一个游标为011，如果遍历011之前，哈希表长度扩展成了16，011这个游标就成了0011；
69.假设在长度为8时，已经遍历过的游标是：000，001，010，哈希表长度扩展到16后，这些索引的哈希桶中的节点，分布到新的哈希桶的索引将会是：0000，1000，0001，1001，0010和1010。现在要开始遍历的游标为0011，而1000，1001，1010这些哈希桶中的节点在后续还是会遍历到，这就产生了较多的重复遍历；
70.而在哈希表缩小的情况下，哈希表长度为16时，遍历完0100的游标后，下一个游标为0101，此时长度缩小为8，0101这个游标就成了101；
71.在长度为16时，尚未遍历过的游标是：0101，0110，0111，1000，1001，1010，1011，1100，1101，1110，1111。在哈希表长度缩小后，这些游标对应的元素分配到新的哈希桶中，索引将会是：000，001，010，011，100，101，110，111。现在要开始遍历的游标为101，那101之前的000，001，010，011，100这些游标就不会遍历了，这就发生了遗漏的情况；
72.因此，按照常规顺序遍历会发生哈希桶的遗漏，也可能会有较多的哈希桶被重复遍历。而本技术方案并不存在此种情况，保证了系统的稳定性、健壮性，提升了系统运行效率。
73.请参阅图2，图2为本技术实施例提供的一种哈希表遍历系统的结构示意图。
74.本技术实施例提供的一种哈希表遍历系统，可以包括：
75.第一获取模块101，用于获取目标哈希表；
76.第一表示模块102，用于以二进制形式表示目标哈希表中每个哈希桶的游标；
77.第一设置模块103，用于将0作为当前时刻的遍历游标；
78.第一遍历模块104，用于对当前时刻的遍历游标对应的哈希桶进行遍历；
79.第二设置模块105，用于将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标；
80.第一判断模块106，用于判断下一时刻的遍历游标是否为0，若否，则返回执行对当前时刻的遍历游标对应的哈希桶进行遍历的步骤；若是，则结束遍历。
81.本技术实施例提供的一种哈希表遍历系统，第一遍历模块包括：
82.第一遍历单元，用于对当前时刻的遍历游标对应的哈希桶进行遍历，并在遍历过程中判断目标哈希表是否发生rehash；若在遍历过程中目标哈希表发生rehash，则以二进
制形式更新rehash后的目标哈希表中每个哈希桶的游标；
83.还包括：
84.第一设置单元，用于第二设置模块将当前时刻的遍历游标的高位加一，并向当前时刻的遍历游标的低位进位，得到下一时刻的遍历游标，第一判断模块判断下一时刻的遍历游标是否为0之前，按照保持遍历游标值不变的规则，基于哈希桶更新后的游标来更新下一时刻的遍历游标。
85.本技术实施例提供的一种哈希表遍历系统，目标哈希表的大小为2n。
86.本技术实施例提供的一种哈希表遍历系统，游标的位数为n。
87.本技术还提供了一种哈希表遍历设备及计算机可读存储介质，其均具有本技术实施例提供的一种哈希表遍历方法具有的对应效果。请参阅图3，图3为本技术实施例提供的一种哈希表遍历设备的结构示意图。
88.本技术实施例提供的一种哈希表遍历设备，包括存储器201和处理器202，存储器201中存储有计算机程序，处理器202执行计算机程序时实现如上任一实施例所描述哈希表遍历方法的步骤。
89.请参阅图4，本技术实施例提供的另一种哈希表遍历设备中还可以包括：与处理器202连接的输入端口203，用于传输外界输入的命令至处理器202；与处理器202连接的显示单元204，用于显示处理器202的处理结果至外界；与处理器202连接的通信模块205，用于实现哈希表遍历设备与外界的通信。显示单元204可以为显示面板、激光扫描使显示器等；通信模块205所采用的通信方式包括但不局限于移动高清链接技术(hml)、通用串行总线(usb)、高清多媒体接口(hdmi)、无线连接：无线保真技术(wifi)、蓝牙通信技术、低功耗蓝牙通信技术、基于ieee802.11s的通信技术。
90.本技术实施例提供的一种计算机可读存储介质，计算机可读存储介质中存储有计算机程序，计算机程序被处理器执行时实现如上任一实施例所描述哈希表遍历方法的步骤。
91.本技术所涉及的计算机可读存储介质包括随机存储器(ram)、内存、只读存储器(rom)、电可编程rom、电可擦除可编程rom、寄存器、硬盘、可移动磁盘、cd-rom、或技术领域内所公知的任意其它形式的存储介质。
92.本技术实施例提供的哈希表遍历系统、设备及计算机可读存储介质中相关部分的说明请参见本技术实施例提供的哈希表遍历方法中对应部分的详细说明，在此不再赘述。另外，本技术实施例提供的上述技术方案中与现有技术中对应技术方案实现原理一致的部分并未详细说明，以免过多赘述。
93.还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
94.对所公开的实施例的上述说明，使本领域技术人员能够实现或使用本技术。对这
些实施例的多种修改对本领域技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本技术的精神或范围的情况下，在其它实施例中实现。因此，本技术将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。
