[發(fā)明專利]一種基于哈希查找的Flash檢索方法及存儲介質(zhì)

在審

• 申請?zhí)枺?/td>: 202010400678.4
• 申請日: 2020-05-13
• 公開（公告）號: CN111651372A
• 公開（公告）日: 2020-09-11
• 發(fā)明（設(shè)計）人: 沈坤;王建國;聶思靜;梁美紅;陳秀瓊;王敏敏
• 申請（專利權(quán)）人: 湖北三江航天萬峰科技發(fā)展有限公司
• 主分類號: G06F12/02
• 分類號: G06F12/02
• 代理公司: 武漢東喻專利代理事務(wù)所(普通合伙) 42224
• 代理人: 雷霄

本發(fā)明公開了一種基于哈希查找的Flash檢索方法及存儲介質(zhì)。該方法包括步驟：接收待存儲的數(shù)據(jù)，每份數(shù)據(jù)具有唯一的關(guān)鍵值，根據(jù)預(yù)先構(gòu)建的哈希函數(shù)和每份數(shù)據(jù)的關(guān)鍵值，計算每份數(shù)據(jù)的哈希值；在Flash中創(chuàng)建索引表，每份數(shù)據(jù)的哈希值表示該份數(shù)據(jù)在索引表中的索引位置，建立索引表中的索引位置與Flash存儲頁的映射關(guān)系；根據(jù)每份數(shù)據(jù)的哈希值和所述映射關(guān)系確定每份數(shù)據(jù)的Flash存儲頁，將數(shù)據(jù)存儲到對應(yīng)的Flash存儲頁中。本發(fā)明具有檢索效率高的優(yōu)點。

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)檢索技術(shù)領(lǐng)域，更具體地，涉及一種基于哈希查找的Flash檢索方法及存儲介質(zhì)。

背景技術(shù)

在嵌入式產(chǎn)品設(shè)計中，通常需要存儲一些配置參數(shù)、運行狀態(tài)、運行結(jié)果等數(shù)據(jù)。而且這些數(shù)據(jù)需要能長期保存，不能在掉電時丟失。檢索存儲數(shù)據(jù)的效率，將直接影響產(chǎn)品的性能，甚至決定產(chǎn)品設(shè)計的成敗。

常見的查找算法有順序查找、二分查找、二叉排序樹查找。對于嵌入式單片機上的Flash檢索，其儲存和可使用的空間有限，所以不太適合二叉排序樹，同時對于檢索的速度有要求，在存儲和檢索的數(shù)據(jù)量比較大時，順序查找和二分查找在時間要求上也不適合。

發(fā)明內(nèi)容

針對現(xiàn)有技術(shù)的至少一個缺陷或改進(jìn)需求，本發(fā)明提供了一種基于哈希查找的Flash檢索方法及存儲介質(zhì)，可以讓Flash中有限的存儲空間內(nèi)存放更多的數(shù)據(jù)，同時還能保證數(shù)據(jù)檢索的高效性。

為實現(xiàn)上述目的，按照本發(fā)明的第一方面，提供了一種基于哈希查找的Flash檢索方法，包括：

接收待存儲的數(shù)據(jù)，每份數(shù)據(jù)具有唯一的關(guān)鍵值，根據(jù)預(yù)先構(gòu)建的哈希函數(shù)和每份數(shù)據(jù)的關(guān)鍵值，計算每份數(shù)據(jù)的哈希值；

在Flash中創(chuàng)建索引表，每份數(shù)據(jù)的哈希值表示該份數(shù)據(jù)在索引表中的索引位置，建立索引表中的索引位置與Flash存儲頁的映射關(guān)系；

根據(jù)每份數(shù)據(jù)的哈希值和所述映射關(guān)系確定每份數(shù)據(jù)的Flash存儲頁，將數(shù)據(jù)存儲到對應(yīng)的Flash存儲頁。

優(yōu)選地，若多份數(shù)據(jù)計算的哈希值相同，則多份數(shù)據(jù)在索引表中的索引位置相同，將該多份數(shù)據(jù)按序存儲到該索引位置對應(yīng)的Flash存儲頁。

優(yōu)選地，所述將該多份數(shù)據(jù)按序存儲到該索引位置對應(yīng)的Flash存儲頁中，當(dāng)存儲后一份數(shù)據(jù)時，若該索引位置對應(yīng)的Flash存儲頁沒有空余存儲空間，則查找空白的Flash存儲頁，將后一份數(shù)據(jù)存儲到該空白的Flash存儲頁，建立后一份數(shù)據(jù)的Flash存儲頁與該索引位置對應(yīng)的Flash存儲頁的鏈接關(guān)系。

優(yōu)選地，F(xiàn)lash檢索方法還包括：

接收數(shù)據(jù)查詢請求，所述數(shù)據(jù)查詢請求中包括待查詢數(shù)據(jù)的關(guān)鍵值；

根據(jù)待查詢數(shù)據(jù)的關(guān)鍵值及所述哈希函數(shù)計算待查詢數(shù)據(jù)的哈希值；

根據(jù)待查詢數(shù)據(jù)的哈希值獲取待查詢在索引表中的索引位置，在該索引位置對應(yīng)的Flash存儲頁查找待查詢數(shù)據(jù)并返回查詢結(jié)果。

優(yōu)選地，若待查詢數(shù)據(jù)的索引位置對應(yīng)的Flash存儲頁沒有找到待查詢數(shù)據(jù)，并且待查詢數(shù)據(jù)的索引位置對應(yīng)的Flash存儲頁鏈接到另一Flash存儲頁，則繼續(xù)在該另一Flash存儲頁查找待查詢數(shù)據(jù)并返回查詢結(jié)果。

優(yōu)選地，F(xiàn)lash檢索方法還包括：

接收數(shù)據(jù)刪除請求，所述數(shù)據(jù)刪除請求中包括待刪除數(shù)據(jù)的關(guān)鍵值；

根據(jù)待刪除數(shù)據(jù)的關(guān)鍵值及所述哈希函數(shù)計算待刪除數(shù)據(jù)的哈希值；

根據(jù)待刪除數(shù)據(jù)的哈希值獲取待刪除數(shù)據(jù)在索引表中的索引位置，在該索引位置對應(yīng)的Flash存儲頁查詢并刪除待刪除數(shù)據(jù)。