CN110688380A - Address book anti-reconstruction method suitable for equipment with limited storage space - Google Patents
Address book anti-reconstruction method suitable for equipment with limited storage space Download PDFInfo
- Publication number
- CN110688380A CN110688380A CN201910906677.4A CN201910906677A CN110688380A CN 110688380 A CN110688380 A CN 110688380A CN 201910906677 A CN201910906677 A CN 201910906677A CN 110688380 A CN110688380 A CN 110688380A
- Authority
- CN
- China
- Prior art keywords
- data
- key
- index
- address
- address book
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/22—Indexing; Data structures therefor; Storage structures
- G06F16/2228—Indexing structures
- G06F16/2255—Hash tables
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/22—Indexing; Data structures therefor; Storage structures
- G06F16/2282—Tablespace storage structures; Management thereof
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention provides an address book anti-reconstruction method suitable for equipment with limited storage space, which can run in limited memory with high efficiency, and has the advantages of simple and understandable algorithm, low complexity and easy implementation. In the technical scheme of the invention, a master table and a slave table are constructed based on a hash table structure, and the contact names and the associated data form association by mutual indexing; duplication can be detected when new data is added to the master table and the slave table, and the duplication can be used for merging the address lists from different sources. When address book data is added, the HASH code is calculated for 1 time by using a quick HASH algorithm, the basic capacity of a HASH table is modulo by the HASH code, the value of a data address index is calculated, and if the indexes are the same, the data address index is compared to judge whether the data are repeated.
Description
Technical Field
The invention relates to the technical field of computer data processing, in particular to an address book anti-reconstruction method suitable for equipment with limited storage space.
Background
In the prior art, for the processing of the address list, mostly, the anti-replay processing is not performed during the data storage, but the anti-replay processing is performed on the address list data participating in the calculation during the subsequent calculation. However, when the method is developed on the basis of equipment with limited storage space, such as a single chip microcomputer, anti-duplication processing is required during storage, but most of the existing anti-duplication methods are designed for equipment with unlimited storage space, and the use mode of the existing anti-duplication methods for the storage space is not suitable for the equipment with limited storage space, and when the method is applied to the equipment with limited storage space, such as the single chip microcomputer, the operation efficiency is poor.
Disclosure of Invention
In order to solve the problem that the operation efficiency of the existing address book anti-duplication method is poor when the existing address book anti-duplication method is operated on equipment with limited storage space, the invention provides the address book anti-duplication construction method suitable for the equipment with limited storage space, the address book anti-duplication construction method can be operated in the limited memory with high efficiency, and the algorithm is simple and easy to understand and is easy to realize.
The technical scheme of the invention is as follows: the address book reconstruction preventing method suitable for equipment with limited storage space is characterized by comprising the following steps of:
s1: reading all address book data to be added into a memory of the equipment;
s2: determining the number n _ Directory of hash tables of the address list to be established according to the data type n _ Class contained in the address list data; the data of the corresponding type in each address book hash table is used as a key code, and the data except the key code is used as associated data and is stored in the table in the form of an associated data address;
namely: n _ Class is equal to n _ Directory, and both n _ Directory and n _ Class are positive integers;
s3: constructing n _ Directory hash tables of the address lists;
in each address book hash table, column elements of each row include: occupation flag, data field, chain index;
the field of the occupation flag is used for setting a use flag to indicate whether the record is used or not;
the fields of the data field are used for storing actual data, and the actual data comprises: a key data field, an associated data address field;
the related data address field stores an index address in another related address book hash table, and the index address stores other kinds of data with an index relation set with the key;
the address book hash table with the key code being the contact name is set as a master table, and the address book hash tables of other types are set as slave tables;
in the primary table, the number relationship between the key data field and the associated data address field is: num is a natural number, wherein Num is not less than (n _ Class-1); index information of all kinds of associated data except the key is stored in the associated data address field in the main table, wherein the number of the associated data address fields of the same kind is more than or equal to 1;
in the slave table, the number relationship between the key data field and the associated data address field is: 1: 1; only the address of the key of the primary table is stored in the associated data address field in the secondary table;
the field of the chain index is used for supporting a zipper method to process conflicts, and when a plurality of pieces of information need to occupy the same record position, the field is used for recording the index of the next record;
s4: initializing the length of the address book hash table to be N + N x y%;
wherein N is the basic capacity of the hash table, and N is a positive integer;
y is used for processing the space reservation rate of the Hash mapping conflict, and y is a positive integer; when data is newly added, if the data corresponding to the index obtained through calculation conflicts with the newly added data, a conflict chain needs to be sequentially hung behind the basic capacity N for placing the information of the conflicted contact person, and then N x y% of space outside the basic capacity is used for constructing the conflict chain;
s5: initializing all fields of the n _ Directory address book hash tables;
setting the occupied mark field of each address book hash table as follows: not used;
setting all of the chain index fields to: invalid;
initializing the use states of the associated data address fields corresponding to all keys as follows: invalid;
s6: acquiring all the address book data needing to be added read in the step S1, sequentially reading each address book data, and assigning values to the directory data of the address book data to be processed;
the directory data to be processed comprises: key code data KeyCode and associated data LinkCode; the quantity relationship between the key code data KeyCode and the associated data LinkCode is as follows: n _ Data, wherein n _ Data is a natural number;
according to the type of key code data KeyCode in the directory data DirectoryData to be processed, taking the address book hash table of the corresponding type as the directory hash table TargetDirectory to be processed;
s7: adding the directory data to be processed into the TargetDirectory of the hash table of the address book to be processed;
the method specifically comprises the following steps:
a 1: assigning the key code data Keycode to a key code TempKeycode to be processed; calculating the hash code of the TempKeycode to be processed by using a hash algorithm, and assuming that the value of the obtained hash code is HASHCODE;
a 2: calculating the chain index of the key code TempKeyCode to be processed;
using the hash code value hash code modulo N to obtain a remainder INDEX, where INDEX is the value of the chain INDEX field, and the details are as follows:
INDEX＝HASHCODE modN；
a 3: in the address book hash table TargetDirectory to be processed, checking the corresponding occupied zone bit in the row at the INDEX position;
if the field of the occupied zone bit is: if not, indicating that the key data field in the data field corresponding to the key data field is not used, setting the row corresponding to INDEX as the row element to be inserted, and executing step a 6;
otherwise, indicating that the key data field in the data field corresponding to the key data field is used, executing step a 4;
a 4: obtaining data in a key code data field in the data field, and comparing the data serving as comparison data ComparCode with the key code TempKeyCode to be processed;
if the CompleeCode is the same as the TempKeyCode, the to-be-processed key code TempKeyCode is already in the hash table and does not need to be added again, and the adding operation for the to-be-processed key code TempKeyCode is finished at this time;
otherwise, the to-be-processed key TempKeyCode is not stored in the hash table, and the problem of data repetition does not exist, and step a5 is executed;
a 5: sequentially searching unoccupied rows of a first data field from an N x y% region behind the basic capacity N of the address book hash table TargetDirectory to be processed as row elements to be inserted, hanging at the tail of the conflict chain, and assigning the value of the INDEX of the last row at the tail of the conflict chain to INDEX;
a 6: storing the key to be processed TempKeycode into a field of key data in the data field in the row element to be inserted, wherein the corresponding chain INDEX automatically stores the value of INDEX;
s8: aiming at the key code TempKeycode to be processed, finding the corresponding associated data LinkCode in the same directory data to be processed, and setting the mutual index relationship between the key code TempKeyCode to be processed and the associated data LinkCode:
s9: and repeating the steps S6-S8 until all the address book data read in the step S1 are processed, and ending the construction operation.
It is further characterized in that:
in step S8, the method for setting the mutual index relationship between the to-be-processed key TempKeyCode and the associated data LinkCode includes the following steps:
b 1: confirming the number n _ Data of the LinkCode of the associated Data of the TempKeyCode to be processed in the directory Data DirectoryData to be processed;
if n _ Data is equal to 0, the LinkCode represents that the associated Data is empty, the associated index operation is not needed, and the operation of the current associated index is finished;
otherwise, performing step b 2;
b 2: confirming the kind of the key code TempKeycode to be processed;
if the kind of the key code to be processed TempKeyCode is a contact name, executing step b 3;
otherwise, performing step b 7;
b3, sequentially taking out each Data in the n _ Data associated Data LinkCodes, and sequentially setting the Data as to-be-confirmed associated Data TempLinkCodes;
b4, the key code to be processed TempKeyCode is a main key, the address book Hash table to be processed TargetDirectory corresponding to the key code to be processed is a main table, the associated data TempLinkCode to be confirmed is a slave key, and the address book Hash table corresponding to the associated data TempLinkCode is a slave table;
calling step S7, inserting the extracted associated data TempLinkCode to be confirmed into the slave table of the corresponding type according to the type of the associated data TempLinkCode, and recording the index address of the associated data TempLinkAddress in the slave table as TempLinkAddress;
b 5: taking INDEX as an INDEX address of the main key in the main table and TempLinkAddress as an INDEX address of the slave key in the slave table, and sequentially executing the following steps:
establishing an index relationship between the primary key and the secondary key in the secondary table;
establishing an index relationship between the slave key and the master key in the master table;
b6, repeating b 4-b 5 until the LinkCode of the n _ Data associated Data is searched; step b9 is executed;
b7, the key code to be processed TempKeyCode is a slave key, the address book hash table to be processed TargetDirectory corresponding to the key code to be processed is a slave table, the associated data LinkCode is a master key, and the address book hash table corresponding to the key code to be processed is a master table;
the associated data LinkCode to-be-confirmed associated data TempLinkCode;
step S7 is called, the to-be-confirmed associated data TempLinkCode is inserted into the main table, and the index address of the to-be-confirmed associated data TempLinkCode in the main table is recorded as TempLinkAddress;
b8, taking TempLinkAddress as the INDEX address of the main key in the main table and INDEX as the INDEX address of the slave table in the slave table, and sequentially executing the following steps:
establishing an index relationship between the slave key and the master key in the master table;
establishing an index relationship between the primary key and the secondary key in the secondary table;
b9, ending the operation of the current association index;
in the slave table, establishing an index relationship between the master key and the slave key, including the following steps:
c1, setting the associated data address field corresponding to the slave key in the slave table as a slave key associated address field;
c2, confirming the state of the slave key association data address field;
if the state of the slave key associated data address field is: invalid, representing that the slave key is in the slave table, and if no associated index is established with the key code in the master table, storing the index address of the master key in the master table into the associated data address field of the slave key;
performing step c 4;
otherwise, representing that the slave key is in the corresponding slave table, and the associated index has been established with the key code in the master table, then step c3 is executed;
c 3: confirming whether the index relation is to be reestablished or not to the user;
if the index relationship needs to be reestablished, deleting the existing index relationship, and executing the step c 4;
otherwise, performing step c 5;
c4, establishing the index relationship between the slave key and the master key in the master table;
c5, ending the operation;
in the primary table, establishing an index relationship between the secondary key and the primary key:
d 1: setting an associated data address field corresponding to the main key as a main key associated data address field in the main table;
sequentially acquiring the states of Num main key associated data address fields corresponding to the main keys;
d 2: confirming the state of each primary key associated data address field;
if the status of all the primary key associated data address fields is not invalid, then representing that all the primary key associated data address fields are used, performing step d 4;
otherwise, when the primary key associated data address field with the first invalid state is found, stopping the operation of confirming the state of the primary key associated data address field, and executing step d 3;
d3, storing the index address of the slave key in the slave table into the field, and ending the operation;
d4, prompting the user that the slave key can not be added to the main key, and inquiring whether the client wants to delete the associated data of the main key;
if the customer selects yes, entering a management data deleting process of the main key, and ending the operation;
if the customer selects no, the operation is finished;
in the step c3, the method specifically comprises the following steps:
e1, displaying the prompt information: the slave key belongs to other main keys, and whether the user wants to modify the associated main key of the slave key is inquired;
if the user chooses: if yes, go to step e 2;
if the user chooses: if not, go to step e 4;
e2, acquiring the current primary key with index relation of the secondary key, and setting the current primary key as the primary key to be released; finding the primary key to be released in the primary table;
e 3: in the associated data address field corresponding to the primary key to be released, retrieving the associated data address field corresponding to the secondary key, and setting the state of the associated data address field to be: invalid;
e4, ending the operation;
the structure of the address book basic hash table is realized by an array;
the address book data comprises a data type n _ Class with a value of 2, and the data type comprises: contact name, phone number; the number n _ Directory of the address book hash tables is 2, and the address book hash tables comprise contact name hash tables and telephone number hash tables;
in the contact name hash table, if the number of the user behaviors expected to be stored in the hash table is X, the number of array elements of the contact name hash table is M:
M＝(1+x％)*X
in the formula: x is a reserved rate of newly-added contacts preset according to the product use environment; aiming at the contact name hash table, wherein M is the number of array elements of the contact name hash table, namely the number of the array elements is the basic capacity N;
in the phone number hash table corresponding to the contact name hash table, the number element quantity P of the phone number hash table conforms to the following formula:
P＝M*p
in the formula: m is the length of the hash table of the contact names, and p is the maximum number of the telephones which can be owned by one contact; aiming at the telephone number hash table, the array element quantity P of the telephone number hash table is the basic capacity N of the telephone number hash table;
the value range of the space reservation rate y% is as follows: 20 percent to y percent to 30 percent.
According to the address book anti-reconstruction method suitable for the equipment with limited storage space, provided by the invention, repeated data is not removed based on the database, and the data is subjected to anti-reconstruction processing in the memory when the data table is constructed. The existing database-based anti-duplication algorithm has the algorithm complexity calculation mode as follows: the address book has two kinds of data of telephone and name, and the address book is first taken out and then one telephone and the rest are taken outTelephone comparison, see if duplicate, need
Comparing for the number of times of O (n)2) (ii) a Besides, address book maintenance operations such as adjustment of array elements after weight removal are carried out. In the technical scheme of the invention, a master table and a slave table are constructed based on a hash table structure, and the contact names and the associated data form association by mutual indexing; duplication can be detected when new data is added to the master table and the slave table, and the duplication can be used for merging the address lists from different sources. When address book data is added, calculating the HASH code for 1 time by using a quick HASH algorithm, calculating the value of a data address index by using the basic capacity of a HASH table modulo the HASH code, and comparing and judging whether the data is repeated if the indexes are the same; the performance of the quick HASH algorithm for calculating the HASH code for 1 time is similar in one-time comparison performance, and the calculation index refers to one-time division and can be regarded as one-time comparison; then again, if there are both phone and name data in the address book: when the address book is established by using the algorithm, 2 times of calculation are needed, n pieces of information are added, 2n times of calculation are needed, and the comparison caused by index conflict is carried out to determine whether the repeated technology times are far less than n, namely, the time complexity of the technical scheme is O (n); in conclusion, the technical scheme of the invention has the advantages of strong structure and algorithm function, high performance, linear relation between time complexity and information quantity, and suitability for running on equipment with limited storage space.
Drawings
FIG. 1 is a diagram illustrating the basic structure of a hash table according to the present invention;
FIG. 2 is a diagram illustrating the structure of the data fields of the double hash tables and the structure of the index associations between the data fields;
FIG. 3 is a schematic flow chart of hash table construction according to the present invention;
FIG. 4 is a flowchart illustrating the process of indexing the hash tables.
Detailed Description
As shown in fig. 1, the method for preventing address book reconstruction according to the present invention is applicable to a device with limited storage space, and includes the following steps.
S1: all address book data required to be added are read into the memory of the equipment, and the following calculation is completed in the memory.
S2: determining the number n _ Directory of hash tables of the address list to be established according to the data type n _ Class contained in the address list data; the data of the corresponding type in each address book hash table is used as a key code, and the data except the key code is used as associated data and is stored in the table in the form of an associated data address; in the embodiments shown in fig. 1 to fig. 2, the address book data includes a data type n _ Class having a value of 2, and the data types include: contact name, phone number.
S3: constructing n _ Directory address book hash tables; the number n _ Directory of the address book hash tables is 2, and the address book hash tables comprise contact name hash tables and telephone number hash tables;
as shown in fig. 1, in each address book hash table, the column elements of each row include: occupation flag, data field, chain index;
the field of the occupation flag is used for setting a use flag to indicate whether the record is used or not;
the field of the data field is used for storing actual data and consists of a key data field and a related data address field of the stored actual data;
the associated data address field stores an index address in another associated address book hash table, and the index address stores other kinds of data with an index relation set with the key data field;
the address book hash table with the key code being the name of the contact person is set as a master table, and the address book hash tables of other types are set as slave tables;
in the main table, the number relationship between the key data field and the associated data address field is as follows: num is a natural number, wherein Num is not less than (n _ Class-1); index information of all kinds of associated data except the key is stored in the associated data address field in the main table, wherein the number of the associated data address field of the same kind is more than or equal to 1;
in the slave table, the number relationship between the key data field and the associated data address field is: 1: 1; only the address of the key code of the main table is stored in the associated data address field in the auxiliary table;
the field of the chain index is used for supporting the zipper method to process conflicts, and when a plurality of pieces of information need to occupy the same record position, the field is used for recording the index of the next record.
S4: initializing the hash table length of the address book to be N + N x y%;
wherein N is the basic capacity of the hash table, and N is a positive integer;
y is used for processing the space reservation rate of the Hash mapping conflict, and y is a positive integer; when data is newly added, if the data corresponding to the index obtained through calculation conflicts with the newly added data, a conflict chain needs to be sequentially hung behind the basic capacity N for placing the information of the conflicted contact person, and then N x y% of space outside the basic capacity is used for constructing the conflict chain;
in the embodiment, the structure of the address book basic hash table is realized by an array; in the contact name hash table, if the number of user behaviors expected to be stored in the hash table is X, the number of array elements of the contact name hash table is M:
M＝(1+x％)*X
in the formula: x is a reserved rate of newly-added contacts preset according to the product use environment; aiming at the contact name hash table, the number of array elements of the contact name hash table is M, namely the basic capacity N of the contact name hash table;
in the telephone number hash table corresponding to the contact name hash table, the array element quantity P of the telephone number hash table conforms to the following formula:
P＝M*p
in the formula: m is the length of the hash table of the contact name, and p is the maximum number of the telephone numbers which can be owned by one contact; aiming at the telephone number hash table, the array element quantity P of the telephone number hash table is the basic capacity N of the telephone number hash table;
the value range of the space reservation rate y% is as follows: 20 percent to y percent to 30 percent.
S5: initializing fields of hash tables of all n _ Directory address lists;
setting the occupation mark field of each address book hash table as follows: not used;
all chain index fields are set to: invalid;
initializing the use states of the associated data address fields corresponding to all the keys as follows: invalid;
s6: acquiring all the address book data needing to be added read in the step S1, sequentially reading each address book data, and assigning values to the directory data of the address book data to be processed;
the directory data to be processed comprises: key code data KeyCode and associated data LinkCode; the quantity relation between the key code data KeyCode and the associated data LinkCode is as follows: n _ Data, wherein n _ Data is a natural number;
according to the type of key code data KeyCode in the directory data DirectoryData to be processed, taking the directory hash table of the corresponding type as the directory hash table TargetDirectory to be processed;
s7: adding directory data to be processed into a hash table TargetDirectory of the address book to be processed;
the method specifically comprises the following steps:
a 1: assigning the key code data Keycode to a key code TempKeycode to be processed; calculating a hash code of the TempKeycode to be processed by using a hash algorithm, and assuming that the value of the obtained hash code is HASHCODE;
a 2: calculating the chain index of the key code TempKeycode to be processed;
using the hash code value hash code modulo N to obtain a remainder INDEX, where INDEX is the value of the chain INDEX field, as follows:
INDEX＝HASHCODE mod N；
a 3: in the address book hash table TargetDirectory to be processed, checking a corresponding occupied zone bit in a row at an INDEX position;
if the field occupying the zone bit is: if not, the key data field in the data field corresponding to the key data field is not used, the row corresponding to INDEX is set as the row element to be inserted, and step a6 is executed;
otherwise, indicating that the key data field in the corresponding data field has been used, executing step a 4;
a 4: obtaining data in a key code data field in a data domain, and comparing the data serving as comparison data ComparCode with a key code TempKeyCode to be processed;
if the CompleeCode is the same as the TempKeyCode, the fact that the to-be-processed key TempKeyCode exists in the hash table and does not need to be added again is indicated, and the adding operation for the to-be-processed key TempKeyCode is finished at this time;
otherwise, the TempKeyCode to be processed is not stored in the hash table, and the problem of data repetition does not exist, and the step a5 is executed;
a 5: sequentially searching unoccupied rows of a first data field from an N x y% region behind the basic capacity N of the address book hash table TargetDirectory to be processed as row elements to be inserted, hanging at the tail of a conflict chain, and assigning the value of the INDEX of the last row at the tail of the conflict chain to INDEX;
a 6: storing the key code TempKeycode to be processed into the field of the key code data in the data field in the row element to be inserted, and automatically storing the value of INDEX in the corresponding chain INDEX;
s8: aiming at the key code TempKeycode to be processed, finding the corresponding associated data Linkcode in the same directory data to be processed, and setting the mutual index relationship between the key code TempKeycode to be processed and the associated data Linkcode:
s9: and repeating the steps S6-S8 until all the address book data read in the step S1 are processed, and ending the construction operation.
The contact person name and the associated data are associated through mutual indexing, namely, the contact person information is marked, convenience is provided for maintenance of the data structure, algorithm design is simplified, and performance is improved. The address book data can be stored in a database and a file, and can be read out from the database table or the file during maintenance, and the data calculation is carried out in the memory through the hash table structure, so that the method is more suitable for equipment with less storage space and simple structure, such as a single chip microcomputer and the like.
As shown in fig. 4, in step S8, the step of setting the mutual index relationship between the to-be-processed key TempKeyCode and the associated data LinkCode includes the following steps:
b 1: confirming the number n _ Data of the LinkCode related Data of the TempKeyCode to be processed in the directory Data DirectoryData to be processed;
if n _ Data is equal to 0, the LinkCode represents that the associated Data is empty, the associated index operation is not needed, and the operation of the current associated index is finished;
otherwise, performing step b 2;
b 2: confirming the kind of the key code TempKeycode to be processed;
if the kind of the key code to be processed TempKeyCode is the contact name, executing step b 3;
otherwise, performing step b 7;
b3, sequentially taking out each Data from the n _ Data associated Data LinkCodes, and sequentially setting the Data as to-be-confirmed associated Data TempLinkCodes;
b4, setting a key code TempKeycode to be processed as a main key, a corresponding address book Hash table to be processed TargetDirectory as a main table, and confirming that the associated data TempLinkcode is a slave key and the corresponding address book Hash table is a slave table;
calling step S7, inserting the extracted associated data TempLinkCode to be confirmed into the slave table of the corresponding type according to the type of the associated data TempLinkCode, and recording the index address of the slave table as TempLinkAddress;
b 5: taking INDEX as a main key into the INDEX address in the table, and TempLinkAddress as a slave key into the INDEX address in the slave table, and sequentially executing the following steps:
establishing an index relation of a primary key and a secondary key in a secondary table;
establishing an index relation between the slave key and the master key in the master table;
b6, repeating b 4-b 5 until the LinkCode of n _ Data associated Data is searched; step b9 is executed;
b7, setting a key code TempKeycode to be processed as a slave key, a corresponding address book hash table to be processed TargetDirectory as a slave table, associated data Linkcode as a master key and a corresponding address book hash table as a master table;
the associated data LinkCode is to confirm associated data TempLinkCode;
step S7 is invoked, the TempLinkCode of the associated data to be confirmed is inserted into the main table, and the index address of the TempLinkAddress in the main table is recorded;
b8, substituting TempLinkAddress as the INDEX address of the main key in the main table and INDEX as the INDEX address of the slave table in the slave table, and sequentially executing the following steps:
establishing an index relation between a slave key and a master key in a master table;
establishing an index relation between a primary key and a secondary key in a secondary table;
b9, the operation of the current association index is finished.
In the slave table, establishing an index relationship between the master key and the slave key, including the following steps:
c1, in the slave table, setting the associated data address field corresponding to the slave key as the slave key associated address field;
c2, confirming the state of the slave key association data address field;
if the status of the slave key associated data address field is: if the secondary key is invalid, indicating that the secondary key is in the secondary table and does not establish an associated index with the key code in the primary table, storing the index address of the primary key in the primary table into the associated data address field of the secondary key;
performing step c 4;
otherwise, representing that the slave key is in the corresponding slave table, and the associated index is already established with the key code in the master table, then step c3 is executed;
c 3: confirming whether the index relation is to be reestablished or not to the user;
if the index relationship needs to be reestablished, deleting the existing index relationship, and executing the step c 4;
otherwise, performing step c 5;
c4, establishing the index relationship between the slave key and the master key in the master table;
c5, finishing the operation.
In the primary table, the index relationship from the key and the primary key is established:
d 1: in the main table, setting an associated data address field corresponding to a main key as a main key associated data address field;
sequentially acquiring the states of Num main key associated data address fields corresponding to the main keys;
d 2: confirming the state of each primary key associated data address field;
if the status of all primary key associated data address fields is not invalid, then step d4 is performed, indicating that all primary key associated data address fields are used;
otherwise, finding the primary key associated data address field with the first state as invalid; stopping confirming the state of the primary key associated data address field;
d3, storing the index address of the slave key in the slave table into the field, and ending the operation;
d4, prompting the user that the auxiliary key can not be added to the main key, inquiring whether the client wants to delete the associated data of the main key;
if the customer selects yes, entering a management data deleting process of the main key, and ending the operation;
if the customer chooses no, the operation is finished.
In the step c3, the method specifically comprises the following steps:
e1, displaying the prompt information: the slave key belongs to other main keys, and whether the user wants to modify the associated main key of the slave key is inquired;
if the user chooses: if yes, go to step e 2;
if the user chooses: if not, go to step e 4;
e2, acquiring the primary key with index relation of the current secondary key, and setting the primary key as the primary key to be released; finding a primary key to be released in the primary table;
e 3: in the associated data address field corresponding to the primary key to be released, the associated data address field corresponding to the secondary key is retrieved, and the state is set as: invalid;
e4, finishing the operation.
The technical scheme of the invention has simple structure and small used storage space, maintains the information of the address list in the memory and is suitable for the calculation requirements of low storage equipment such as a singlechip and the like; the detection is repeated when new data is added, and the duplicate checking function is completed when the new data is added, so that not only is the calculation time saved, but also duplicate checking is not needed during subsequent calculation, and the complexity of subsequent operation is reduced.
Claims (10)
1. The address book reconstruction preventing method suitable for equipment with limited storage space is characterized by comprising the following steps of:
s1: reading all address book data to be added into a memory of the equipment;
s2: determining the number n _ Directory of hash tables of the address list to be established according to the data type n _ Class contained in the address list data; the data of the corresponding type in each address book hash table is used as a key code, and the data except the key code is used as associated data and is stored in the table in the form of an associated data address;
namely: n _ Class is equal to n _ Directory, and both n _ Directory and n _ Class are positive integers;
s3: constructing n _ Directory hash tables of the address lists;
in each address book hash table, column elements of each row include: occupation flag, data field, chain index;
the field of the occupation flag is used for setting a use flag to indicate whether the record is used or not;
the fields of the data field are used for storing actual data, and the actual data comprises: a key data field, an associated data address field;
the related data address field stores an index address in another related address book hash table, and the index address stores other kinds of data with an index relation set with the key;
the address book hash table with the key code being the contact name is set as a master table, and the address book hash tables of other types are set as slave tables;
in the primary table, the number relationship between the key data field and the associated data address field is: num is a natural number, wherein Num is not less than (n _ Class-1); index information of all kinds of associated data except the key is stored in the associated data address field in the main table, wherein the number of the associated data address fields of the same kind is more than or equal to 1;
in the slave table, the number relationship between the key data field and the associated data address field is: 1: 1; only the address of the key of the primary table is stored in the associated data address field in the secondary table;
the field of the chain index is used for supporting a zipper method to process conflicts, and when a plurality of pieces of information need to occupy the same record position, the field is used for recording the index of the next record;
s4: initializing the length of the address book hash table to be N + N x y%;
wherein N is the basic capacity of the hash table, and N is a positive integer;
y is used for processing the space reservation rate of the Hash mapping conflict, and y is a positive integer; when data is newly added, if the data corresponding to the index obtained through calculation conflicts with the newly added data, a conflict chain needs to be sequentially hung behind the basic capacity N for placing the information of the conflicted contact person, and then N x y% of space outside the basic capacity is used for constructing the conflict chain;
s5: initializing all fields of the n _ Directory address book hash tables;
setting the occupied mark field of each address book hash table as follows: not used;
setting all of the chain index fields to: invalid;
initializing the use states of the associated data address fields corresponding to all keys as follows: invalid;
s6: acquiring all the address book data needing to be added read in the step S1, sequentially reading each address book data, and assigning values to the directory data of the address book data to be processed;
the directory data to be processed comprises: key code data KeyCode and associated data LinkCode; the quantity relationship between the key code data KeyCode and the associated data LinkCode is as follows: n _ Data, wherein n _ Data is a natural number;
according to the type of key code data KeyCode in the directory data DirectoryData to be processed, taking the address book hash table of the corresponding type as the directory hash table TargetDirectory to be processed;
s7: adding the directory data to be processed into the TargetDirectory of the hash table of the address book to be processed;
the method specifically comprises the following steps:
a 1: assigning the key code data Keycode to a key code TempKeycode to be processed; calculating the hash code of the TempKeycode to be processed by using a hash algorithm, and assuming that the value of the obtained hash code is HASHCODE;
a 2: calculating the chain index of the key code TempKeyCode to be processed;
using the hash code value hash code modulo N to obtain a remainder INDEX, where INDEX is the value of the chain INDEX field, and the details are as follows:
INDEX＝HASHCODE mod N；
a 3: in the address book hash table TargetDirectory to be processed, checking the corresponding occupied zone bit in the row at the INDEX position;
if the field of the occupied zone bit is: if not, indicating that the key data field in the data field corresponding to the key data field is not used, setting the row corresponding to INDEX as the row element to be inserted, and executing step a 6;
otherwise, indicating that the key data field in the data field corresponding to the key data field is used, executing step a 4;
a 4: obtaining data in a key code data field in the data field, and comparing the data serving as comparison data ComparCode with the key code TempKeyCode to be processed;
if the CompleeCode is the same as the TempKeyCode, the to-be-processed key code TempKeyCode is already in the hash table and does not need to be added again, and the adding operation for the to-be-processed key code TempKeyCode is finished at this time;
otherwise, the to-be-processed key TempKeyCode is not stored in the hash table, and the problem of data repetition does not exist, and step a5 is executed;
a 5: sequentially searching unoccupied rows of a first data field from an N x y% region behind the basic capacity N of the address book hash table TargetDirectory to be processed as row elements to be inserted, hanging at the tail of the conflict chain, and assigning the value of the INDEX of the last row at the tail of the conflict chain to INDEX;
a 6: storing the key to be processed TempKeycode into a field of key data in the data field in the row element to be inserted, wherein the corresponding chain INDEX automatically stores the value of INDEX;
s8: aiming at the key code TempKeycode to be processed, finding the corresponding associated data LinkCode in the same directory data to be processed, and setting the mutual index relationship between the key code TempKeyCode to be processed and the associated data LinkCode:
s9: and repeating the steps S6-S8 until all the address book data read in the step S1 are processed, and ending the construction operation.
2. The address book reconstruction preventing method applicable to devices with limited storage space according to claim 1, wherein the address book reconstruction preventing method comprises the following steps: in step S8, the method for setting the mutual index relationship between the to-be-processed key TempKeyCode and the associated data LinkCode includes the following steps:
b 1: confirming the number n _ Data of the LinkCode of the associated Data of the TempKeyCode to be processed in the directory Data DirectoryData to be processed;
if n _ Data is equal to 0, the LinkCode represents that the associated Data is empty, the associated index operation is not needed, and the operation of the current associated index is finished;
otherwise, performing step b 2;
b 2: confirming the kind of the key code TempKeycode to be processed;
if the kind of the key code to be processed TempKeyCode is a contact name, executing step b 3;
otherwise, performing step b 7;
b3, sequentially taking out each Data in the n _ Data associated Data LinkCodes, and sequentially setting the Data as to-be-confirmed associated Data TempLinkCodes;
b4, the key code to be processed TempKeyCode is a main key, the address book Hash table to be processed TargetDirectory corresponding to the key code to be processed is a main table, the associated data TempLinkCode to be confirmed is a slave key, and the address book Hash table corresponding to the associated data TempLinkCode is a slave table;
calling step S7, inserting the extracted associated data TempLinkCode to be confirmed into the slave table of the corresponding type according to the type of the associated data TempLinkCode, and recording the index address of the associated data TempLinkAddress in the slave table as TempLinkAddress;
b 5: taking INDEX as an INDEX address of the main key in the main table and TempLinkAddress as an INDEX address of the slave key in the slave table, and sequentially executing the following steps:
establishing an index relationship between the primary key and the secondary key in the secondary table;
establishing an index relationship between the slave key and the master key in the master table;
b6, repeating b 4-b 5 until the LinkCode of the n _ Data associated Data is searched; step b9 is executed;
b7, the key code to be processed TempKeyCode is a slave key, the address book hash table to be processed TargetDirectory corresponding to the key code to be processed is a slave table, the associated data LinkCode is a master key, and the address book hash table corresponding to the key code to be processed is a master table;
the associated data LinkCode to-be-confirmed associated data TempLinkCode;
step S7 is called, the to-be-confirmed associated data TempLinkCode is inserted into the main table, and the index address of the to-be-confirmed associated data TempLinkCode in the main table is recorded as TempLinkAddress;
b8, taking TempLinkAddress as the INDEX address of the main key in the main table and INDEX as the INDEX address of the slave table in the slave table, and sequentially executing the following steps:
establishing an index relationship between the slave key and the master key in the master table;
establishing an index relationship between the primary key and the secondary key in the secondary table;
b9, the operation of the current association index is finished.
3. The address book reconstruction preventing method suitable for the device with limited storage space according to claim 2, wherein the address book reconstruction preventing method comprises the following steps: in the slave table, establishing an index relationship between the master key and the slave key, including the following steps:
c1, setting the associated data address field corresponding to the slave key in the slave table as a slave key associated address field;
c2, confirming the state of the slave key association data address field;
if the state of the slave key associated data address field is: invalid, representing that the slave key is in the slave table, and if no associated index is established with the key code in the master table, storing the index address of the master key in the master table into the associated data address field of the slave key;
performing step c 4;
otherwise, representing that the slave key is in the corresponding slave table, and the associated index has been established with the key code in the master table, then step c3 is executed;
c 3: confirming whether the index relation is to be reestablished or not to the user;
if the index relationship needs to be reestablished, deleting the existing index relationship, and executing the step c 4;
otherwise, performing step c 5;
c4, establishing the index relationship between the slave key and the master key in the master table;
c5, finishing the operation.
4. The address book reconstruction preventing method suitable for the device with limited storage space according to claim 2, wherein the address book reconstruction preventing method comprises the following steps: in the primary table, establishing an index relationship between the secondary key and the primary key:
d 1: setting an associated data address field corresponding to the main key as a main key associated data address field in the main table;
sequentially acquiring the states of Num main key associated data address fields corresponding to the main keys;
d 2: confirming the state of each primary key associated data address field;
if the status of all the primary key associated data address fields is not invalid, then representing that all the primary key associated data address fields are used, performing step d 4;
otherwise, when the primary key associated data address field with the first invalid state is found, stopping the operation of confirming the state of the primary key associated data address field, and executing step d 3;
d3, storing the index address of the slave key in the slave table into the field, and ending the operation;
d4, prompting the user that the slave key can not be added to the main key, and inquiring whether the client wants to delete the associated data of the main key;
if the customer selects yes, entering a management data deleting process of the main key, and ending the operation;
if the customer chooses no, the operation is finished.
5. The address book reconstruction preventing method suitable for the device with limited storage space according to claim 3, wherein the address book reconstruction preventing method comprises the following steps: in the step c3, the method specifically comprises the following steps:
e1, displaying the prompt information: the slave key belongs to other main keys, and whether the user wants to modify the associated main key of the slave key is inquired;
if the user chooses: if yes, go to step e 2;
if the user chooses: if not, go to step e 4;
e2, acquiring the current primary key with index relation of the secondary key, and setting the current primary key as the primary key to be released; finding the primary key to be released in the primary table;
e 3: in the associated data address field corresponding to the primary key to be released, retrieving the associated data address field corresponding to the secondary key, and setting the state of the associated data address field to be: invalid;
e4, finishing the operation.
6. The address book reconstruction preventing method applicable to devices with limited storage space according to claim 1, wherein the address book reconstruction preventing method comprises the following steps: the structure of the address book basic hash table is realized through arrays.
7. The address book reconstruction preventing method applicable to the device with limited storage space according to claim 6, wherein the address book reconstruction preventing method comprises the following steps: the address book data comprises a data type n _ Class with a value of 2, and the data type comprises: contact name, phone number; the number n _ Directory of the address book hash tables is 2, and the address book hash tables comprise contact name hash tables and telephone number hash tables.
8. The address book reconstruction preventing method applicable to devices with limited storage space according to claim 7, wherein the address book reconstruction preventing method comprises the following steps: in the contact name hash table, if the number of the user behaviors expected to be stored in the hash table is X, the number of array elements of the contact name hash table is M:
M＝(1+x％)*X
in the formula: x is a reserved rate of newly-added contacts preset according to the product use environment; and aiming at the contact name hash table, wherein the number of array elements of the contact name hash table is M, namely the basic capacity N of the contact name hash table.
9. The address book reconstruction preventing method applicable to devices with limited storage space according to claim 8, wherein the address book reconstruction preventing method comprises the following steps: in the phone number hash table corresponding to the contact name hash table, the number element quantity P of the phone number hash table conforms to the following formula:
P＝M*p
in the formula: m is the length of the hash table of the contact names, and p is the maximum number of the telephones which can be owned by one contact; and aiming at the telephone number hash table, the array element quantity P of the telephone number hash table is the basic capacity N of the telephone number hash table.
10. The address book reconstruction preventing method applicable to devices with limited storage space according to claim 1, wherein the address book reconstruction preventing method comprises the following steps: the value range of the space reservation rate y% is as follows: 20 percent to y percent to 30 percent.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910906677.4A CN110688380B (en) | 2019-09-24 | 2019-09-24 | Address book anti-reconstruction method suitable for equipment with limited storage space |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910906677.4A CN110688380B (en) | 2019-09-24 | 2019-09-24 | Address book anti-reconstruction method suitable for equipment with limited storage space |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN110688380A true CN110688380A (en) | 2020-01-14 |
| CN110688380B CN110688380B (en) | 2023-02-03 |
Family
ID=69109968
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910906677.4A Active CN110688380B (en) | 2019-09-24 | 2019-09-24 | Address book anti-reconstruction method suitable for equipment with limited storage space |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN110688380B (en) |
Citations (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101079034A (en) * | 2006-07-10 | 2007-11-28 | 腾讯科技（深圳）有限公司 | System and method for eliminating redundancy file of file storage system |
| US20080235260A1 (en) * | 2007-03-23 | 2008-09-25 | International Business Machines Corporation | Scalable algorithms for mapping-based xml transformation |
| US20100179954A1 (en) * | 2009-01-09 | 2010-07-15 | Linkage Technology Group Co., Ltd. | Quick Mass Data Manipulation Method Based on Two-Dimension Hash |
| CN101997875A (en) * | 2010-10-29 | 2011-03-30 | 北京大学 | Secure multi-party network communication platform and construction method and communication method thereof |
| CN102521228A (en) * | 2011-11-01 | 2012-06-27 | 浙江省电力试验研究院 | Key value mapping method for linear data table |
| CN102572050A (en) * | 2010-12-09 | 2012-07-11 | 希姆通信息技术（上海）有限公司 | Mobile phone contacts number inquiry information processing method |
| CN103226591A (en) * | 2013-04-15 | 2013-07-31 | 厦门亿联网络技术股份有限公司 | Method and device for supporting quick access of multiple keywords |
| CN104462328A (en) * | 2014-12-02 | 2015-03-25 | 深圳中科讯联科技有限公司 | Blended data management method and device based on Hash tables and dual-circulation linked list |
| US20150370835A1 (en) * | 2014-06-24 | 2015-12-24 | Infinidat Ltd. | Hash based de-duplication in a storage system |
| CN105393220A (en) * | 2013-05-15 | 2016-03-09 | 思杰系统有限公司 | Systems and methods for deploying a spotted virtual server in a cluster system |
| CN109358987A (en) * | 2018-10-26 | 2019-02-19 | 黄淮学院 | A kind of backup cluster based on two-stage data deduplication |
-
2019
- 2019-09-24 CN CN201910906677.4A patent/CN110688380B/en active Active
Patent Citations (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101079034A (en) * | 2006-07-10 | 2007-11-28 | 腾讯科技（深圳）有限公司 | System and method for eliminating redundancy file of file storage system |
| US20080235260A1 (en) * | 2007-03-23 | 2008-09-25 | International Business Machines Corporation | Scalable algorithms for mapping-based xml transformation |
| US20100179954A1 (en) * | 2009-01-09 | 2010-07-15 | Linkage Technology Group Co., Ltd. | Quick Mass Data Manipulation Method Based on Two-Dimension Hash |
| CN101997875A (en) * | 2010-10-29 | 2011-03-30 | 北京大学 | Secure multi-party network communication platform and construction method and communication method thereof |
| CN102572050A (en) * | 2010-12-09 | 2012-07-11 | 希姆通信息技术（上海）有限公司 | Mobile phone contacts number inquiry information processing method |
| CN102521228A (en) * | 2011-11-01 | 2012-06-27 | 浙江省电力试验研究院 | Key value mapping method for linear data table |
| CN103226591A (en) * | 2013-04-15 | 2013-07-31 | 厦门亿联网络技术股份有限公司 | Method and device for supporting quick access of multiple keywords |
| CN105393220A (en) * | 2013-05-15 | 2016-03-09 | 思杰系统有限公司 | Systems and methods for deploying a spotted virtual server in a cluster system |
| US20150370835A1 (en) * | 2014-06-24 | 2015-12-24 | Infinidat Ltd. | Hash based de-duplication in a storage system |
| CN104462328A (en) * | 2014-12-02 | 2015-03-25 | 深圳中科讯联科技有限公司 | Blended data management method and device based on Hash tables and dual-circulation linked list |
| CN109358987A (en) * | 2018-10-26 | 2019-02-19 | 黄淮学院 | A kind of backup cluster based on two-stage data deduplication |
Non-Patent Citations (4)
| Title |
|---|
| IDREOS S 等: "Continuous multi-way joins over distributed hash tables", 《PROCEEDINGS OF THE 11TH INTERNATIONAL CONFERENCE ON EXTENDING DATABASE TECHNOLOGY: ADVANCES IN DATABASE TECHNOLOGY》 * |
| 吴朋朋 等: "移动终端通讯录数据同步去重算法", 《2013年中国信息通信研究新进展论文集》 * |
| 吴朋朋: "移动终端通讯录数据去重合并关键技术研究", 《中国优秀硕士学位论文全文数据库信息科技辑》 * |
| 贺元香等: "除留余数法建立哈希表的方法改进", 《甘肃科技》 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN110688380B (en) | 2023-02-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110275884B (en) | Data storage method and node | |
| CN110413611B (en) | Data storage and query method and device | |
| EP0124097B1 (en) | Method for storing and retrieving data in a data base | |
| CN109634932B (en) | Intelligent contract storage method and storage system | |
| CN105488050B (en) | A kind of more indexing means of database, apparatus and system | |
| CN108205577B (en) | Array construction method, array query method, device and electronic equipment | |
| CN109918341B (en) | Log processing method and device | |
| CN105224532B (en) | Data processing method and device | |
| CN101685468A (en) | Content addressable storage systems and methods employing searchable blocks | |
| CN114153848B (en) | Block chain data storage method and device and electronic equipment | |
| CN112988761A (en) | Block chain data storage method and device and electronic equipment | |
| US20200142875A1 (en) | Random walking and cluster-based random walking method, apparatus and device | |
| CN110688380B (en) | Address book anti-reconstruction method suitable for equipment with limited storage space | |
| CN112632187B (en) | Attribute hiding and canceling method based on counting bloom filter | |
| CN112306748B (en) | Data recovery method, device and storage medium | |
| CN114840487A (en) | Metadata management method and device for distributed file system | |
| CN113779286A (en) | Method and device for managing graph data | |
| CN112488708B (en) | Block chain account relevance query method and false transaction screening method | |
| CN110569291B (en) | Key data query and acquisition method and device for digital currency wallet | |
| CN111625543B (en) | Method for realizing globally monotonically increasing sequence based on HBase table | |
| CN106557583A (en) | Archival storage and archives storage method | |
| CN108984780B (en) | Method and device for managing disk data based on data structure supporting repeated key value tree | |
| CN112988911B (en) | Block chain data storage method and device and electronic equipment | |
| CN106469042B (en) | The generation method and device of pseudo random number | |
| JP6123372B2 (en) | Information processing system, name identification method and program |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |