利用映射关系存储数据的方法
专利名称：利用映射关系存储数据的方法
技术领域：
本发明涉及数据存取技术，尤其涉及利用映射关系存储数据的方法。
背景技术：
目前，对数据信息进行存取的技术是一门相对较成熟的技术。系统(如计算机系统)的微处理器或其他控制设备(以下统称为处理器)可以将数据信息存储在存储器以进行保存。而且，处理器还记录相应的存储地址，当需要读取该数据信息时，处理器按照预先保存的存储地址即可获得对应的数据信息。以数组M为例，I为数组序号，M[I]为数据元素，假设I的范围为
，则处理器可以在存储器中顺序存储M[1]、M[2]、M[3]...M[10]。当存储空间不连续时，处理器需要存储数据序号I及对应的数组元素M[I]。也就是说，当某一类A中的元素和另一类B中的数据信息存在映射关系时，若希望通过A从存储器中读取与A具有映射关系的数据信息B时，处理器在存储器中需要预先保存该类数据A中的每一元素AI及对应的B类数据中BK数据信息。进一步假设A的长度为32个BIT(比特)，则A的取值范围
，若所有的从0000H至FFFFH的AI元素全部映射同一个BK，则按照现有的存储方法，处理器至少需要2^32*N个存储容量的存储空间(如图1所示)，N为BK所占的存储空间。很显然，上述数据信息存储方法造成存储空间的大量耗费。
为此，现有技术提出一种利用HASH(哈西)列表进行具有映射关系的数据存储以及对应的读取方法。先介绍如何保存具有映射关系的数据的存储方法。请参阅图2，其为现有技术中利用映射关系进行数据存储流程图。
首先进行步骤S110系统的处理器采用某一算法将A中的所有元素先映射至C类信息中的元素；然后进行步骤S120所述处理器根据C类信息的范围及所述算法确定HASH列表所占的存储空间，在存储器中分配对应空间大小的地址以存储HASH列表，而且建立C类信息中的每一元素与HASH列表中每一单元的一一对应关系；最后进行步骤S130，将数据信息B中的每一元素依次保存在HASH列表的每一单元中。
比如，A的范围为
，B中每一元素所占的存储空间为N个字节，若AI元素小于等于8888H，则映射数据信息B中的元素BK1；否则，AI元素映射数据信息B中的元素BK2。若保存具有上述映射关系的A和B，则根据上述存储方法进行存储具体过程为首先设置C类信息，建立A和C的映射关系；f(A)=C10000H<=AI<=8888HC28888H<=AI<=FFFFH]]>然后，确定和C中元素一一对应的HASH列表的单元的个数和每个单元所占的存储空间，进而确定该HASH列表所占的存储空间。每个单元的存储空间可以设置为N个字节或是(4+N)个字节，则HASH列表所占的存储空间为2*N或者2*(4+N)个字节，随后，将BK1保存在C1所对应的第一HASH列表单元中，将BK2保存在C2所对应的第二HASH列表单元中。
事实上，上述存储方法可能存在A1、A2、A3分别映射B1、B2、B3，但是根据设置的算法将A1、A2、A3多对一映射至CI，为此将C1所一一对应的第一HAHS列表单元下又设置三个子单元子单元1、子单元2、子单元3。并且每个子单元保存A信息及对应的B信息而且保存前一子单元地址和下一子单元地址。其中，子单元1可以保存A1、B1及子单元2的地址，子单元2可以保存A2、B2及子单元3的地址，子单元3可以保存A3、B3及第一HASH列表单元的地址。
按照上述方法在存储单元中保存好B中的每一数据元素。则当获得A中的某一元素时，处理器能够根据根据A从存储器中获得映射的B元素，具体包括首先，处理器以A元素为依据，根据预先设定的算法进行计算，获得C元素；然后，以C元素为入口参数找到存储器中对应的HASH列表单元，并取出HASH列表单元中的内容，若是数据信息，则取出的数据信息即为B元素；否则获得的内容是子单元1的地址信息，再以A元素为参数查找子单元，找到A元素对应的数据信息B，并将数据信息B取出。
但是，现有技术存储具有映射关系数据的方法虽然节省了存储容量，但是还是存在以下问题存取单元为所述处理器每次从存储器中读取数据的最大容量，假设每个子单元的大小为8个字节，而处理器是以64个字节为存取单位对存储器进行访问，则处理器对每个8字节单元的访问都需要64个字节，由此导致处理器存取数据的效率非常低。
发明内容
本发明的目的在于提供一种具有映射关系的数据进行存储的方法，以解决现有技术中处理器存储数据的效率低的技术问题。
为解决上述问题，本发明公开了一种利用映射关系存储数据的方法，以实现处理器根据第一类的元素从存储器中找到与所述元素具有映射关系的第二类数据，包括(1)所述处理器进行初始设置，所述初始设置包括根据处理器的存取单元设置块的容量，所述存取单元为所述处理器每次从存储器中读取数据的最大容量；(2)第一类的所有元素按照预先设置的算法分别映射至第三类的元素，并在所述存储器中生成哈西列表，而且所述哈西列表的每一单元与所述第三类中每一元素存在一一对应关系；(3)处理器在哈西列表的每一单元下设置若干具有所述容量的块，并将所述第一类元素和与所述元素具有映射关系的第二类数据保存在块中，而且满足条件所述第一类元素按照步骤(2)的算法映射的第三类元素是所述单元对应的第三类元素。
步骤(3)还包括在每一块下设置若干子单元，并且子单元的个数是由块的容量和所述子单元所占的容量所确定的，所述每一子单元用以存储一第一类元素及与之具有映射关系的第二类数据。
还包括(a)当处理器需要在所述存储器中保存新的第一类元素及与之具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素，然后判断所述存储器中与第三类元素对应的单元下的所有块下的子单元中是否有第一类元素与第二类数据的对应关系，若有，则输出重复保存；否则判断单元下所有块下是否有空闲的子单元，若有，进行步骤(c)，否则(b)；(b)在所述单元下重新设置块，并在新块的第一个子单元中进行步骤(c)；(c)将所述第一类元素及与所述第一类元素具有映射关系的第二类数据保存在所述子单元中，并输出保存成功。
当处理器需要在所述存储器中删除一第一类元素及与所述第一类元素具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素；然后在所述存储器中找到与第三类元素对应的哈西列表的单元；随后查找所述单元下的每一块下的每一子单元，若存在子单元中保存有第一类元素与第二类数据的映射关系，则将所述子单元中存储内容清空，并删除所述子单元，输出删除成功；否则输出删除失败。
若所述子单元所处的块下未设置其他子单元，则删除所述块。
所述哈西列表的每一单元是一固定大小的数组或是一固定大小的链表。
所述哈西列表的每一单元下设置若干块具体为所述单元的存储空间被分成若干存储单元，每一存储单元为一块的存储空间，或存储单元分配块的存储空间，所述单元中保存块的存储地址，所述存储地址用以查找所述块，获得块中存储内容。
所述块下设置子单元具体为所述块的存储空间中划分出一存储单元，其为一子单元的存储空间，或存储器分配子单元的存储空间，所述块中存储子单元的存储地址，所述存储地址用以查找所述子单元，获得子单元中存储的内容。
一种数据读取方法，以实现通过第一类元素从存储器中获得与所述元素具有映射关系的第二类数据，其特征在于，包括(A)处理器通过所述第一类元素按照所述算法计算第三类元素；(B)处理器在存储器的哈西列表中找到与所述第三类元素对应的单元，遍历所述单元下的所有块，判断是否找到其存储内容中包含所述第一类元素的块，若是，获得与所述第一类元素具有映射关系的第二类数据，否则，读取数据失败。
步骤(B)还包括若所述块下还设置子单元，则通过遍历所述块下的子单元的存储空间来查找所述第一类元素获得与所述第一类元素具有映射关系的第二类数据。
与现有技术相比，本发明根据处理器处理数据的能力预先设置块的容量，并且存储器以所述容量分配块，然后将数据存储在块中，当处理器以块为单元读取存储器中的数据时，大大提高了处理器的处理效率，而且也提出数据存取的速率。
图1是未使用哈西算法存储具有映射关系的数据的存储方式；图2是现有技术中利用映射关系进行数据存储流程图；图3为本发明利用映射关系存储数据的方法的流程图；图4为本发明的数据存储示意图。
具体实施例方式
以下结合附图，具体说明本发明。
请参阅图3，其为本发明利用映射关系存储数据的方法的流程图。该方法是用以实现处理器根据第一类的元素从存储器中找到与所述元素具有映射关系的第二类数据，包括S210处理器进行初始设置，所述初始设置包括根据处理器的存取单元设置块的容量，所述存取单元为所述处理器每次从存储器中读取数据的最大容量；所述块的容量等于该处理器的存储单元是本发明的一较佳实施例，从而使得处理器以块为单元进行读取数据时，处理器读取数据快且处理器的处理效率高；S220第一类的所有元素按照预先设置的算法分别映射至第三类的元素，并在所述存储器中生成哈西列表，而且所述哈西列表的每一单元与所述第三类中每一元素存在一一对应关系；由于哈西列表中的每一单元与第三类中每一元素存在一一对应关系，所以根据第三类元素的个数且每一单元应占用的存储空间即可在存储器中开辟相应存储容量作为哈西列表。哈西列表的每一单元是一固定大小的数组或是一固定大小的链表；S230处理器在哈西列表的每一单元下设置若干块，并将所述第一类元素和与所述元素具有映射关系的第二类数据保存在块中，而且满足条件所述第一类元素按照步骤S220的算法映射的第三类元素是所述单元对应的第三类元素。所述哈西更表的每一单元下设置若干块可以有两种方式第一种方式单元的存储空间被分成若干存储单元，每一存储单元为一块的存储空间，并且所述存储单元等于步骤S210中确定的块的容量；第二种方式存储器分配块的存储空间，所述单元中保存块的存储地址，所述存储地址用以查找所述块，获得块中存储内容，并且所述存储空间等于步骤S220中确定块的容量。若所述块是一链表，则所述块中还需保前一块的存储地址及后一块的存储地址。若所述块是本单元的第一个块，则所述块的前一块存储地址保存的是单元的存储地址。若所述块是本单元的最后一个块，则所述块的后一块存储地址保存的是本单元的存储地址或置空。
通过上述数据存储的方法，处理器根据自身的存取数据的能力设置了块的大小，并且将具有映射关系的第一类元素及第二类数据存储在块中。当处理器读取数据时，能够以块为单元访问存储器，不仅提高了数据读取的速率同时也提高了处理器的利用效率。
在本发明中，为了使得每一第一类元素及与之具有映射关系的第二类数据能够更清晰地保存，为此在块下又设置了子单元，比如在所述块的存储空间中划分出一存储单元，其为一子单元的存储空间，或者存储器分配子单元的存储空间，所述块中存储子单元的存储地址，所述存储地址用以查找所述子单元，获得子单元中存储的内容。每一子单元用以存储一第一类元素及具有映射关系的第二类数据。若块中的所有子单元不是处于存储器中的连续存储空间，则每一子单元中还需保存前一子单元所在的存储地址及后一子单元所在的存储地址。若所述子单元是本块的第一个子单元，则所述子单元的前一子单元存储地址保存的是块的存储地址。若所述子单元是本块的最后一个子单元，则所述子单元的后一子单元存储地址保存的是本块的存储地址或置空(请参阅图4)。
在上述数据存储的基础上，若处理器在所述存储器中保存新的第一类元素及与之具有映射关系的第二类数据，则主要按照下述步骤进行存储新增加数据(a)当处理器需要在所述存储器中保存新的第一类元素及与之具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素，然后判断所述存储器中与第三类元素对应的单元下的所有块下的子单元中是否有第一类元素与第二类数据的对应关系，若有，则输出重复保存；否则判断单元下所有块下是否有空闲的子单元，若有，进行步骤(c)，否则(b)；(b)在所述单元下重新设置块，并在新块的第一个子单元中进行步骤(c)；(c)将所述第一类元素及与所述第一类元素具有映射关系的第二类数据保存在所述子单元中，并输出保存成功。
在上述数据存储的基础上，若处理器需要在所述存储器中删除一第一类元素及与所述第一类元素具有映射关系的第二类数据时，则主要按照下述步骤进行数据删除先按照所述算法找到所述第一类元素映射的第三类元素；然后在所述存储器中找到与第三类元素对应的哈西列表的单元；随后查找所述单元下的每一块下的每一子单元，若存在子单元中保存有第一类元素与第二类数据的映射关系，则将所述子单元中存储内容清空，并删除所述子单元，输出删除成功；否则输出删除失败；若所述子单元所处的块下未设置其他子单元，则删除所述块。
在上述数据存储的基础上，处理器主要按照以下方式进行数据读取操作(A)处理器通过所述第一类元素按照所述算法计算第三类元素；(B)处理器在存储器的哈西列表中找到与所述第三类元素对应的单元，遍历所述单元下的所有块，判断是否找到其存储内容中包含所述第一类元素的块，若是，获得与所述第一类元素具有映射关系的第二类数据，否则，读取数据失败。若所述块下还设置子单元，则通过遍历所述块下的子单元的存储空间来查找所述第一类元素获得与所述第一类元素具有映射关系的第二类数据。
以下就举个应用例来具体说明本发明。
假设(1)第一类元素A为48BIT数据，第二类数据B为16BIT数据；2)HASH算法为C＝(crc32(A)^(crc32(A)＞＞16))&0x03fff，其中C为第三类元素，crc32(A)是对元素A进行CRC32算法计算后的结果；从该HASH算法可以看出来C为14BIT，即哈西列表的存储容量为16K(0～0x3fff)，且哈西列表的每一单元可以采用数组方式。每个子单元中用48BIT存储A元素，用16BIT存储B数据，总计两个长字。
一个块中含有固定的3个子单元采用数组实现，加上前项指针(保存前一子单元的存储地址)和后项指针(保存后一子单元的存储地址)，请参阅5，其为块的存储结构图(共8个长字)。另外，考虑到实际发生的最大冲突数，限制每个哈西列表中的每一单元中块最大数目为3。
处理器数据总线为64bit，一次最少访问8byte数据，最多访问64byte数据，而且访问8byte和64byte的时间相同。则按照现有技术的存储方法，处理器每次访问一个单元，大小为8byte(sizeof(A)+sizeof(A))，采用本发明的算法，处理器每次访问一个块，为32byte，减去其中的指针开销(8byte)，效率变成了原来的三倍。
以上公开的仅为本发明的一个具体实施例，但本发明并非局限于此，本领域的技术人员能思之的变化，都应落在本发明的保护范围内。
权利要求
1.一种利用映射关系存储数据的方法，以实现处理器根据第一类的元素从存储器中找到与所述元素具有映射关系的第二类数据，其特征在于，包括(1)所述处理器进行初始设置，所述初始设置包括根据处理器的存取单元设置块的容量，所述存取单元为所述处理器每次从存储器中读取数据的最大容量；(2)第一类的所有元素按照预先设置的算法分别映射至第三类的元素，并在所述存储器中生成哈西列表，而且所述哈西列表的每一单元与所述第三类中每一元素存在一一对应关系；(3)处理器在哈西列表的每一单元下设置若干具有所述容量的块，并将所述第一类元素和与所述元素具有映射关系的第二类数据保存在块中，而且满足条件所述第一类元素按照步骤(2)的算法映射的第三类元素是所述单元对应的第三类元素。
2.如权利要求1所述的利用映射关系存储数据的方法，其特征在于，步骤(3)还包括在每一块下设置若干子单元，并且子单元的个数是由块的容量和所述子单元所占的容量所确定的，所述每一子单元用以存储一第一类元素及与之具有映射关系的第二类数据。
3.如权利要求2所述的利用映射关系存储数据的方法，其特征在于，还包括(a)当处理器需要在所述存储器中保存新的第一类元素及与之具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素，然后判断所述存储器中与第三类元素对应的单元下的所有块下的子单元中是否有第一类元素与第二类数据的对应关系，若有，则输出重复保存；否则判断单元下所有块下是否有空闲的子单元，若有，进行步骤(c)，否则(b)；(b)在所述单元下重新设置块，并在新块的第一个子单元中进行步骤(c)；(c)将所述第一类元素及与所述第一类元素具有映射关系的第二类数据保存在所述子单元中，并输出保存成功。
4.如权利要求2所述的利用映射关系存储数据的方法，其特征在于，还包括当处理器需要在所述存储器中删除一第一类元素及与所述第一类元素具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素；然后在所述存储器中找到与第三类元素对应的哈西列表的单元；随后查找所述单元下的每一块下的每一子单元，若存在子单元中保存有第一类元素与第二类数据的映射关系，则将所述子单元中存储内容清空，并删除所述子单元，输出删除成功；否则输出删除失败。若所述子单元所处的块下未设置其他子单元，则删除所述块。
5.如权利要求1或2所述的利用映射关系存储数据的方法，其特征在于，所述哈西列表的每一单元是一固定大小的数组或是一固定大小的链表。
6.如权利要求1所述的利用映射关系存储数据的方法，其特征在于，所述哈西列表的每一单元下设置若干块具体为所述单元的存储空间被分成若干存储单元，每一存储单元为一块的存储空间，或存储单元分配块的存储空间，所述单元中保存块的存储地址，所述存储地址用以查找所述块，获得块中存储内容。
7.如权利要求2或6所述的利用映射关系存储数据的方法，其特征在于，所述块下设置子单元具体为所述块的存储空间中划分出一存储单元，其为一子单元的存储空间，或存储器分配子单元的存储空间，所述块中存储子单元的存储地址，所述存储地址用以查找所述子单元，获得子单元中存储的内容。
8.一种如权利要求1方式存储的数据读取方法，以实现通过第一类元素从存储器中获得与所述元素具有映射关系的第二类数据，其特征在于，包括(A)处理器通过所述第一类元素按照所述算法计算第三类元素；(B)处理器在存储器的哈西列表中找到与所述第三类元素对应的单元，遍历所述单元下的所有块，判断是否找到其存储内容中包含所述第一类元素的块，若是，获得与所述第一类元素具有映射关系的第二类数据，否则，读取数据失败。
9.如权利要求8所述的数据读取方法，其特征在于，步骤(B)还包括若所述块下还设置子单元，则通过遍历所述块下的子单元的存储空间来查找所述第一类元素获得与所述第一类元素具有映射关系的第二类数据。
全文摘要
一种利用映射关系存储数据的方法，包括(1)处理器进行初始设置，初始设置包括根据处理器的存取单元设置块的容量，处理器的存取单元为处理器每次从存储器中读取数据的最大容量；(2)第一类的所有元素按照预先设置的算法分别映射至第三类的元素，并在存储器中生成哈西列表，哈西列表的每一单元与第三类中每一元素存在一一对应关系；(3)处理器在哈西列表的每一单元下设置若干具有上述容量的块，并将第一类元素和与元素具有映射关系的第二类数据保存在块中。根据处理器的存取单元的不同设置块的容量，由此提高了处理器处理效率及读取数据的速率。
文档编号G06F12/00GK1790318SQ200410101489
公开日2006年6月21日 申请日期2004年12月16日 优先权日2004年12月16日
发明者汤剑, 张少雄, 段小祥 申请人:华为技术有限公司
技术领域：
本发明涉及数据存取技术，尤其涉及利用映射关系存储数据的方法。
背景技术：
目前，对数据信息进行存取的技术是一门相对较成熟的技术。系统(如计算机系统)的微处理器或其他控制设备(以下统称为处理器)可以将数据信息存储在存储器以进行保存。而且，处理器还记录相应的存储地址，当需要读取该数据信息时，处理器按照预先保存的存储地址即可获得对应的数据信息。以数组M为例，I为数组序号，M[I]为数据元素，假设I的范围为
，则处理器可以在存储器中顺序存储M[1]、M[2]、M[3]...M[10]。当存储空间不连续时，处理器需要存储数据序号I及对应的数组元素M[I]。也就是说，当某一类A中的元素和另一类B中的数据信息存在映射关系时，若希望通过A从存储器中读取与A具有映射关系的数据信息B时，处理器在存储器中需要预先保存该类数据A中的每一元素AI及对应的B类数据中BK数据信息。进一步假设A的长度为32个BIT(比特)，则A的取值范围
，若所有的从0000H至FFFFH的AI元素全部映射同一个BK，则按照现有的存储方法，处理器至少需要2^32*N个存储容量的存储空间(如图1所示)，N为BK所占的存储空间。很显然，上述数据信息存储方法造成存储空间的大量耗费。
为此，现有技术提出一种利用HASH(哈西)列表进行具有映射关系的数据存储以及对应的读取方法。先介绍如何保存具有映射关系的数据的存储方法。请参阅图2，其为现有技术中利用映射关系进行数据存储流程图。
首先进行步骤S110系统的处理器采用某一算法将A中的所有元素先映射至C类信息中的元素；然后进行步骤S120所述处理器根据C类信息的范围及所述算法确定HASH列表所占的存储空间，在存储器中分配对应空间大小的地址以存储HASH列表，而且建立C类信息中的每一元素与HASH列表中每一单元的一一对应关系；最后进行步骤S130，将数据信息B中的每一元素依次保存在HASH列表的每一单元中。
比如，A的范围为
，B中每一元素所占的存储空间为N个字节，若AI元素小于等于8888H，则映射数据信息B中的元素BK1；否则，AI元素映射数据信息B中的元素BK2。若保存具有上述映射关系的A和B，则根据上述存储方法进行存储具体过程为首先设置C类信息，建立A和C的映射关系；f(A)=C10000H<=AI<=8888HC28888H<=AI<=FFFFH]]>然后，确定和C中元素一一对应的HASH列表的单元的个数和每个单元所占的存储空间，进而确定该HASH列表所占的存储空间。每个单元的存储空间可以设置为N个字节或是(4+N)个字节，则HASH列表所占的存储空间为2*N或者2*(4+N)个字节，随后，将BK1保存在C1所对应的第一HASH列表单元中，将BK2保存在C2所对应的第二HASH列表单元中。
事实上，上述存储方法可能存在A1、A2、A3分别映射B1、B2、B3，但是根据设置的算法将A1、A2、A3多对一映射至CI，为此将C1所一一对应的第一HAHS列表单元下又设置三个子单元子单元1、子单元2、子单元3。并且每个子单元保存A信息及对应的B信息而且保存前一子单元地址和下一子单元地址。其中，子单元1可以保存A1、B1及子单元2的地址，子单元2可以保存A2、B2及子单元3的地址，子单元3可以保存A3、B3及第一HASH列表单元的地址。
按照上述方法在存储单元中保存好B中的每一数据元素。则当获得A中的某一元素时，处理器能够根据根据A从存储器中获得映射的B元素，具体包括首先，处理器以A元素为依据，根据预先设定的算法进行计算，获得C元素；然后，以C元素为入口参数找到存储器中对应的HASH列表单元，并取出HASH列表单元中的内容，若是数据信息，则取出的数据信息即为B元素；否则获得的内容是子单元1的地址信息，再以A元素为参数查找子单元，找到A元素对应的数据信息B，并将数据信息B取出。
但是，现有技术存储具有映射关系数据的方法虽然节省了存储容量，但是还是存在以下问题存取单元为所述处理器每次从存储器中读取数据的最大容量，假设每个子单元的大小为8个字节，而处理器是以64个字节为存取单位对存储器进行访问，则处理器对每个8字节单元的访问都需要64个字节，由此导致处理器存取数据的效率非常低。
发明内容
本发明的目的在于提供一种具有映射关系的数据进行存储的方法，以解决现有技术中处理器存储数据的效率低的技术问题。
为解决上述问题，本发明公开了一种利用映射关系存储数据的方法，以实现处理器根据第一类的元素从存储器中找到与所述元素具有映射关系的第二类数据，包括(1)所述处理器进行初始设置，所述初始设置包括根据处理器的存取单元设置块的容量，所述存取单元为所述处理器每次从存储器中读取数据的最大容量；(2)第一类的所有元素按照预先设置的算法分别映射至第三类的元素，并在所述存储器中生成哈西列表，而且所述哈西列表的每一单元与所述第三类中每一元素存在一一对应关系；(3)处理器在哈西列表的每一单元下设置若干具有所述容量的块，并将所述第一类元素和与所述元素具有映射关系的第二类数据保存在块中，而且满足条件所述第一类元素按照步骤(2)的算法映射的第三类元素是所述单元对应的第三类元素。
步骤(3)还包括在每一块下设置若干子单元，并且子单元的个数是由块的容量和所述子单元所占的容量所确定的，所述每一子单元用以存储一第一类元素及与之具有映射关系的第二类数据。
还包括(a)当处理器需要在所述存储器中保存新的第一类元素及与之具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素，然后判断所述存储器中与第三类元素对应的单元下的所有块下的子单元中是否有第一类元素与第二类数据的对应关系，若有，则输出重复保存；否则判断单元下所有块下是否有空闲的子单元，若有，进行步骤(c)，否则(b)；(b)在所述单元下重新设置块，并在新块的第一个子单元中进行步骤(c)；(c)将所述第一类元素及与所述第一类元素具有映射关系的第二类数据保存在所述子单元中，并输出保存成功。
当处理器需要在所述存储器中删除一第一类元素及与所述第一类元素具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素；然后在所述存储器中找到与第三类元素对应的哈西列表的单元；随后查找所述单元下的每一块下的每一子单元，若存在子单元中保存有第一类元素与第二类数据的映射关系，则将所述子单元中存储内容清空，并删除所述子单元，输出删除成功；否则输出删除失败。
若所述子单元所处的块下未设置其他子单元，则删除所述块。
所述哈西列表的每一单元是一固定大小的数组或是一固定大小的链表。
所述哈西列表的每一单元下设置若干块具体为所述单元的存储空间被分成若干存储单元，每一存储单元为一块的存储空间，或存储单元分配块的存储空间，所述单元中保存块的存储地址，所述存储地址用以查找所述块，获得块中存储内容。
所述块下设置子单元具体为所述块的存储空间中划分出一存储单元，其为一子单元的存储空间，或存储器分配子单元的存储空间，所述块中存储子单元的存储地址，所述存储地址用以查找所述子单元，获得子单元中存储的内容。
一种数据读取方法，以实现通过第一类元素从存储器中获得与所述元素具有映射关系的第二类数据，其特征在于，包括(A)处理器通过所述第一类元素按照所述算法计算第三类元素；(B)处理器在存储器的哈西列表中找到与所述第三类元素对应的单元，遍历所述单元下的所有块，判断是否找到其存储内容中包含所述第一类元素的块，若是，获得与所述第一类元素具有映射关系的第二类数据，否则，读取数据失败。
步骤(B)还包括若所述块下还设置子单元，则通过遍历所述块下的子单元的存储空间来查找所述第一类元素获得与所述第一类元素具有映射关系的第二类数据。
与现有技术相比，本发明根据处理器处理数据的能力预先设置块的容量，并且存储器以所述容量分配块，然后将数据存储在块中，当处理器以块为单元读取存储器中的数据时，大大提高了处理器的处理效率，而且也提出数据存取的速率。
图1是未使用哈西算法存储具有映射关系的数据的存储方式；图2是现有技术中利用映射关系进行数据存储流程图；图3为本发明利用映射关系存储数据的方法的流程图；图4为本发明的数据存储示意图。
具体实施例方式
以下结合附图，具体说明本发明。
请参阅图3，其为本发明利用映射关系存储数据的方法的流程图。该方法是用以实现处理器根据第一类的元素从存储器中找到与所述元素具有映射关系的第二类数据，包括S210处理器进行初始设置，所述初始设置包括根据处理器的存取单元设置块的容量，所述存取单元为所述处理器每次从存储器中读取数据的最大容量；所述块的容量等于该处理器的存储单元是本发明的一较佳实施例，从而使得处理器以块为单元进行读取数据时，处理器读取数据快且处理器的处理效率高；S220第一类的所有元素按照预先设置的算法分别映射至第三类的元素，并在所述存储器中生成哈西列表，而且所述哈西列表的每一单元与所述第三类中每一元素存在一一对应关系；由于哈西列表中的每一单元与第三类中每一元素存在一一对应关系，所以根据第三类元素的个数且每一单元应占用的存储空间即可在存储器中开辟相应存储容量作为哈西列表。哈西列表的每一单元是一固定大小的数组或是一固定大小的链表；S230处理器在哈西列表的每一单元下设置若干块，并将所述第一类元素和与所述元素具有映射关系的第二类数据保存在块中，而且满足条件所述第一类元素按照步骤S220的算法映射的第三类元素是所述单元对应的第三类元素。所述哈西更表的每一单元下设置若干块可以有两种方式第一种方式单元的存储空间被分成若干存储单元，每一存储单元为一块的存储空间，并且所述存储单元等于步骤S210中确定的块的容量；第二种方式存储器分配块的存储空间，所述单元中保存块的存储地址，所述存储地址用以查找所述块，获得块中存储内容，并且所述存储空间等于步骤S220中确定块的容量。若所述块是一链表，则所述块中还需保前一块的存储地址及后一块的存储地址。若所述块是本单元的第一个块，则所述块的前一块存储地址保存的是单元的存储地址。若所述块是本单元的最后一个块，则所述块的后一块存储地址保存的是本单元的存储地址或置空。
通过上述数据存储的方法，处理器根据自身的存取数据的能力设置了块的大小，并且将具有映射关系的第一类元素及第二类数据存储在块中。当处理器读取数据时，能够以块为单元访问存储器，不仅提高了数据读取的速率同时也提高了处理器的利用效率。
在本发明中，为了使得每一第一类元素及与之具有映射关系的第二类数据能够更清晰地保存，为此在块下又设置了子单元，比如在所述块的存储空间中划分出一存储单元，其为一子单元的存储空间，或者存储器分配子单元的存储空间，所述块中存储子单元的存储地址，所述存储地址用以查找所述子单元，获得子单元中存储的内容。每一子单元用以存储一第一类元素及具有映射关系的第二类数据。若块中的所有子单元不是处于存储器中的连续存储空间，则每一子单元中还需保存前一子单元所在的存储地址及后一子单元所在的存储地址。若所述子单元是本块的第一个子单元，则所述子单元的前一子单元存储地址保存的是块的存储地址。若所述子单元是本块的最后一个子单元，则所述子单元的后一子单元存储地址保存的是本块的存储地址或置空(请参阅图4)。
在上述数据存储的基础上，若处理器在所述存储器中保存新的第一类元素及与之具有映射关系的第二类数据，则主要按照下述步骤进行存储新增加数据(a)当处理器需要在所述存储器中保存新的第一类元素及与之具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素，然后判断所述存储器中与第三类元素对应的单元下的所有块下的子单元中是否有第一类元素与第二类数据的对应关系，若有，则输出重复保存；否则判断单元下所有块下是否有空闲的子单元，若有，进行步骤(c)，否则(b)；(b)在所述单元下重新设置块，并在新块的第一个子单元中进行步骤(c)；(c)将所述第一类元素及与所述第一类元素具有映射关系的第二类数据保存在所述子单元中，并输出保存成功。
在上述数据存储的基础上，若处理器需要在所述存储器中删除一第一类元素及与所述第一类元素具有映射关系的第二类数据时，则主要按照下述步骤进行数据删除先按照所述算法找到所述第一类元素映射的第三类元素；然后在所述存储器中找到与第三类元素对应的哈西列表的单元；随后查找所述单元下的每一块下的每一子单元，若存在子单元中保存有第一类元素与第二类数据的映射关系，则将所述子单元中存储内容清空，并删除所述子单元，输出删除成功；否则输出删除失败；若所述子单元所处的块下未设置其他子单元，则删除所述块。
在上述数据存储的基础上，处理器主要按照以下方式进行数据读取操作(A)处理器通过所述第一类元素按照所述算法计算第三类元素；(B)处理器在存储器的哈西列表中找到与所述第三类元素对应的单元，遍历所述单元下的所有块，判断是否找到其存储内容中包含所述第一类元素的块，若是，获得与所述第一类元素具有映射关系的第二类数据，否则，读取数据失败。若所述块下还设置子单元，则通过遍历所述块下的子单元的存储空间来查找所述第一类元素获得与所述第一类元素具有映射关系的第二类数据。
以下就举个应用例来具体说明本发明。
假设(1)第一类元素A为48BIT数据，第二类数据B为16BIT数据；2)HASH算法为C＝(crc32(A)^(crc32(A)＞＞16))&0x03fff，其中C为第三类元素，crc32(A)是对元素A进行CRC32算法计算后的结果；从该HASH算法可以看出来C为14BIT，即哈西列表的存储容量为16K(0～0x3fff)，且哈西列表的每一单元可以采用数组方式。每个子单元中用48BIT存储A元素，用16BIT存储B数据，总计两个长字。
一个块中含有固定的3个子单元采用数组实现，加上前项指针(保存前一子单元的存储地址)和后项指针(保存后一子单元的存储地址)，请参阅5，其为块的存储结构图(共8个长字)。另外，考虑到实际发生的最大冲突数，限制每个哈西列表中的每一单元中块最大数目为3。
处理器数据总线为64bit，一次最少访问8byte数据，最多访问64byte数据，而且访问8byte和64byte的时间相同。则按照现有技术的存储方法，处理器每次访问一个单元，大小为8byte(sizeof(A)+sizeof(A))，采用本发明的算法，处理器每次访问一个块，为32byte，减去其中的指针开销(8byte)，效率变成了原来的三倍。
以上公开的仅为本发明的一个具体实施例，但本发明并非局限于此，本领域的技术人员能思之的变化，都应落在本发明的保护范围内。
权利要求
1.一种利用映射关系存储数据的方法，以实现处理器根据第一类的元素从存储器中找到与所述元素具有映射关系的第二类数据，其特征在于，包括(1)所述处理器进行初始设置，所述初始设置包括根据处理器的存取单元设置块的容量，所述存取单元为所述处理器每次从存储器中读取数据的最大容量；(2)第一类的所有元素按照预先设置的算法分别映射至第三类的元素，并在所述存储器中生成哈西列表，而且所述哈西列表的每一单元与所述第三类中每一元素存在一一对应关系；(3)处理器在哈西列表的每一单元下设置若干具有所述容量的块，并将所述第一类元素和与所述元素具有映射关系的第二类数据保存在块中，而且满足条件所述第一类元素按照步骤(2)的算法映射的第三类元素是所述单元对应的第三类元素。
2.如权利要求1所述的利用映射关系存储数据的方法，其特征在于，步骤(3)还包括在每一块下设置若干子单元，并且子单元的个数是由块的容量和所述子单元所占的容量所确定的，所述每一子单元用以存储一第一类元素及与之具有映射关系的第二类数据。
3.如权利要求2所述的利用映射关系存储数据的方法，其特征在于，还包括(a)当处理器需要在所述存储器中保存新的第一类元素及与之具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素，然后判断所述存储器中与第三类元素对应的单元下的所有块下的子单元中是否有第一类元素与第二类数据的对应关系，若有，则输出重复保存；否则判断单元下所有块下是否有空闲的子单元，若有，进行步骤(c)，否则(b)；(b)在所述单元下重新设置块，并在新块的第一个子单元中进行步骤(c)；(c)将所述第一类元素及与所述第一类元素具有映射关系的第二类数据保存在所述子单元中，并输出保存成功。
4.如权利要求2所述的利用映射关系存储数据的方法，其特征在于，还包括当处理器需要在所述存储器中删除一第一类元素及与所述第一类元素具有映射关系的第二类数据时，先按照所述算法找到所述第一类元素映射的第三类元素；然后在所述存储器中找到与第三类元素对应的哈西列表的单元；随后查找所述单元下的每一块下的每一子单元，若存在子单元中保存有第一类元素与第二类数据的映射关系，则将所述子单元中存储内容清空，并删除所述子单元，输出删除成功；否则输出删除失败。若所述子单元所处的块下未设置其他子单元，则删除所述块。
5.如权利要求1或2所述的利用映射关系存储数据的方法，其特征在于，所述哈西列表的每一单元是一固定大小的数组或是一固定大小的链表。
6.如权利要求1所述的利用映射关系存储数据的方法，其特征在于，所述哈西列表的每一单元下设置若干块具体为所述单元的存储空间被分成若干存储单元，每一存储单元为一块的存储空间，或存储单元分配块的存储空间，所述单元中保存块的存储地址，所述存储地址用以查找所述块，获得块中存储内容。
7.如权利要求2或6所述的利用映射关系存储数据的方法，其特征在于，所述块下设置子单元具体为所述块的存储空间中划分出一存储单元，其为一子单元的存储空间，或存储器分配子单元的存储空间，所述块中存储子单元的存储地址，所述存储地址用以查找所述子单元，获得子单元中存储的内容。
8.一种如权利要求1方式存储的数据读取方法，以实现通过第一类元素从存储器中获得与所述元素具有映射关系的第二类数据，其特征在于，包括(A)处理器通过所述第一类元素按照所述算法计算第三类元素；(B)处理器在存储器的哈西列表中找到与所述第三类元素对应的单元，遍历所述单元下的所有块，判断是否找到其存储内容中包含所述第一类元素的块，若是，获得与所述第一类元素具有映射关系的第二类数据，否则，读取数据失败。
9.如权利要求8所述的数据读取方法，其特征在于，步骤(B)还包括若所述块下还设置子单元，则通过遍历所述块下的子单元的存储空间来查找所述第一类元素获得与所述第一类元素具有映射关系的第二类数据。
全文摘要
一种利用映射关系存储数据的方法，包括(1)处理器进行初始设置，初始设置包括根据处理器的存取单元设置块的容量，处理器的存取单元为处理器每次从存储器中读取数据的最大容量；(2)第一类的所有元素按照预先设置的算法分别映射至第三类的元素，并在存储器中生成哈西列表，哈西列表的每一单元与第三类中每一元素存在一一对应关系；(3)处理器在哈西列表的每一单元下设置若干具有上述容量的块，并将第一类元素和与元素具有映射关系的第二类数据保存在块中。根据处理器的存取单元的不同设置块的容量，由此提高了处理器处理效率及读取数据的速率。
文档编号G06F12/00GK1790318SQ200410101489
公开日2006年6月21日 申请日期2004年12月16日 优先权日2004年12月16日
发明者汤剑, 张少雄, 段小祥 申请人:华为技术有限公司
最新回复(0)