HASH GAME - Online Skill Game GET 300

　　即时通讯(IM，Instant Messaging)工具由于具有准入技术低，可以即时通过较少的语句来表达自己情感，与关注自己的用户分享，因而，信息传递的效率较高，其应用也越来越广泛。现有的即时通讯用户收听人列表在理论上没有任何限制，用户通过各类客户端就可以实时接收到自己关注的收听人发表或者转播的消息，因此，对应接收到的消息数据数量将十分庞大，如何对接收的消息等数据进行有效地存储以及对存储的数据进行快速地查询，是即时通讯技术发展亟需解决的技术问题。现有技术中，即时通讯客户端常采用哈希(Hash)算法，利用Hash表来实现对数据的快速存储，Hash算法一般包括循环冗余校验码(CRC，Cyclic Redundancy Check)算法 32、信息-摘要算法(Message-Digest Algorithm) 5 以及安全哈希算法(SHA，Secure Hash Algorithm)，采用Hash算法对数据串进行数字化后生成一个主键(Key)值，再用Key值对一个较大的质数M取余，这样，可以使数据均勻地分布在大小为M的Hash表上。图1为现有技术基于哈希算法的数据存储结构示意图。参见图1，利用Hash算法， 例如，Md5对数据进行数字化后取前8字节生成一个Key值，将该Key值对预先设定的一个较大的质数M取余，然后将该数据及其对应的Key值存储至取余映射的Hash表中，M可根据实际需要以及对数据进行Hash后得到的Key值确定。当对数据进行Hash后得到的Key值相同时，即主键值发生冲突，则在Hash表中采用链表的方式将Key值相同的所有的数据组织起来，如图1中datalOO datal02，其Key 值对M取余后为10，datallO datall3，其Key值对M取余后为11，则分别以链表的方式依次存储。当用户需要查询数据时，首先对需要查询的数据利用Hash算法进行处理，得到 Key值，接着对存储的Hash表采用的质数M进行取余定位该数据在Hash表中的位置，然后在定位的位置查询获取Key值对应的数据并向用户返回相应信息。由上述可见，由于将所有数据存储在一张Hash表中，所需存储空间大，对存储设备要求高；同时，对于存储时发生冲突的主键值对应的数据，Hash表采用链表的方式进行存储，每个数据具有相同的主键值，造成后续查询和读取的困难，而对于未发生冲突的主键值对应的数据，还需要为Hash表预留与发生冲突的主键值时对应的存储空间，以及，需要在采用质数M的Hash表中进行遍历，以确定没有相同的数据时才能进行存储，使得存储效率较低；进一步地，对于Hash表中存储的未发生冲突的数据，其查询的复杂度(效率)与 Hash表采用的质数M相关，而对于Hash表中存储的发生冲突的数据，查询数据的复杂度是 O(n)，其中η是冲突链表上存储的数据个数，例如，以查询图1中数据datalll为例，首先获取datalll的Key值，接着，计算Key1^M,获取其取余位置，即索引位置，也就是图1中的11 位置处，然后在索引位置的链表上进行遍历，直到查询的数据与Hash表中存储的datalll 匹配为止。这样，数据访问速度慢、访问复杂度高、查询效率低。

　　有鉴于此，本发明的主要目的在于提出一种基于哈希算法的数据存储方法，降低存储设备要求、提高存储效率。本发明的另一目的在于提出一种基于哈希算法的数据存储装置，降低存储设备要求、提高存储效率。为达到上述目的，本发明提供了一种基于哈希算法的数据存储方法，该方法包括预先设置L个后端存储模块以及后端存储模块标识与模L运算的映射关系，L为大于1的自然数；根据Hash算法计算待存储数据的主键值；对获取的主键值以后端存储模块数量为模执行模运算，根据后端存储模块标识与模L运算的映射关系，将执行模L运算的主键值及对应的数据输出至相应标识的后端存储模块；确定后端存储模块预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值。所述确定后端存储模块预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值具体包括依序判断后端存储模块预先设置的Hash表中是否存储有待存储数据对应的主键值，如果没有，在该Hash表中存储该主键值以及该主键值对应的数据；否则，将Hash表中存储的数据与该主键值对应的数据进行匹配；判断Hash表中存储的数据与该主键值对应的数据不相匹配，对Hash表中存储的数据设置冲突标记，将该主键值加上预先设置的步长；判断加上预先设置的步长的次数没有超过预先设置的阈值，返回执行所述依序判断后端存储模块预先设置的Hash表中是否存储有待存储数据对应的主键值的步骤。所述预先设置的步长与预先设置的步长的次数的乘积模后端存储模块数量的余数为0。进一步包括所述后端存储模块的数量以每次翻倍的方式进行扩容。进一步包括根据查询请求获取查询请求对应的主键值；对获取的主键值以后端存储模块数量为模执行模运算，根据后端存储模块标识与模L运算的映射关系，获取主键值对应的后端存储模块；搜索Hash表，获取待查询数据。所述根据查询请求获取查询请求对应的主键值具体包括获取查询请求，判断查询请求中携带的是数据还是已经标识化的主键值，如果是数据，计算该数据对应的主键值，将计算得到的主键值作为查询请求对应的主键值；如果是已经标识化的主键值，将该标识化的主键值作为查询请求对应的主键值。当所述查询请求中携带的是数据时，所述搜索Hash表，获取待查询数据具体包括搜索Hash表，确定有待查询数据对应的主键值；判断存储的该主键值对应的数据结构中是否置有冲突标记，如果没有，返回查询请求成功信息，携带该主键值对应的数据；如果有，将当前带查询数据对应的主键值加上预先设置的步长；确定加上预先设置的步长的次数没有超过预先设置的阈值，返回执行所述搜索 Hash表，确定有待查询数据对应的主键值的步骤。当所述查询请求中携带的是标识化的主键值时，所述搜索Hash表，获取待查询数据具体包括搜索Hash表中是否有标识化的主键值，如果有，返回查询请求成功信息，携带该标识化的主键值对应的数据。一种基于哈希算法的数据存储装置，该装置包括多个后端存储模块、映射关系存储模块、主键值计算模块以及模运算单元，其中，映射关系存储模块，用于存储后端存储模块标识与模L运算的映射关系，L为后端存储模块数量；主键值计算模块，用于根据Hash算法计算待存储数据的主键值，输出至模运算单元；模运算单元，用于根据后端存储模块数量，对获取的主键值取模，根据取模的余数从映射关系存储模块获取取模的余数映射的后端存储模块标识，将执行取模运算的主键值及对应的数据输出至相应标识的后端存储模块；后端存储模块，用于确定预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值。所述后端存储模块为随机存储器、闪存、可擦写存储器或硬盘。所述后端存储模块包括主键值查询单元、Hash表存储单元、数据匹配单元以及主键值冲突处理单元，其中，主键值查询单元，用于依序判断Hash表中是否存储有待存储数据对应的主键值， 如果没有，将该主键值以及该主键值对应的数据输出至Hash表中进行存储；如果有，将该主键值以及该主键值对应的数据输出至数据匹配单元；数据匹配单元，用于将接收的数据与Hash表中存储的数据进行匹配，如果相同， 不作处理；否则，对存储的数据设置冲突标记，将该主键值输出至主键值冲突处理单元；主键值冲突处理单元，用于将接收的主键值加上预先设置的步长，判断加上预先设置的步长的次数是否超过预先设置的阈值，如果是，不作处理；否则，将加上预先设置步长的主键值输出至主键值查询单元。由上述的技术方案可见，本发明提供的一种基于哈希算法的数据存储方法及装置，通过预先设置L个后端存储模块以及后端存储模块标识与模L运算的映射关系；根据 Hash算法计算待存储数据的主键值；对获取的主键值以后端存储模块数量为模执行模运算，根据后端存储模块标识与模L运算的映射关系，将执行模L运算的主键值及对应的数据

　　图1为现有技术基于哈希算法的数据存储结构示意图。图2为本发明实施例基于哈希算法的数据存储方法流程示意图。图3为本发明实施例根据数据主键值以及后端存储模块数量选择用于存储数据的后端存储模块的示意图。图4为本发明实施例Hash表的结构示意图。图5为本发明实施例确定后端存储模块预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值流程示意图。图6为本发明实施例查询数据的流程示意图。图7为本发明实施例基于哈希算法的数据存储装置结构示意图。

　　为使本发明的目的、技术方案和优点更加清楚，下面将结合附图及具体实施例对本发明作进一步地详细描述。本发明实施例中，采用分布式存储方法，对待存储的数据进行分类，将分类的数据分别存储至对应的分布式存储装置中以降低对装置的存储空间要求；同时，对于现有发生冲突的主键值对应的数据，本发明实施例采用特定的方式生成Hash的主键值并设置冲突次数，使得每个数据对应的主键值唯一以提高后续查询的效率。图2为本发明实施例基于哈希算法的数据存储方法流程示意图。参见图2，该流程包括步骤201，预先设置多个后端存储模块以及后端存储模块标识与模L运算的映射关系，L为后端存储模块数量；本步骤中，后端存储模块可以是随机存储器、闪存、可擦写存储器、硬盘等内置于客户端的存储单元，也可以是外置的相互独立的服务器。较佳地，后端存储模块的数量为质数(L)个，例如，对于设置的3个后端存储模块， 其对应的标识可以分别为0、1、2。后端存储模块标识与模L运算的映射关系可以是，如果模 L运算的余数为0的数据，则对应标识为0的后端存储模块，余数为1的数据对应标识为1 的后端存储模块，以此类推。步骤202，根据Hash算法计算待存储数据的主键值KEY ；本步骤中，Hash算法般包括CRC 32、MD5以及SHA，本发明实施例中，采用MD5算

　　法进行运算。步骤203，对获取的主键值以后端存储模块数量为模执行模运算，根据后端存储模块标识与模L运算的映射关系，将执行模L运算的主键值及对应的数据输出至相应标识的后端存储模块；本步骤中，根据步骤202获取的主键值KEY，以后端存储模块数量(L)执行模运算，即对后端存储模块数量进行取余，通过KEY MOD L来选择相应的后端服务器。图3为本发明实施例根据数据主键值以及后端存储模块数量选择用于存储数据的后端存储模块的示意图。参见图3，以N = 3为例，将Key mod 3 == 0对应的主键值及主键值对应的数据输出至后端存储模块0中，将Key mod 3 = = 1对应的主键值及主键值对应的数据输出至后端存储模块1中，将Key mod 3 = = 2对应的主键值及主键值对应的数据输出至后端存储模块2中。步骤204，确定后端存储模块预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值。本步骤中，确定Hash表中没有存储与主键值匹配的数据且与待存储数据相同的数据，存储该主键值及对应的数据。后端存储模块预先设置的Hash表个数为质数，其中，质数可以取较大值，Hash表根据预设的质数采用多个Hash桶并排的方式。图4为本发明实施例Hash表的结构示意图。参见图4，Hash表采用3个Hash桶并排的方式，即Hash表的桶数为3，标识分别为0、3、6，每个Hash桶的深度为5。图5为本发明实施例确定后端存储模块预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值流程示意图。参见图5，该流程包括步骤501，依序判断后端存储模块预先设置的Hash表中是否存储有待存储数据对应的主键值，如果没有，执行步骤502，否则，执行步骤503 ；本步骤中，依序搜索后端存储模块预先设置的Hash表，也就是从图4中Hash表的第一行开始依序搜索。步骤502，存储该主键值以及该主键值对应的数据；本步骤中，如果预先设置的Hash表中未存储有该主键值，表明未对该主键值对应的数据进行存储。步骤503，将Hash表中存储的数据与该主键值对应的数据进行匹配，如果相同，结束流程，否则，对Hash表中存储的数据设置冲突标记(Flag)，将该主键值加上预先设置的步长；本步骤中，如果Hash表中存储有该主键值，表明Hash表中已对该主键值对应的数据进行过存储，则需要进一步判断存储的数据与待存储的数据是否匹配，如果匹配，表明存储的数据即为待存储的数据，不需要再行存储，如果不匹配，表明存储的数据对应的主键值与待存储的数据对应的主键值发生冲突，需要对待存储的数据对应的主键值进行重新设置以便可以唯一标识该待存储的数据。同时在与待存储的数据发生冲突的存储的数据结构中置一个冲突标记flag，表示该存储的数据曾经冲突过。504，判断加上预先设置的步长的次数是否超过预先设置的阈值，如果是，结束流程，否则，返回执行步骤501。本步骤中，预先设置的步长与预先设置的步长的次数的乘积与预设的后端存储模块数量取余的余数为0。即Key mod N= (Key+m*step)modN,或(m*st 印)modN = 0式中，Key为待存储数据对应的主键值；

　　N为后端存储模块数量；m为预先设置的步长的次数；St印为预先设置的步长。至此，基于哈希算法的数据存储方法流程结束。由上述可见，本发明实施例的基于哈希算法的数据存储方法，采用分布式存储方法，预先设置多个后端存储模块，根据待存储数据的主键值以及后端存储模块的个数对待存储的数据进行分类，将分类的数据分别存储至对应的后端存储模块，降低了对装置的存储空间要求；同时，对于存储时发生冲突的主键值对应的数据，Hash表采用步长递进的方式进行存储，使得每个存储的数据具有唯一的主键值，并能保证在分布式系统中，冲突的数据能够部署在同一后端存储模块上以便于后续查询和读取；进一步地，Hash表中桶的深度为设置的步长的次数，有效减少了 Hash表存储所需的空间。本发明实施例中，当需要对数据存储进行平行扩容时，例如，增加并行的后端存储模块个数，只需要满足增加的后端存储模块个数为初始后端存储模块个数的倍数关系即可，并将待存储数据对应的主键值以更新后的后端存储模块数量执行模运算，举例来说，后端存储模块L以每次翻倍的方式扩容，则满足(m*st印)mod(2n*L) = 0 (η = 0,1,2,3...), 根据该式可以确定步长，当步长确定后，数据存储的平行扩容方案也就可以确定，可以有效地满足平行扩容情况下的需求。下面再对后续用户查询数据的流程进行说明。图6为本发明实施例查询数据的流程示意图。参见图6，该流程包括步骤600，获取查询请求，判断查询请求中携带的是数据还是已经标识化的主键值，如果是数据，执行步骤601，如果是已经标识化的主键值，执行步骤611 ；本步骤中，判断查询请求中携带的是数据还是已经标识化的主键值，属于现有技术，具体可参见相关技术文献，在此不再赘述。步骤601，根据Hash算法计算待查询数据的主键值；步骤602，对获取的主键值以后端存储模块数量执行模运算，根据后端存储模块标识与模运算的映射关系，获取主键值对应的后端存储模块；本步骤中，根据获取的主键值，对后端存储模块数量进行取余，从而获取主键值对应的数据所存储的后端存储模块地址。步骤603，依序搜索Hash表中是否有待查询数据对应的主键值，如果没有，执行步骤604，否则，执行步骤605 ；步骤604，返回查询请求失败信息，结束流程；本步骤中，如果在Hash表中没有搜索到待查询数据对应的主键值，表明该待查询数据没有存储在Hash表中。步骤605，判断存储的该主键值对应的数据结构中是否置有冲突标记，如果没有， 执行步骤606，否则，执行步骤607 ；步骤606，返回查询请求成功信息，携带该主键值对应的数据；步骤607，将当前带查询数据对应的主键值加上预先设置的步长；本步骤中，Key = Key+st印。步骤608，判断加上预先设置的步长的次数是否超过预先设置的阈值，如果是，执行步骤609，否则，返回执行步骤603。步骤609，返回查询请求失败信息，结束流程；步骤611，对标识化的主键值以后端存储模块数量执行模运算，根据后端存储模块标识与模运算的映射关系，获取主键值对应的后端存储模块；步骤612，搜索Hash表中是否有标识化的主键值，如果没有，执行步骤613，否则， 执行步骤614;步骤613，返回查询请求失败信息，结束流程；步骤614，返回查询请求成功信息，携带该标识化的主键值对应的数据。至此，该查询数据的流程结束。由上可见，本实施例的查询数据的方法，由于采用分布式Hash算法，首先根据查询数据对应的主键值选取查询的后端存储模块标识，再通过相应后端存储模块中的Hash 表进行搜索查询，有效减少了查询的复杂度，提高了数据访问速度对于数据的查询请求， 在发生Hash冲突的情况下，其查询的复杂度为0(m)，其中，m为预先设置的步长的次数，因而， 可以极大地提高查询响应速度；而对于标识化的主键值查询请求，其查询复杂度为0(1)。图7为本发明实施例基于哈希算法的数据存储装置结构示意图。参见图7，该装置包括多个后端存储模块、映射关系存储模块、主键值计算模块、模运算单元，其中，映射关系存储模块，用于存储后端存储模块标识与模L运算的映射关系；主键值计算模块，用于根据Hash算法计算待存储数据的主键值KEY，输出至模运算单元；模运算单元，用于根据后端存储模块数量，对获取的主键值取模，根据取模的余数从映射关系存储模块获取取模的余数映射的后端存储模块标识，将执行取模运算的主键值及对应的数据输出至相应标识的后端存储模块；后端存储模块，用于确定预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值。本发明实施例中，后端存储模块可以是随机存储器、闪存、可擦写存储器或硬盘。后端存储模块包括主键值查询单元、Hash表存储单元、数据匹配单元以及主键值冲突处理单元，其中，主键值查询单元，用于依序判断Hash表存储单元Hash表中是否存储有待存储数据对应的主键值，如果没有，将该主键值以及该主键值对应的数据输出至Hash表进行存储；如果有，将该主键值以及该主键值对应的数据输出至数据匹配单元；数据匹配单元，用于将接收的数据与Hash表存储单元Hash表中存储的数据进行匹配，如果相同，不作处理；否则，对存储的数据设置冲突标记，将该主键值输出至主键值冲突处理单元；主键值冲突处理单元，用于将接收的主键值加上预先设置的步长，判断加上预先设置的步长的次数是否超过预先设置的阈值，如果是，不作处理；否则，将加上预先设置步长的主键值输出至主键值查询单元。以上所述仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换以及改进等，均应包含在本发明的保护范围之内。

　　1.一种基于哈希算法的数据存储方法，其特征在于，该方法包括预先设置L个后端存储模块以及后端存储模块标识与模L运算的映射关系，L为大于1 的自然数；根据Hash算法计算待存储数据的主键值；对获取的主键值以后端存储模块数量为模执行模运算，根据后端存储模块标识与模 L运算的映射关系，将执行模L运算的主键值及对应的数据输出至相应标识的后端存储模块；确定后端存储模块预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值。

　　2.如权利要求1所述的方法，其特征在于，所述确定后端存储模块预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值具体包括依序判断后端存储模块预先设置的Hash表中是否存储有待存储数据对应的主键值， 如果没有，在该Hash表中存储该主键值以及该主键值对应的数据；否则，将Hash表中存储的数据与该主键值对应的数据进行匹配；判断Hash表中存储的数据与该主键值对应的数据不相匹配，对Hash表中存储的数据设置冲突标记，将该主键值加上预先设置的步长；判断加上预先设置的步长的次数没有超过预先设置的阈值，返回执行所述依序判断后端存储模块预先设置的Hash表中是否存储有待存储数据对应的主键值的步骤。

　　7.如权利要求6所述的方法，其特征在于，当所述查询请求中携带的是数据时，所述搜索Hash表，获取待查询数据具体包括搜索Hash表，确定有待查询数据对应的主键值；判断存储的该主键值对应的数据结构中是否置有冲突标记，如果没有，返回查询请求成功信息，携带该主键值对应的数据；如果有，将当前带查询数据对应的主键值加上预先设置的步长；确定加上预先设置的步长的次数没有超过预先设置的阈值，返回执行所述搜索Hash表，确定有待查询数据对应的主键值的步骤。

　　9.一种基于哈希算法的数据存储装置，其特征在于，该装置包括多个后端存储模块、 映射关系存储模块、主键值计算模块以及模运算单元，其中，映射关系存储模块，用于存储后端存储模块标识与模L运算的映射关系，L为后端存储模块数量；主键值计算模块，用于根据Hash算法计算待存储数据的主键值，输出至模运算单元；模运算单元，用于根据后端存储模块数量，对获取的主键值取模，根据取模的余数从映射关系存储模块获取取模的余数映射的后端存储模块标识，将执行取模运算的主键值及对应的数据输出至相应标识的后端存储模块；后端存储模块，用于确定预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值。

　　11.如权利要求9所述的装置，其特征在于，所述后端存储模块包括主键值查询单元、 Hash表存储单元、数据匹配单元以及主键值冲突处理单元，其中，主键值查询单元，用于依序判断Hash表中是否存储有待存储数据对应的主键值，如果没有，将该主键值以及该主键值对应的数据输出至Hash表中进行存储；如果有，将该主键值以及该主键值对应的数据输出至数据匹配单元；数据匹配单元，用于将接收的数据与Hash表中存储的数据进行匹配，如果相同，不作处理；否则，对存储的数据设置冲突标记，将该主键值输出至主键值冲突处理单元；主键值冲突处理单元，用于将接收的主键值加上预先设置的步长，判断加上预先设置的步长的次数是否超过预先设置的阈值，如果是，不作处理；否则，将加上预先设置步长的主键值输出至主键值查询单元。

　　本发明公开了一种基于哈希算法的数据存储方法及装置。包括预先设置L个后端存储模块以及后端存储模块标识与模L运算的映射关系；根据Hash算法计算待存储数据的主键值；对获取的主键值以后端存储模块数量为模执行模运算，根据后端存储模块标识与模L运算的映射关系，将执行模L运算的主键值及对应的数据输出至相应标识的后端存储模块；确定后端存储模块预先设置的Hash表中没有存储待存储数据，存储待存储数据及对应的主键值。应用本发明，可以降低存储设备要求、提高存储效率。