[發(fā)明專利]一種數(shù)組構(gòu)建、數(shù)組查詢的方法、裝置及電子設(shè)備

有效

• 申請?zhí)枺?/td>: 201611187039.4
• 申請日: 2016-12-20
• 公開（公告）號(hào): CN108205577B
• 公開（公告）日: 2022-06-03
• 發(fā)明（設(shè)計(jì)）人: 代兵
• 申請（專利權(quán)）人: 阿里巴巴集團(tuán)控股有限公司
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22;G06F16/2453
• 代理公司: 北京清源匯知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 11644
• 代理人: 馮德魁

本申請公開了一種數(shù)組構(gòu)建的方法、裝置、一種電子設(shè)備、一種數(shù)組查詢的方法、裝置以及另一種電子設(shè)備。其中，所述數(shù)組構(gòu)建的方法包括：根據(jù)待存儲(chǔ)的各字段的取值，確定能存儲(chǔ)各字段的取值所需的比特位數(shù)；將比特位數(shù)作為數(shù)組元素的容量建立數(shù)組；將各字段的取值存儲(chǔ)到數(shù)組的數(shù)組元素內(nèi)。采用上述方法通過鍵值對(duì)的鍵值所占用的最大空間，將bitmap數(shù)組中數(shù)組元素的容量進(jìn)行擴(kuò)容，將常規(guī)的數(shù)組元素的容量從一個(gè)bit位擴(kuò)展到能存放下鍵值所占用的最大內(nèi)存空間的bit位數(shù)，并以擴(kuò)展容量后的數(shù)組元素為單位創(chuàng)建數(shù)組，擴(kuò)展了使用bitmap數(shù)組查詢的使用場景，這種結(jié)構(gòu)相對(duì)于hash表查詢，不進(jìn)行hash值的函數(shù)的計(jì)算，也無hash值的沖突處理，只需要O(1)的時(shí)間復(fù)雜度，查詢效率高。

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

本申請涉及數(shù)據(jù)處理技術(shù)領(lǐng)域，具體涉及一種數(shù)組構(gòu)建的方法以及一種數(shù)組查詢的方法；本申請同時(shí)涉及一種數(shù)組構(gòu)建的裝置、一種電子設(shè)備、一種數(shù)組查詢的裝置以及另一種電子設(shè)備。

背景技術(shù)

隨著計(jì)算機(jī)信息技術(shù)的快速發(fā)展，越來越多的用戶對(duì)數(shù)據(jù)的存儲(chǔ)和查詢提出了更高的要求。目前在大量數(shù)據(jù)信息中進(jìn)行特定數(shù)據(jù)元素的查詢時(shí)，常使用bitmap(位圖)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)快速查詢以及存儲(chǔ)數(shù)據(jù)。bitmap數(shù)據(jù)結(jié)構(gòu)以key-value(鍵值對(duì))的數(shù)據(jù)存儲(chǔ)都是基于一個(gè)字段作為key，將bitmap中每一個(gè)bit位來表示一個(gè)key對(duì)應(yīng)的value，key不單獨(dú)占用存儲(chǔ)空間，通過在bitmap中的偏移bit來表示。由于bitmap是使用每一個(gè)bit位單獨(dú)存放value，所以value的值為只能為0或1，例如：用數(shù)字表示的用戶ID時(shí)，key可以表示為int類型，而且value只有兩個(gè)值可以表示為用戶在線或不在線，此時(shí)使用bitmap數(shù)組來查詢非常高效。

而當(dāng)value為字符或字符串類型，不能使用數(shù)值類型來表達(dá)時(shí)，就無法使用bitmap數(shù)據(jù)結(jié)構(gòu)來查詢數(shù)據(jù)元素，此時(shí)常使用hashtable(hash表)來提高查詢效率。使用hash表來進(jìn)行查詢時(shí)，在數(shù)據(jù)元素的數(shù)目較大的情況下，由于對(duì)key進(jìn)行hash值計(jì)算時(shí)，計(jì)算出的hash值可能會(huì)存在沖突，在hash值沖突以及hash桶遍歷都需要一些計(jì)算資源，即使增加表項(xiàng)容量，也并不能改善沖突率，同時(shí)也增加了內(nèi)存消耗。

由此可見，在現(xiàn)有的快速查詢方案下，如果使用bitmap數(shù)據(jù)結(jié)構(gòu)來查詢數(shù)據(jù)元素，則要求value只能包含0或1兩個(gè)值，使用場景有限；對(duì)于不能使用bitmap數(shù)據(jù)結(jié)構(gòu)來查詢數(shù)據(jù)元素的情況下，使用hash表作為替代方案時(shí)，計(jì)算hash值以及在hash沖突時(shí)查詢的計(jì)算代價(jià)高，相對(duì)于bitmap的時(shí)間復(fù)雜度較高。

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

本申請?zhí)峁┝艘环N數(shù)組構(gòu)建的方法以及一種數(shù)組查詢的方法，以解決現(xiàn)有技術(shù)中的上述問題。本申請同時(shí)提供了一種數(shù)組構(gòu)建的裝置、一種電子設(shè)備、一種數(shù)組查詢的裝置以及另一種電子設(shè)備。

本申請實(shí)施例提供了一種數(shù)組構(gòu)建的方法，所述數(shù)組構(gòu)建的方法，包括：

根據(jù)待存儲(chǔ)的各字段的取值，確定能存儲(chǔ)各字段的取值所需的比特位數(shù)；

將所述比特位數(shù)作為數(shù)組元素的容量建立數(shù)組；

將各字段的取值存儲(chǔ)到所述數(shù)組的數(shù)組元素內(nèi)。

可選的，所述字段，包括：鍵值對(duì)。

可選的，所述根據(jù)待存儲(chǔ)的各字段的取值，確定能存儲(chǔ)各字段的取值所需的比特位數(shù)，包括：

根據(jù)待存儲(chǔ)的各鍵值對(duì)的鍵值，確定存儲(chǔ)最大鍵值占用的比特位數(shù)；或者

根據(jù)待存儲(chǔ)的各鍵值對(duì)預(yù)設(shè)的鍵值容量，確定所述鍵值容量占用的比特位數(shù)。

可選的，所述將所述比特位數(shù)作為數(shù)組元素的容量建立數(shù)組時(shí)，包括：

按照所述數(shù)組元素在所述數(shù)組內(nèi)的偏移位置，為所述數(shù)組元素設(shè)置下標(biāo)。

可選的，所述將各字段的取值存儲(chǔ)到所述數(shù)組的數(shù)組元素內(nèi)，包括：