哈希游戏作为一种新兴的区块链应用，它巧妙地结合了加密技术与娱乐，为玩家提供了全新的体验。万达哈希平台凭借其独特的彩票玩法和创新的哈希算法，公平公正-方便快捷!万达哈希,哈希游戏平台,哈希娱乐,哈希游戏

　　(73)专利权人北京云杉世纪网络科技有限公司地址100083北京市海淀区成府路28号12

　　本发明实施例提供一种GC程序语言中哈希表的实现方法及装置,方法包括,若哈希表的矩阵中最后一个对象位于矩阵中对象块数组的最后位置,则创建一个新对象块数组,并将新对象块数组插入到所述矩阵的最后一行的下方,获取新对象块数组位于矩阵中的行号,将哈希表的索引数组中与行号相同的下标位置指向新对象块数组,并将新对象块数组的起始位置的元素初始化为待插入对象,若哈希表的矩阵中的最后一个对象不位于对象块数组的最后位置,则将最后一个对象所在位置的后一个位置的元素初始化为所述待插入对象。本发明实施例降低了内存申请和释放的频率,降低了堆内存中对象的数量,使得哈希表的性能得到显著提升。

　　若哈希表的矩阵中最后一个对象位于所述矩阵中对象块数组的最后位置,则创建一个新对象块数组,并将所述新对象块数组插入到所述矩阵的最后一行的下方,

　　获取所述新对象块数组位于所述矩阵中的行号,将所述哈希表的索引数组中与所述行号相同的下标位置指向所述新对象块数组,并将所述新对象块数组的起始位置的元素初始化为待插入对象,

　　若所述哈希表的矩阵中的最后一个对象不位于所述对象块数组的最后位置,则将所述最后一个对象所在位置的后一个位置的元素初始化为所述待插入对象,

　　将所述哈希表的索引数组中与所述行号相同的下标位置指向所述新对象块数组的步骤还包括,

　　若所述索引数组的长度小于或等于所述新对象块数组位于所述矩阵中的行号,则创建一个新的索引数组,其中,所述新的索引数组的长度大于原来的索引数组的长度,

　　将原来的索引数组的内容复制到所述新的索引数组中,并将所述新的索引数组中与所述行号相同的下标位置指向所述新对象块数组。

　　2.根据权利要求1所述的GC程序语言中哈希表的实现方法,其特征在于,若哈希表的矩阵中最后一个对象位于所述矩阵中对象块数组的最后位置,则创建一个新对象块数组的步骤之前还包括,

　　计算所述待插入对象的Key值的哈希值,根据所述哈希值定位所述待插入对象在哈希表的哈希桶中的位置,

　　遍历访问所述哈希表的链表的所述位置,若所述位置不存在所述待插入对象,则判断所述哈希表的矩阵中的最后一个对象是否位于所述对象块数组的最后位置。

　　3.根据权利要求1或2所述的GC程序语言中哈希表的实现方法,其特征在于,还包括,

　　计算待删除对象的Key值的哈希值,根据所述待删除对象的Key值的哈希值定位所述待删除对象在哈希表的哈希桶中的位置,

　　遍历访问所述待删除对象在所述哈希表的链表的所述位置,若所述位置存在所述待删除对象,则将所述待删除对象和所述矩阵中的最后一个对象互换,

　　若所述待删除对象互换后的位置为所述对象块数组的起始位置,则销毁所述待删除对象互换后所在的对象块数组。

　　4.根据权利要求3所述的GC程序语言中哈希表的实现方法,其特征在于,销毁所述待删除对象互换后所在的对象块数组的步骤之后还包括,

　　若所述索引数组的长度减去所述待删除对象互换后位于所述矩阵的行号大于预设阈值,则创建一个新的索引数组,其中,所述新的索引数组的长度小于原来的索引数组的长度,

　　将原来的索引数组的内容复制到所述新的索引数组中,并将所述新的索引数组中与所述待删除对象互换后位于所述矩阵的行号相同的下标位置指向空。

　　5.根据权利要求3所述的GC程序语言中哈希表的实现方法,其特征在于,将所述待删除对象和所述矩阵中的最后一个对象互换的步骤之后还包括,

　　若所述待删除对象互换后的位置不为所述对象块数组的起始位置,则删除互换后的所述待删除对象。

　　6.根据权利要求1或2所述的GC程序语言中哈希表的实现方法,其特征在于,还包括,

　　计算待查找对象的Key值的哈希值,根据所述待查找对象的Key值的哈希值定位所述待查找对象在哈希表的哈希桶中的位置,

　　遍历访问所述待查找对象在所述哈希表的链表的所述位置,若所述位置存在所述待查找对象,则将所述待查找对象返回。

　　创建模块,用于在哈希表的矩阵中最后一个对象位于所述矩阵中对象块数组的最后位置时,创建一个新对象块数组,并将所述新对象块数组插入到所述矩阵的最后一行的下方,

　　插入模块,用于获取所述新对象块数组位于所述矩阵中的行号,将所述哈希表的索引数组中与所述行号相同的下标位置指向所述新对象块数组,并将所述新对象块数组的起始位置的元素初始化为待插入对象,

　　若所述哈希表的矩阵中的最后一个对象不位于所述对象块数组的最后位置,则将所述最后一个对象所在位置的后一个位置的元素初始化为所述待插入对象,

　　若所述索引数组的长度小于或等于所述新对象块数组位于所述矩阵中的行号,则创建一个新的索引数组,其中,所述新的索引数组的长度大于原来的索引数组的长度,

　　将原来的索引数组的内容复制到所述新的索引数组中,并将所述新的索引数组中与所述行号相同的下标位置指向所述新对象块数组。

　　8.一种电子设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,其特征在于,所述处理器执行所述程序时实现如权利要求1至6任一项所述GC程序语言中哈希表的实现方法的步骤。

　　9.一种非暂态计算机可读存储介质,其上存储有计算机程序,其特征在于,该计算机程序被处理器执行时实现如权利要求1至6任一项所述GC程序语言中哈希表的实现方法的步骤。

　　[0001 ] 本发明属于计算机数据结构技术领域,尤其涉及一种GC程序语言中哈希表的实现方法及装置。

　　[0002] 在GC(Garbage Collection,垃圾回收)程序语言中,对象的高频构造和销毁会由于周期性的垃圾回收引发巨大的程序执行开销。例如在Golang语言中,高频构造和销毁的对象会在堆空间上占据大量的零散内存空间,并在每隔2分钟的垃圾回收发生时导致整个程序长时间锁定无法执行堆内存访问指令。

　　[0003] 哈希表是程序设计语言中重要的数据结构,如Golang的map和Java的HashMap等,用于实现对象的快速查找。在GC程序语言中,哈希表中对象的高频插入和删除会导致大量堆空间上的对象被频繁创建和销毁,周期性执行的GC操作锁定整个堆空间时也会由于对象数量庞大而长时间锁定,进而导致哈希表此时的查询性能显著降低。

　　[0004] 由于哈希表是一个非常经典的数据结构,因此其实现方式在各种语言中大同小异。简单来讲,通过一个数组H存储哈希值对应的链表表头,该数组称之为哈希桶。插入、删除、查询操作会先通过对对象的Key进行哈希计算,定位到在H数组中的下标,并扫描该下标位置指向的链表判断是否存在该对象及是否需要增删该对象。

　　[0005] 以Golang为例,它使用传统的哈希表实现方法,在向哈希表插入对象时,会在堆空间上生成一个对象,删除一个对象时会从堆空间中标记该对象已不再被哈希表使用。由于堆空间中的GC会定期检查堆空间所有对象,若没有被任何代码使用则将其最终释放。

　　[0006] 在高频插入和删除操作时,对象的申请和释放使得GC会面对一个由大量零碎对象构成的堆空间,对哈希表的频繁操作会显著影响哈希表的整体性能。

　　[0007] 为克服上述现有的哈希表实现方法对哈希表频繁操作影响哈希表性能的问题或者至少部分地解决上述问题,本发明实施例提供一种GC程序语言中哈希表的实现方法及装置。

　　[0008] 根据本发明实施例的第一方面,提供一种GC程序语言中哈希表的实现方法,包括,

　　[0009] 若哈希表的矩阵中最后一个对象位于所述矩阵中对象块数组的最后位置,则创建一个新对象块数组,并将所述新对象块数组插入到所述矩阵的最后一行的下方,

　　[0010] 获取所述新对象块数组位于所述矩阵中的行号,将所述哈希表的索引数组中与所述行号相同的下标位置指向所述新对象块数组,并将所述新对象块数组的起始位置的元素初始化为待插入对象,

　　[001 1 ] 若所述哈希表的矩阵中的最后一个对象不位于所述对象块数组的最后位置,则将所述最后一个对象所在位置的后一个位置的元素初始化为所述待插入对象。

　　[0012] 具体地,若哈希表的矩阵中最后一个对象位于所述矩阵中对象块数组的最后位

　　[0013] 计算所述待插入对象的Key值的哈希值,根据所述哈希值定位所述待插入对象在哈希表的哈希桶中的位置,

　　[0014] 遍历访问所述哈希表的链表的所述位置,若所述位置不存在所述待插入对象,则判断所述哈希表的矩阵中的最后一个对象是否位于所述对象块数组的最后位置。

　　[0015] 具体地,将所述哈希表的索引数组中与所述行号相同的下标位置指向所述新对象块数组的步骤还包括,

　　[0016] 若所述索引数组的长度小于或等于所述新对象块数组位于所述矩阵中的行号,则创建一个新的索引数组,其中,所述新的索引数组的长度大于原来的索引数组的长度,

　　[0017] 将原来的索引数组的内容复制到所述新的索引数组中,并将所述新的索引数组中与所述行号相同的下标位置指向所述新对象块数组。

　　[0019] 计算待删除对象的Key值的哈希值,根据所述待删除对象的Key值的哈希值定位所述待删除对象在哈希表的哈希桶中的位置,

　　[0020] 遍历访问所述待删除对象在所述哈希表的链表的所述位置,若所述位置存在所述待删除对象,则将所述待删除对象和所述矩阵中的最后一个对象互换,

　　[0021 ] 若所述待删除对象互换后的位置为所述对象块数组的起始位置,则销毁所述待删除对象互换后所在的对象块数组。

　　[0022] 具体地,销毁所述待删除对象互换后所在的对象块数组的步骤之后还包括,

　　[0023] 若所述索引数组的长度减去所述待删除对象互换后位于所述矩阵的行号大于预设阈值,则创建一个新的索引数组,其中,所述新的索引数组的长度小于原来的索引数组的长度,

　　[0024] 将原来的索引数组的内容复制到所述新的索引数组中,并将所述新的索引数组中与所述待删除对象互换后位于所述矩阵的行号相同的下标位置指向空。

　　[0025] 具体地,将所述待删除对象和所述矩阵中的最后一个对象互换的步骤之后还包括,

　　[0026] 若所述待删除对象互换后的位置不为所述对象块数组的起始位置,则删除互换后的所述待删除对象。

　　[0028] 计算待查找对象的Key值的哈希值,根据所述待查找对象的Key值的哈希值定位所述待查找对象在哈希表的哈希桶中的位置,

　　[0029] 遍历访问所述待查找对象在所述哈希表的链表的所述位置,若所述位置存在所述待查找对象,则将所述待查找对象返回。

　　[0030] 根据本发明实施例第二方面提供一种GC程序语言中哈希表的实现装置,包括,

　　[0031 ] 创建模块,用于在哈希表的矩阵中最后一个对象位于所述矩阵中对象块数组的最后位置时,创建一个新对象块数组,并将所述新对象块数组插入到所述矩阵的最后一行的下方,

　　[0032] 插入模块,用于获取所述新对象块数组位于所述矩阵中的行号,将所述哈希表的索引数组中与所述行号相同的下标位置指向所述新对象块数组,并将所述新对象块数组的

　　[0033] 若所述哈希表的矩阵中的最后一个对象不位于所述对象块数组的最后位置,则将所述最后一个对象所在位置的后一个位置的元素初始化为所述待插入对象。

　　[0034] 根据本发明实施例的第三个方面,还提供一种电子设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,所述处理器调用所述程序指令能够执行第一方面的各种可能的实现方式中任一种可能的实现方式所提供的GC程序语言中哈希表的实现方法。

　　[0035] 根据本发明实施例的第四个方面,还提供一种非暂态计算机可读存储介质,所述非暂态计算机可读存储介质存储计算机指令,所述计算机指令使所述计算机执行第一方面的各种可能的实现方式中任一种可能的实现方式所提供的GC程序语言中哈希表的实现方法。

　　[0036] 本发明实施例提供一种GC程序语言中哈希表的实现方法及装置,该方法通过在向哈希表插入对象时,若哈希表的矩阵中最后一个对象位于矩阵中对象块数组的最后位置,则创建一个新对象块数组,将待插入对象插入新对象块数组的起始位置,通过将对象在哈希表中以对象块的方式进行存放,使得哈希表中的内存申请单元为矩阵中的一个数组,而非单个对象,从而将内存申请的频率降低至1/Height(B) ,堆内存中对象的数量降低至1/Height(B) ,哈希表的性能得到显著提升。

　　[0037] 为了更清楚地说明本发明实施例或现有技术中的技术方案,下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍,显而易见地,下面描述中的附图是本发明的一些实施例,对于本领域普通技术人员来讲,在不付出创造性劳动的前提下,还可以根据这些附图获得其他的附图。

　　[0038] 图1为本发明实施例提供的GC程序语言中哈希表的实现方法整体流程示意图,

　　[0039] 图2为本发明实施例提供的GC程序语言中哈希表的实现方法中哈希表的架构示意图,

　　[0040] 图3为本发明实施例提供的GC程序语言中哈希表的实现装置整体结构示意图,

　　[0042] 为了更清楚地说明本发明实施例或现有技术中的技术方案,下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍,显而易见地,下面描述中的附图是本发明的一些实施例,对于本领域普通技术人员来讲,在不付出创造性劳动的前提下,还可以根据这些附图获得其他的附图。

　　[0043] 在本发明的一个实施例中提供一种GC程序语言中哈希表的实现方法,图1为本发明实施例提供的GC程序语言中哈希表的实现方法整体流程示意图,该方法包括(S101)若哈希表的矩阵中最后一个对象位于所述矩阵中对象块数组的最后位置,则创建一个新对象块数组,并将所述新对象块数组插入到所述矩阵的最后一行的下方,

　　[0044] 本实施例中的哈希表包括三个部分,即哈希桶H、多个长度相同的对象块数组构成

　　的矩阵B和一个变长索引数组I,如图2所示。其中对象块数组为由多个对象构成的对象块形成的数组。哈希表初始化时,由调用者传入H的长度LH、变长索引数组的初始长度Len(I) 、B 中每个数组的长度,即B的高度Height(B) 。初始时B中的数组个数Len(B)(1 )B[0]数组的长度等于Height(B) 。B中存储的对象以对象块的方式紧挨存放,每个对象块的长度为Height (B) ,通常Height(B)可取值为[16,256]之间的整数。初始时变长索引数组的第0个位置I[0]指向B[0] 。

　　[0046] S102,获取所述新对象块数组位于所述矩阵中的行号,将所述哈希表的索引数组中与所述行号相同的下标位置指向所述新对象块数组,并将所述新对象块数组的起始位置的元素初始化为待插入对象,

　　[0048] S103,若所述哈希表的矩阵中的最后一个对象不位于所述对象块数组的最后位置,则将所述最后一个对象所在位置的后一个位置的元素初始化为所述待插入对象。

　　[0050] 本实施例通过在向哈希表插入对象时,若哈希表的矩阵中最后一个对象位于矩阵中对象块数组的最后位置,则创建一个新对象块数组,将待插入对象插入新对象块数组的起始位置,通过将对象在哈希表中以对象块的方式进行存放,使得哈希表中的内存申请单元为矩阵中的一个数组,而非单个对象,从而将内存申请的频率降低至1/Height(B) ,堆内存中对象的数量降低至1/Height(B) ,哈希表的性能得到显著提升。

　　[0051 ] 在上述实施例的基础上,本实施例中若哈希表的矩阵中最后一个对象位于所述矩阵中对象块数组的最后位置,则创建一个新对象块数组的步骤之前还包括,计算所述待插入对象的Key值的哈希值,根据所述哈希值定位所述待插入对象在哈希表的哈希桶中的位置,遍历访问所述哈希表的链表的所述位置,若所述位置不存在所述待插入对象,则判断所述哈希表的矩阵中的最后一个对象是否位于所述对象块数组的最后位置。

　　[0052] 具体地,为了避免待插入对象的重复插入,在将待插入对象插入哈希表之前,先判断待插入对象是否在哈希表中已经存在,若不存在才对其进行插入。

　　[0053] 计算待插入对象的Key值的哈希值Hash(key) ,并定位其在H数组中的下标h。遍历访问H[h]对应的链表,若找到待插入对象则返回,否则将待插入对象插入哈希表。

　　[0054] 在上述实施例的基础上,本实施例中将所述哈希表的索引数组中与所述行号相同的下标位置指向所述新对象块数组的步骤还包括,若所述索引数组的长度小于或等于所述新对象块数组位于所述矩阵中的行号,则创建一个新的索引数组,其中,所述新的索引数组的长度大于原来的索引数组的长度,将原来的索引数组的内容复制到所述新的索引数组中,并将所述新的索引数组中与所述行号相同的下标位置指向所述新对象块数组。

　　[0055] 具体地,若I的长度小于或等于i+1 ,则生成一个比I长的新索引数组,如新I的长度为原来I的长度的两倍,并将原来I中的内容复制到新I中。将新I中的I[i+1]指向B[i+1] ,将B[i+1] [0]初始化为待插入对象的object。

　　[0056] 在上述各实施例的基础上,本实施例中还包括,计算待删除对象的Key值的哈希值,根据所述待删除对象的Key值的哈希值定位所述待删除对象在哈希表的哈希桶中的位置,遍历访问所述待删除对象在所述哈希表的链表的所述位置,若所述位置存在所述待删除对象,则将所述待删除对象和所述矩阵中的最后一个对象互换,若所述待删除对象互换后的位置为所述对象块数组的起始位置,则销毁所述待删除对象互换后所在的对象块数组。

　　[0057] 具体地,从哈希表中删除一个待删除对象key,object时,计算key的哈希值Hash (key) ,并定位其在H数组中的下标h。遍历访问H[h]对应的链表,若没找到待删除对象则返回空,若找到待删除对象,且待删除对象在B中的位置为B[i] [j] ,则将它和B矩阵中的最后一个元素B[i2] [j2]互换。若j2(0)则销毁B[i2]整个数组。若j20,则仅删除互换后的待删除对象。

　　[0058] 本实施例通过将对象在哈希表中以对象块的方式进行存放,使得哈希表中的内存释放单元为矩阵中的一个数组,而非单个对象,从而将内存释放的频率降低至1/Height (B) ,堆内存中对象的数量降低至1/Height(B) ,哈希表的性能得到显著提升。

　　[0059] 在上述实施例的基础上,本实施例中销毁所述待删除对象互换后所在的对象块数组的步骤之后还包括,若所述索引数组的长度减去所述待删除对象互换后位于所述矩阵的行号大于预设阈值,则创建一个新的索引数组,其中,所述新的索引数组的长度小于原来的索引数组的长度,将原来的索引数组的内容复制到所述新的索引数组中,并将所述新的索引数组中与所述待删除对象互换后位于所述矩阵的行号相同的下标位置指向空。

　　[0060] 具体地,若i2远小于I数组的长度,如i2小于I数组长度的1/4,则生成一个比I短的新数组,如为原来I数组长度的1/2,并将原来I中的内容复制到新的I数组中,并将I[i2]指向空。

　　[0061 ] 在上述各实施例的基础上,本实施例中还包括,计算待查找对象的Key值的哈希值,根据所述待查找对象的Key值的哈希值定位所述待查找对象在哈希表的哈希桶中的位置,遍历访问所述待查找对象在所述哈希表的链表的所述位置,若所述位置存在所述待查找对象,则将所述待查找对象返回。

　　[0062] 具体地,从哈希表中查询一个待查询对象key,object时,计算待查找对象的Key 值的哈希值Hash(key) ,并定位其在H数组中的下标h。遍历访问H[h]对应的链表,若找到待查询对象则返回。

　　[0063] 在本发明的另一个实施例中提供一种GC程序语言中哈希表的实现装置,该装置用于实现前述各实施例中的方法。因此,在前述GC程序语言中哈希表的实现方法的各实施例中的描述和定义,可以用于本发明实施例中各个执行模块的理解。图3为本发明实施例提供的GC程序语言中哈希表的实现装置整体结构示意图,该装置包括创建模块301和插入模块

　　[0064] 创建模块,用于在哈希表的矩阵中最后一个对象位于所述矩阵中对象块数组的最后位置时,创建一个新对象块数组,并将所述新对象块数组插入到所述矩阵的最后一行的下方,

　　[0065] 插入模块,用于获取所述新对象块数组位于所述矩阵中的行号,将所述哈希表的索引数组中与所述行号相同的下标位置指向所述新对象块数组,并将所述新对象块数组的

　　[0066] 若所述哈希表的矩阵中的最后一个对象不位于所述对象块数组的最后位置,则将所述最后一个对象所在位置的后一个位置的元素初始化为所述待插入对象。

　　[0067] 本实施例通过在向哈希表插入对象时,若哈希表的矩阵中最后一个对象位于矩阵中对象块数组的最后位置,则创建一个新对象块数组,将待插入对象插入新对象块数组的起始位置,通过将对象在哈希表中以对象块的方式进行存放,使得哈希表中的内存申请单元为矩阵中的一个数组,而非单个对象,从而将内存申请的频率降低至1/Height(B) ,堆内存中对象的数量降低至1/Height(B) ,哈希表的性能得到显著提升。

　　[0068] 在上述实施例的基础上,本实施例中还包括判断模块,用于计算所述待插入对象的Key值的哈希值,根据所述哈希值定位所述待插入对象在哈希表的哈希桶中的位置,遍历访问所述哈希表的链表的所述位置,若所述位置不存在所述待插入对象,则判断所述哈希表的矩阵中的最后一个对象是否位于所述对象块数组的最后位置。

　　[0069] 在上述实施例的基础上,本实施例中插入模块还用于,若所述索引数组的长度小于或等于所述新对象块数组位于所述矩阵中的行号,则创建一个新的索引数组,其中,所述新的索引数组的长度大于原来的索引数组的长度,将原来的索引数组的内容复制到所述新的索引数组中,并将所述新的索引数组中与所述行号相同的下标位置指向所述新对象块数组。