[發(fā)明專利]適用于存儲空間受限的設(shè)備的通訊錄防重構(gòu)建方法

有效

• 申請?zhí)枺?/td>: 201910906677.4
• 申請日: 2019-09-24
• 公開（公告）號: CN110688380B
• 公開（公告）日: 2023-02-03
• 發(fā)明（設(shè)計）人: 李立亞;吳麗;閭立新
• 申請（專利權(quán)）人: 無錫科技職業(yè)學(xué)院
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 無錫盛陽專利商標(biāo)事務(wù)所(普通合伙) 32227
• 代理人: 顧吉云;黃瑩

1.適用于存儲空間受限的設(shè)備的通訊錄防重構(gòu)建方法，其特征在于，其包括以下步驟：

S1：把所有的需要添加的通訊錄數(shù)據(jù)讀入設(shè)備的內(nèi)存中；

S2：根據(jù)所述通訊錄數(shù)據(jù)中包含數(shù)據(jù)種類n_Class，確定需要建立通訊錄哈希表的數(shù)量n_Directory；每一個所述通訊錄哈希表中以其對應(yīng)種類的數(shù)據(jù)作為關(guān)鍵碼，所述關(guān)鍵碼以外的數(shù)據(jù)作為關(guān)聯(lián)數(shù)據(jù)、以關(guān)聯(lián)數(shù)據(jù)地址的形式存儲在該表中；

即：n_Class等于n_Directory，且n_Directory、n_Class都為正整數(shù)；

S3：構(gòu)建n_Directory個所述通訊錄哈希表；

在每一個所述通訊錄哈希表中，每一行的列元素包括：占用標(biāo)志、數(shù)據(jù)域、鏈索引；

所述占用標(biāo)志的字段用來設(shè)置使用標(biāo)志，表示該占用標(biāo)志對應(yīng)行的記錄是否已經(jīng)被使用；

所述數(shù)據(jù)域的字段用來存放實際數(shù)據(jù)，所述實際數(shù)據(jù)包括：關(guān)鍵碼數(shù)據(jù)字段、關(guān)聯(lián)數(shù)據(jù)地址字段；

所述關(guān)聯(lián)數(shù)據(jù)地址字段存儲了在另外的關(guān)聯(lián)通訊錄哈希表中的索引地址，該索引地址存儲了與所述關(guān)鍵碼設(shè)置了索引關(guān)系的其他種類的數(shù)據(jù)；

所述關(guān)鍵碼為聯(lián)系人姓名的所述通訊錄哈希表設(shè)置為主表，其他種類的所述通訊錄哈希表設(shè)置為從表；

在所述主表中，所述關(guān)鍵碼數(shù)據(jù)字段和所述關(guān)聯(lián)數(shù)據(jù)地址字段的數(shù)量關(guān)系為：1:Num，其中Num為自然數(shù)，且Num≥(n_Class-1)；所述主表中的所述關(guān)聯(lián)數(shù)據(jù)地址字段中，保存了所述關(guān)鍵碼以外的其他所有種類的關(guān)聯(lián)數(shù)據(jù)的索引信息，其中同一種類的所述關(guān)聯(lián)數(shù)據(jù)地址字段的數(shù)量大于等于1；

在所述從表中，所述關(guān)鍵碼數(shù)據(jù)字段和所述關(guān)聯(lián)數(shù)據(jù)地址字段的數(shù)量關(guān)系為：1:1；所述從表中的所述關(guān)聯(lián)數(shù)據(jù)地址字段中，只保存所述主表的關(guān)鍵碼的地址；

所述鏈索引的字段用來支撐拉鏈法處理沖突，當(dāng)多條信息需占用同一記錄位置時，該字段用來記錄下一條記錄的索引；

S4：初始化所述通訊錄哈希表長度為N+N*y％；

其中，N為哈希表的基本容量，N為正整數(shù)；

y％用于處理哈希映射沖突的空間預(yù)留率，y為正整數(shù)；當(dāng)新增數(shù)據(jù)時，如果計算得到索引對應(yīng)的數(shù)據(jù)與新增數(shù)據(jù)發(fā)生沖突，需要在基本容量N的后面順序的掛接一個沖突鏈，用來放置發(fā)生沖突的聯(lián)系人信息，此時就會使用到基本容量以外的N*y％的空間來構(gòu)建沖突鏈；

S5：初始化所有的n_Directory個所述通訊錄哈希表的字段；

將每個所述通訊錄哈希表的所述占用標(biāo)志字段設(shè)置為：未使用；

將所有的所述鏈索引字段設(shè)置為：無效；

將所有關(guān)鍵碼對應(yīng)的所述關(guān)聯(lián)數(shù)據(jù)地址字段的使用狀態(tài)都初始化為：無效；

S6：獲取步驟S1中讀入所有的需要添加的所述通訊錄數(shù)據(jù)，依次讀取每一條通訊錄數(shù)據(jù)，賦值給待處理通訊錄數(shù)據(jù)DirectoryData；

所述待處理通訊錄數(shù)據(jù)DirectoryData包括：關(guān)鍵碼數(shù)據(jù)KeyCode、關(guān)聯(lián)數(shù)據(jù)LinkCode；其中，所述關(guān)鍵碼數(shù)據(jù)KeyCode和所述關(guān)聯(lián)數(shù)據(jù)LinkCode的數(shù)量關(guān)系為：1:n_Data，其中n_Data為自然數(shù)；

根據(jù)所述待處理通訊錄數(shù)據(jù)DirectoryData中關(guān)鍵碼數(shù)據(jù)KeyCode的種類，其對應(yīng)種類的通訊錄哈希表作為待處理通訊錄哈希表TargetDirectory；

S7：添加所述待處理通訊錄數(shù)據(jù)DirectoryData到所述待處理通訊錄哈希表TargetDirectory中；

具體包括以下步驟：

a1：將所述關(guān)鍵碼數(shù)據(jù)KeyCode賦值給待處理關(guān)鍵碼TempKeyCode；使用哈希算法計算所述待處理關(guān)鍵碼TempKeyCode的哈希碼，設(shè)定得到的哈希碼的值為HASHCODE；

a2：計算所述待處理關(guān)鍵碼TempKeyCode的所述鏈索引；

使用哈希碼的值HASHCODE模上N，得到余數(shù)INDEX，INDEX即為所述鏈索引字段的值，具體如下：

INDEX＝HASHCODE mod N；

a3：在所述待處理通訊錄哈希表TargetDirectory中，檢查INDEX處的行中對應(yīng)的所述占用標(biāo)志位；

如果所述占用標(biāo)志位的字段為：未使用，則表示其對應(yīng)的所述數(shù)據(jù)域中的關(guān)鍵碼數(shù)據(jù)字段沒有被使用，則INDEX對應(yīng)的行設(shè)置為待插入行元素，執(zhí)行步驟a6；

否則，則表示其對應(yīng)的所述數(shù)據(jù)域中的關(guān)鍵碼數(shù)據(jù)字段已經(jīng)被使用，執(zhí)行步驟a4；

a4：取得所述數(shù)據(jù)域中的關(guān)鍵碼數(shù)據(jù)字段中的數(shù)據(jù)，作為對比數(shù)據(jù)CompareCode與所述待處理關(guān)鍵碼TempKeyCode進(jìn)行比較；

如果CompareCode與TempKeyCode相同，則表示所述待處理關(guān)鍵碼TempKeyCode已經(jīng)存在于哈希表中，不需要再次添加，本次針對待處理關(guān)鍵碼TempKeyCode的添加操作結(jié)束；

否則，表示所述待處理關(guān)鍵碼TempKeyCode在哈希表中沒有被存儲過，不存在數(shù)據(jù)重復(fù)問題，執(zhí)行步驟a5；

a5：從所述待處理通訊錄哈希表TargetDirectory的基本容量N后面的N*y％區(qū)域中順序的搜索第一個數(shù)據(jù)域未被占用的行設(shè)置為待插入行元素，掛接在所述沖突鏈的末尾，且把所述沖突鏈尾部最后一行的索引的值賦值給INDEX；

a6：將所述待處理關(guān)鍵碼TempKeyCode，存入所述待插入行元素中所述數(shù)據(jù)域中的關(guān)鍵碼數(shù)據(jù)的字段中，其對應(yīng)的所述鏈索引自動存儲INDEX的值；

S8：針對所述待處理關(guān)鍵碼TempKeyCode，在同一條所述待處理通訊錄數(shù)據(jù)DirectoryData中找到對應(yīng)的所述關(guān)聯(lián)數(shù)據(jù)LinkCode，設(shè)置所述待處理關(guān)鍵碼TempKeyCode與所述關(guān)聯(lián)數(shù)據(jù)LinkCode的相互的索引關(guān)系：

S9：重復(fù)步驟S6～S8，直至步驟S1中讀入的所有的所述通訊錄數(shù)據(jù)都處理完畢，結(jié)束本次構(gòu)建操作。