HashMap優(yōu)化及其在列存儲(chǔ)數(shù)據(jù)庫(kù)查詢(xún)中的應(yīng)用*

母紅芬，李　征+，霍衛(wèi)平，金正皓

1.北京化工大學(xué) 計(jì)算機(jī)系，北京 1000292.北京東方國(guó)信科技股份有限公司，北京 100102

HashMap優(yōu)化及其在列存儲(chǔ)數(shù)據(jù)庫(kù)查詢(xún)中的應(yīng)用*

母紅芬1，李征1+，霍衛(wèi)平2，金正皓2

1.北京化工大學(xué) 計(jì)算機(jī)系，北京 100029
2.北京東方國(guó)信科技股份有限公司，北京 100102

HashMap在基本字典操作中具有常數(shù)級(jí)別的平均算法時(shí)間復(fù)雜度，廣泛應(yīng)用于大數(shù)據(jù)的檢索。Block_HashMap（BHMap）基于C++HashMap，其優(yōu)化包括三方面：哈希函數(shù)選取，沖突解決和關(guān)鍵字匹配。優(yōu)化核心在于沖突解決時(shí)，以鏈地址法為基礎(chǔ)，提出了一種高效利用高速緩存的存儲(chǔ)結(jié)構(gòu)Block_List來(lái)存儲(chǔ)沖突的數(shù)據(jù)，并且預(yù)先緩存哈希值，節(jié)省匹配時(shí)間。實(shí)驗(yàn)證明，在桶數(shù)目充足的情況下，BHMap會(huì)多消耗少部分內(nèi)存，但在桶數(shù)目有限，數(shù)據(jù)重復(fù)率比較低的情況下，時(shí)間性能上相對(duì)C++標(biāo)準(zhǔn)模板庫(kù)中的Map提升10倍以上，比unordered_map快3.5倍以上，且消耗的內(nèi)存與unordered_map相差不大。在列存儲(chǔ)數(shù)據(jù)庫(kù)分組和連接查詢(xún)中，關(guān)鍵字的分桶、解決沖突和匹配操作也都涉及到基于哈希的技術(shù)，最終把BHMap應(yīng)用到列存儲(chǔ)數(shù)據(jù)庫(kù)的關(guān)鍵查詢(xún)中。

哈希圖；分組；連接；緩存感知；緩存不敏感；列存儲(chǔ)數(shù)據(jù)庫(kù)；BHMap

1　引言

隨著云計(jì)算與大數(shù)據(jù)的廣泛應(yīng)用，大數(shù)據(jù)集的實(shí)時(shí)動(dòng)態(tài)分析成為研究熱點(diǎn)。高效的數(shù)據(jù)查詢(xún)、分析操作是實(shí)現(xiàn)該目標(biāo)的重要技術(shù)手段。

在大數(shù)據(jù)技術(shù)中，HashMap查找速度快，查詢(xún)、插入、刪除操作的平均復(fù)雜時(shí)間度為O(1)，屬于常數(shù)級(jí)別，查詢(xún)時(shí)間與數(shù)據(jù)集大小無(wú)關(guān)。在眾多數(shù)據(jù)庫(kù)如Oracle、MonentDB/X100[1]、C-Store、Microsoft SQL Server 2012[2]等都使用了HashMap。

HashMap是基于哈希表的數(shù)據(jù)結(jié)構(gòu)，按照key值給每一個(gè)元素分桶，使用哈希函數(shù)對(duì)key值操作，返回哈希值，然后再將(key,value)存放到hashcode對(duì)應(yīng)的桶中。哈希函數(shù)的選取直接影響分桶的效率，而對(duì)于不同的關(guān)鍵字，經(jīng)過(guò)哈希函數(shù)分桶，出現(xiàn)了相同的哈希值，就會(huì)產(chǎn)生“沖突”。

傳統(tǒng)解決沖突的方法是鏈地址法，即將沖突的數(shù)據(jù)以指針鏈表的方式存儲(chǔ)在相應(yīng)的桶后，當(dāng)系統(tǒng)分配的桶數(shù)目不夠時(shí)，進(jìn)行rehash，重新申請(qǐng)桶。使用鏈表方式來(lái)存儲(chǔ)(key,value)，在匹配查找過(guò)程中，會(huì)頻繁地讀取指針指向的內(nèi)存。隨著數(shù)據(jù)量的增大，時(shí)間消耗也急劇增大；同時(shí)rehash策略動(dòng)態(tài)增加桶數(shù)目也會(huì)引起新的時(shí)間開(kāi)銷(xiāo)。

國(guó)內(nèi)外對(duì)HashMap的研究主要集中在使用該結(jié)構(gòu)體實(shí)現(xiàn)數(shù)據(jù)的高效查詢(xún)和插入，大部分直接使用封裝好的接口，很少對(duì)該結(jié)構(gòu)進(jìn)行優(yōu)化。

本文針對(duì)上述情況，考慮分桶效率、緩存利用率和匹配效率，對(duì)HashMap提出以下優(yōu)化策略：（1）在哈希函數(shù)分桶過(guò)程中，使用“按位與”操作代替?zhèn)鹘y(tǒng)的“取模”操作，縮短定址時(shí)間；（2）在解決沖突時(shí)，使用“塊鏈地址法”取代現(xiàn)有的“鏈地址法”，提出存儲(chǔ)結(jié)構(gòu)Block_List，減少指針尋址時(shí)間；（3）在匹配查找時(shí)，在結(jié)構(gòu)體中增加存儲(chǔ)哈希值，將匹配字符串key值改為匹配數(shù)值型哈希值，節(jié)省查找時(shí)間。結(jié)合以上優(yōu)化策略，提出一種數(shù)據(jù)結(jié)構(gòu)BHMap（Block_HashMap），用其解決傳統(tǒng)的HashMap在桶數(shù)目有限，數(shù)據(jù)key重復(fù)率較低情況下的性能瓶頸，最后將BHMap應(yīng)用于列存儲(chǔ)數(shù)據(jù)庫(kù)中，以提高查詢(xún)效率。

本文通過(guò)一個(gè)基準(zhǔn)的計(jì)數(shù)應(yīng)用在千萬(wàn)級(jí)數(shù)據(jù)集上驗(yàn)證BHMap的性能，并與C++標(biāo)準(zhǔn)庫(kù)的Map和unordered_map進(jìn)行比較，結(jié)果顯示，當(dāng)桶數(shù)有限，數(shù)值重復(fù)率較低時(shí)，BHMap只在增加少部分內(nèi)存消耗的情況下，查詢(xún)速度就能比unordered_map快3.5倍以上，比Map快10倍以上。本文給出了BHMap的優(yōu)化方法以及調(diào)用API，通過(guò)在列存儲(chǔ)數(shù)據(jù)庫(kù)的分組和連接查詢(xún)中使用該數(shù)據(jù)結(jié)構(gòu)，說(shuō)明其在大數(shù)據(jù)查詢(xún)中的適用性。

2　背景及相關(guān)工作

哈希技術(shù)在大數(shù)據(jù)環(huán)境下應(yīng)用廣泛，能實(shí)現(xiàn)海量數(shù)據(jù)的高效插入和查詢(xún)。本章主要介紹哈希技術(shù)的研究進(jìn)展，哈希技術(shù)在列存儲(chǔ)數(shù)據(jù)庫(kù)分組和連接查詢(xún)中的應(yīng)用，以及Cache利用率對(duì)數(shù)據(jù)庫(kù)查詢(xún)的重要性。

2.1哈希技術(shù)

哈希技術(shù)由于其高效性、不可逆性以及唯一性，在信息系統(tǒng)的數(shù)據(jù)存儲(chǔ)與訪(fǎng)問(wèn)中占有重要的地位[3-4]。哈希技術(shù)將關(guān)鍵字直接映射為存儲(chǔ)地址，達(dá)到快速尋址的目的，即Addr=H(key)，其中H為哈希函數(shù)。

文獻(xiàn)[5]考慮到在大數(shù)據(jù)環(huán)境下節(jié)省內(nèi)存，使用數(shù)組代替鏈表來(lái)提高定位速度，以減少遍歷鏈表的時(shí)間開(kāi)銷(xiāo)。由于大多數(shù)情況下，數(shù)據(jù)變化未知，使用固定大小的數(shù)組要考慮最壞情況的沖突，會(huì)浪費(fèi)許多不必要的空間，而使用動(dòng)態(tài)數(shù)組要花費(fèi)很多時(shí)間在內(nèi)存分配上。本文提出的方法能夠減少空間的浪費(fèi)，同時(shí)保證定位速度。

2.2哈希技術(shù)在列存儲(chǔ)數(shù)據(jù)庫(kù)查詢(xún)中的應(yīng)用

列存儲(chǔ)數(shù)據(jù)庫(kù)在聯(lián)機(jī)分析處理（online analytical processing，OLAP）、商務(wù)智能、數(shù)據(jù)倉(cāng)庫(kù)等決策分析領(lǐng)域逐漸被應(yīng)用，其將關(guān)系表中的數(shù)據(jù)按字段分開(kāi)存儲(chǔ)，執(zhí)行查詢(xún)時(shí)，僅從磁盤(pán)讀取與當(dāng)前查詢(xún)相關(guān)的列，有效節(jié)省了I/O帶寬，避免不相干數(shù)據(jù)的讀入，從而能夠極大程度地提高分析查詢(xún)的效率。

在列存儲(chǔ)數(shù)據(jù)庫(kù)的查詢(xún)操作中，分組（group by）和連接（join）是最主要的，同時(shí)也是最費(fèi)時(shí)的操作。

2.2.1分組和連接

計(jì)算分組函數(shù)中時(shí)間開(kāi)銷(xiāo)最大的部分是執(zhí)行g(shù)roup by子句，它結(jié)合合計(jì)函數(shù)（max，min，avg，sum），根據(jù)一個(gè)或多個(gè)列對(duì)結(jié)果集進(jìn)行分組。

分組主要有基于排序、基于哈希技術(shù)和基于嵌套循環(huán)3種方式，Albutiu[6]從響應(yīng)時(shí)間、健壯性、資源利用率等方面比較了3者的區(qū)別，得出在數(shù)據(jù)量很大并且無(wú)序的情況下，基于哈希的方法比其他兩種分組方式效率高。

在Oracle 10gR2中，分組由以前版本的sort group by改成了Hash group by，這種算法上的改進(jìn)，取消了sort group by必須進(jìn)行的排序操作。訪(fǎng)問(wèn)時(shí)間復(fù)雜度從O(lbn)降低到了O(1)。

連接基于兩個(gè)或多個(gè)表中列之間的關(guān)系執(zhí)行查詢(xún)操作。比較經(jīng)典的連接算法有嵌套循環(huán)連接、歸并排序連接和哈希連接。

哈希連接常用于大數(shù)據(jù)集連接[7]。使用兩個(gè)表中較小的表，利用連接鍵在內(nèi)存中建立哈希表，然后掃描較大的表并探測(cè)哈希表，找出與哈希表匹配的行。

通常情況下，哈希連接的效果要比嵌套循環(huán)連接和排序合并連接好[8-9]。由于列存儲(chǔ)數(shù)據(jù)庫(kù)的數(shù)據(jù)存儲(chǔ)特性，一般采用哈希連接算法。

2.2.2Cache利用率

Cache的高效訪(fǎng)問(wèn)也是數(shù)據(jù)庫(kù)查詢(xún)的一個(gè)重要方面[10]。文獻(xiàn)[11]對(duì)4種商業(yè)數(shù)據(jù)庫(kù)的分組和連接進(jìn)行了測(cè)試，結(jié)果顯示，CPU等待時(shí)間占整個(gè)處理時(shí)間的50%以上。分析原因，90%是由于L1指令Cache失效和L2數(shù)據(jù)Cache失效造成的。也就是說(shuō)，數(shù)據(jù)庫(kù)系統(tǒng)的執(zhí)行時(shí)間有很大一部分都花費(fèi)在Cache和主存之間的數(shù)據(jù)交換上[12]。

目前在加快數(shù)據(jù)處理操作方面，主要集中于對(duì)Cache感知[13]和Cache不敏感策略[14]的研究。本文借鑒COHJ（cache-oblivious Hash joins）[15]和CONLJ（cacheoblivious nested-loop joins）[16-17]的Cache不敏感策略，對(duì)數(shù)據(jù)庫(kù)join查詢(xún)進(jìn)行優(yōu)化，提出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)Block_List，將沖突數(shù)據(jù)存入Block中，保證Block中數(shù)據(jù)連續(xù)存放，并且設(shè)置合適的Block大小，使整個(gè)Block的內(nèi)容能一次性存放在Cache中，提高命中率，減少CPU的等待時(shí)間。

3　HashMap優(yōu)化

本文提出的HashMap優(yōu)化策略包括：分桶時(shí)的哈希函數(shù)優(yōu)化；用鏈塊地址法解決沖突；增加存儲(chǔ)hashcode，提高key的匹配效率。

3.1哈希函數(shù)分桶

哈希分桶的第一步是選取一個(gè)均勻的哈希函數(shù)，使數(shù)據(jù)進(jìn)入每個(gè)桶的概率相等，這對(duì)于數(shù)據(jù)存儲(chǔ)的平衡性及后期匹配效率都非常重要。

本文對(duì)哈希函數(shù)的改進(jìn)參考Java HashMap的哈希函數(shù)，將HashMap的容量設(shè)置為2的整數(shù)次冪，把“mod”操作改為“位與”操作。

本文優(yōu)化的哈希函數(shù)代碼如圖1所示。

該函數(shù)對(duì)key值進(jìn)行操作，bucket_num代表桶的數(shù)目，是2的整數(shù)次冪，具體大小由系統(tǒng)最大可分配桶數(shù)目決定。將hashcodemodbucket_num操作改為hashcode&(bucket_num-1)，不但對(duì)分桶的概率沒(méi)有影響，還提高了運(yùn)算速度。通過(guò)位與操作，得到key值所對(duì)應(yīng)的hashcode，接下來(lái)將(key,value)指針存到相對(duì)應(yīng)的桶中。

Fig.1　Code of Hash function圖1　哈希函數(shù)代碼

3.2塊鏈地址法解決沖突

傳統(tǒng)鏈地址法解決沖突是將沖突的數(shù)據(jù)以指針鏈表的方式存儲(chǔ)在相應(yīng)的桶后。因此鏈表的存儲(chǔ)是不連續(xù)的，內(nèi)存的申請(qǐng)和釋放也是分段進(jìn)行的，從而遍歷鏈表時(shí)，需要頻繁地訪(fǎng)問(wèn)內(nèi)存，會(huì)造成很大的時(shí)間開(kāi)銷(xiāo)。

衡量哈希表的存儲(chǔ)效率的一個(gè)因素是裝載因子(load_factor，記作α)[18]，它表示一個(gè)鏈的平均存儲(chǔ)元素?cái)?shù)，即對(duì)于一個(gè)能存放n個(gè)元素的、具有m個(gè)桶的哈希表，α為n/m。

在簡(jiǎn)單均勻哈希的假設(shè)下，對(duì)于鏈地址法解決沖突的哈希表，一次成功和不成功的查找所需要的時(shí)間都是Θ(1+α)[18]。

Fig.2　Block_List replacing List圖2　Block_List代替List

降低α可以加快檢索速度，根據(jù)定義可以增加桶的數(shù)量來(lái)降低平均裝載因子。但是動(dòng)態(tài)增加桶的數(shù)量又會(huì)造成重新哈希，從而增加時(shí)間開(kāi)銷(xiāo)。而在桶數(shù)量不變的情況下，隨著n的增加，平均裝載因子必定增加，造成key值沖突的概率增大。有效的辦法就是優(yōu)化沖突化解機(jī)制，提高沖突解決的效率。

考慮遍歷鏈表（List）的時(shí)間開(kāi)銷(xiāo)和Cache的敏感性，本文提出了鏈塊地址法，定義一個(gè)新的結(jié)構(gòu)Block_List來(lái)代替List，該結(jié)構(gòu)轉(zhuǎn)變?nèi)鐖D2所示。

Block之間通過(guò)鏈表鏈接，Block中的數(shù)據(jù)連續(xù)存儲(chǔ)。每個(gè)Block的內(nèi)容如圖3所示。

Fig.3　Contents of block圖3 Block存儲(chǔ)內(nèi)容

該結(jié)構(gòu)中，每個(gè)Block存放一個(gè)結(jié)構(gòu)體數(shù)組，在結(jié)構(gòu)體中存放指向(key,value)的指針，Block之間使用鏈表方式鏈接。算法1是使用Block_List沖突化解的方法。

算法1沖突化解

輸入：原始數(shù)據(jù)(key,value)集合Sk和由哈希函數(shù)計(jì)算得來(lái)的hashcode集合Sh。

對(duì)(key,value)集合以及由3.1節(jié)哈希函數(shù)計(jì)算得出的hashcode集合進(jìn)行分桶，先求出桶編號(hào)m，如果系統(tǒng)分配的桶沒(méi)有用完，且m不存在，則建立一個(gè)新桶；如果m已經(jīng)存在，則表示有沖突，將(key,value)和hashcode存到相應(yīng)的Block中，當(dāng)Block存滿(mǎn)之后，重新開(kāi)辟Block空間。當(dāng)所有數(shù)據(jù)都插入成功后，將所有Block->next置為null，表示結(jié)束。

本文將Block大小設(shè)置為一個(gè)接近α的整數(shù)，因?yàn)棣潦茄b載因子，表示一個(gè)鏈的平均存儲(chǔ)元素?cái)?shù)，讀取Block的數(shù)據(jù)時(shí)，可以將一個(gè)鏈的沖突數(shù)據(jù)一次讀入緩存，與文獻(xiàn)[5]提出的方法相比，浪費(fèi)的空間比較小，提高了堆區(qū)的使用效率。由于不用頻繁地掃描鏈表，此方法相對(duì)傳統(tǒng)的鏈地址法，在查詢(xún)效率上有明顯的優(yōu)勢(shì)，沖突數(shù)據(jù)連續(xù)存放，能高效地利用緩存。

3.3預(yù)緩存hashcode提高匹配效率

列存儲(chǔ)數(shù)據(jù)庫(kù)的key值通常是不定長(zhǎng)的字符串，當(dāng)新的(key,value)值插入進(jìn)來(lái)時(shí)，需要用新key值與Block中每一個(gè)key進(jìn)行比較。

而字符串的存儲(chǔ)機(jī)制是由一個(gè)字符指針指向存放字符串的地址，直接比較key值會(huì)造成頻繁的讀取內(nèi)存。本文將每個(gè)key的hashcode也預(yù)讀到Block中，在匹配時(shí)，先直接用hashcode比對(duì)，當(dāng)Block中具有相同的hashcode時(shí)，才去key值所對(duì)應(yīng)的內(nèi)存中對(duì)比key字符串以及value值。

算法2是預(yù)緩存hashcode值匹配算法的具體實(shí)現(xiàn)。

算法2預(yù)緩存hashcode值匹配算法

對(duì)于輸入的hashcode值以及(key,value)，要查看當(dāng)前HashMap中是否存在該值。首先根據(jù)hashcode求得Bucket_num，如果Bucket_num不存在，則返回false，如果存在，則比較hashcode和該Bucket的第一個(gè)Block中存儲(chǔ)的hashcode，如果不同，返回false，如果相同，對(duì)比兩個(gè)key值。如果遍歷完整個(gè)Block_ List都沒(méi)有匹配到，則返回false。

采用hashcode比對(duì)代替key值的比較，會(huì)增加少量的存儲(chǔ)空間，但由于將字符串的比較改為數(shù)值的比較，對(duì)內(nèi)存的訪(fǎng)問(wèn)次數(shù)相應(yīng)減少了，比較速度也提高了。同時(shí)，每次從內(nèi)存中讀取一個(gè)Block大小的數(shù)據(jù)進(jìn)行Cache，根據(jù)CPU訪(fǎng)問(wèn)數(shù)據(jù)的局部性，使緩存得到高效利用，總體上匹配效率還是提高了。

3.4BHMap

結(jié)合以上優(yōu)化策略，本文提出存儲(chǔ)結(jié)構(gòu)BHMap,該存儲(chǔ)結(jié)構(gòu)如3.2節(jié)中圖2和圖3所示。

首先，在選取哈希函數(shù)分桶的過(guò)程中，設(shè)置桶的大小為2的整數(shù)次冪，保證哈希分桶的均勻性；其次，使用位與操作能夠快速定位桶編號(hào)，當(dāng)新(key,value)插進(jìn)來(lái)，如果發(fā)生沖突，將沖突數(shù)據(jù)存放在該桶之后的Block_List中，直到Block存滿(mǎn)后，重新申請(qǐng)內(nèi)存開(kāi)辟下一塊Block。設(shè)計(jì)Block大小的時(shí)候，考慮Cache敏感性，將Block大小設(shè)計(jì)為接近α的整數(shù)，每次從內(nèi)存中讀取一個(gè)Block的數(shù)據(jù)進(jìn)Cache，使沖突數(shù)據(jù)能夠連續(xù)存放，保證計(jì)算機(jī)的空間和時(shí)間局部性。

同時(shí)，在數(shù)據(jù)插入過(guò)程中，BHMap增加存儲(chǔ)hashcode值，在Block_List中存儲(chǔ)包含指向內(nèi)存(key, value)的指針entry，以及該key值計(jì)算得到的hashcode，在匹配查找的過(guò)程中，先匹配數(shù)值型hashcode，如果相等再匹配key值，可用減少指針尋址時(shí)間以及長(zhǎng)字符串的匹配時(shí)間。

4　實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

根據(jù)提出的優(yōu)化方法，實(shí)驗(yàn)設(shè)計(jì)部分將比較使用BHMap優(yōu)化前后的查詢(xún)性能。測(cè)試準(zhǔn)則包括運(yùn)行時(shí)間和運(yùn)行時(shí)占用的內(nèi)存大小。選取的基準(zhǔn)測(cè)試案例如圖4所示，test_map代表數(shù)據(jù)結(jié)構(gòu)，運(yùn)行時(shí)用BHMap、Map以及unordered_map等替代。

Fig.4　Benchmark test case圖4 基準(zhǔn)測(cè)試案例

該案例實(shí)現(xiàn)一個(gè)單一的計(jì)數(shù)功能。采用該基準(zhǔn)測(cè)試，可以避免其他因素對(duì)實(shí)驗(yàn)結(jié)果的影響。

本文將桶數(shù)目和key值的不重復(fù)數(shù)據(jù)量（Key-NoRepeatNum，β）作為可變參數(shù)來(lái)衡量結(jié)構(gòu)體的性能及適用場(chǎng)景。當(dāng)數(shù)據(jù)量確定時(shí)，桶數(shù)目會(huì)直接影響α。參數(shù)β能夠說(shuō)明源數(shù)據(jù)的不確定性，β越高，說(shuō)明源數(shù)據(jù)重復(fù)率越低，對(duì)其進(jìn)行碰撞的估計(jì)就越難，因此本文將β作為一個(gè)主要參數(shù)，進(jìn)行以下3組實(shí)驗(yàn)。

實(shí)驗(yàn)1比較3種數(shù)據(jù)結(jié)構(gòu)在不同α、β下的性能：①M(fèi)ap，該結(jié)構(gòu)體是C++標(biāo)準(zhǔn)的Map結(jié)構(gòu)，實(shí)現(xiàn)原理是平衡二叉樹(shù)；②unordered_map,該結(jié)構(gòu)在C++ Boost庫(kù)中實(shí)現(xiàn)，用鏈表法解決沖突；③本文提出的BHMap。

實(shí)驗(yàn)2優(yōu)化效果測(cè)試。對(duì)于BHMap，比較3種情況：①只優(yōu)化哈希函數(shù)（HashFunc）；②優(yōu)化哈希函數(shù)以及使用塊鏈結(jié)構(gòu)（Block_List，BList）；③優(yōu)化哈希函數(shù)，使用Block_List并且緩存了hashcode的BHMap。

實(shí)驗(yàn)3適用場(chǎng)景驗(yàn)證。在不同的桶數(shù)目下，比較unordered_map、HashFunc、BList、BHMap在不同的α、β下的性能。

對(duì)于實(shí)驗(yàn)1、實(shí)驗(yàn)2、實(shí)驗(yàn)3，統(tǒng)計(jì)比較各種情況下的運(yùn)行時(shí)間和占用內(nèi)存情況。

實(shí)驗(yàn)使用CentOS release 6.5操作系統(tǒng)，Cache size為15 360 KB，每個(gè)數(shù)據(jù)文件包含10 000 000條記錄，存儲(chǔ)形式為字符串。每個(gè)文件的β近似呈指數(shù)增長(zhǎng)，分別為99,999,9999，99997,999960,9950474。

4.1比較3種數(shù)據(jù)結(jié)構(gòu)性能

對(duì)于3種數(shù)據(jù)結(jié)構(gòu)Map、unordered_map和BHMap，首先比較在不同的桶數(shù)目下的性能。在桶數(shù)目為1 048 576和16 777 216時(shí)（即α為9.537和0.596，Block大小為10），測(cè)得其時(shí)間性能分別如圖5、圖6所示。

從圖5中可以看出，在桶數(shù)目一定時(shí)，隨著β的增加，查詢(xún)消耗的時(shí)間也逐漸增加。在β為9 950 474，即接近于文件總記錄數(shù)時(shí)，BHMap有明顯的性能優(yōu)勢(shì)，其查詢(xún)速度比unordered_map快3.5倍以上，比Map快10倍以上。從實(shí)驗(yàn)數(shù)據(jù)可以看出，BHMap適用于β比較大，即key值的重復(fù)率比較低的情況。

圖6是桶數(shù)目比較多的情況，此時(shí)BHMap和unordered_map的性能差別不大。說(shuō)明桶數(shù)目的大小對(duì)基于HashMap的結(jié)構(gòu)性能影響比較大，桶越多，查詢(xún)速度越快。

Fig.5　Time consumption of 3 data structures圖5　3種數(shù)據(jù)結(jié)構(gòu)時(shí)間消耗比較

Fig.6　Time consumption of 3 data structures圖6　3種數(shù)據(jù)結(jié)構(gòu)時(shí)間消耗比較

對(duì)比圖5、圖6中可以看出，桶數(shù)目直接影響unordered_map的性能。在桶數(shù)目比較大，即α比較小時(shí)，unordered_map也能發(fā)揮很好的性能，其運(yùn)行時(shí)間與BHMap接近，同時(shí)證明了減小α是提高Hash-Map性能的一個(gè)有效方法。實(shí)驗(yàn)也可以證明，執(zhí)行與順序無(wú)關(guān)的操作時(shí)，HashMap的性能比Map好。

圖7、圖8對(duì)比了3個(gè)數(shù)據(jù)結(jié)構(gòu)在不同桶數(shù)目下運(yùn)行的內(nèi)存使用情況。

從圖7、圖8中可以看出，在α比較高，β比較低的情況下，Map運(yùn)行時(shí)占用的內(nèi)存比unordered_map和BHMap少，在桶數(shù)目為1 048 576時(shí)，unordered_map 和BHMap對(duì)內(nèi)存使用的變化趨勢(shì)相同。但是，在桶數(shù)目增加到16 777 216時(shí)，BHMap對(duì)內(nèi)存的使用量明顯增加，比unordered_map高出近一個(gè)數(shù)量級(jí)。

Fig.7　Memory consumption of 3 data structures圖7　3種數(shù)據(jù)結(jié)構(gòu)內(nèi)存消耗比較

Fig.8　Memory consumption of 3 data structures圖8　3種數(shù)據(jù)結(jié)構(gòu)內(nèi)存消耗比較

內(nèi)存方面，BHMap在可用桶數(shù)目比較多的情況下，會(huì)比unordered_map多消耗內(nèi)存。這一點(diǎn)也說(shuō)明了Block_HashMap更適用于桶數(shù)目比較少的情況。

4.2優(yōu)化效果測(cè)試

對(duì)本文提出的3個(gè)優(yōu)化方法HashFunc、BList、BHMap分別測(cè)試其運(yùn)行時(shí)間和內(nèi)存使用量。根據(jù)4.1節(jié)的結(jié)論，本實(shí)驗(yàn)的桶數(shù)目設(shè)置為1 048 576，即桶的數(shù)目比較少的情況。查詢(xún)時(shí)間和內(nèi)存使用情況如圖9、圖10所示。

Fig.9　Time consumption comparison of optimization effect 圖9 優(yōu)化時(shí)間性能比較

Fig.10　Memory consumption comparison of optimization effect 圖10　優(yōu)化內(nèi)存使用比較

圖9說(shuō)明，HashFunc優(yōu)化哈希函數(shù)，使用“位與”操作代替“取模”操作，在β比較低的情況下，能節(jié)省程序運(yùn)行的時(shí)間。但是HashFunc仍然使用鏈表解決沖突，在 β比較高的情況下，其運(yùn)行時(shí)間超過(guò)了unordered_map，因?yàn)樵摪姹镜膬?yōu)化在桶數(shù)目不夠時(shí)，需要?jiǎng)討B(tài)開(kāi)辟新的桶空間，這個(gè)過(guò)程消耗的時(shí)間比較多。BList優(yōu)化版本實(shí)現(xiàn)了Block_List，用塊鏈?zhǔn)浇Y(jié)構(gòu)來(lái)解決沖突，從圖中可以看出，其性能明顯提高。在BHMap版本中，預(yù)緩存了hashcode，使訪(fǎng)問(wèn)速度明顯較BList版本又有所提高。

從圖10中可以看出，使用Block_List結(jié)構(gòu)在 β比較低的情況下，會(huì)比unordered_map多消耗內(nèi)存，但是，在 β接近記錄的總數(shù)時(shí)，unordered_map對(duì)內(nèi)存的使用量也急劇上升，兩者差別減小，這也說(shuō)明了BHMap適用于key值重復(fù)率比較低的情況。

雖然BHMap較BList版本多存儲(chǔ)了hashcode值，會(huì)多占用少量?jī)?nèi)存，但是由于hashcode值是整型數(shù)據(jù)，不會(huì)占用太多內(nèi)存。從內(nèi)存成本和時(shí)間效益來(lái)看實(shí)驗(yàn)結(jié)果也是可以接受的。

4.3適用場(chǎng)景驗(yàn)證

基于4.2節(jié)的實(shí)驗(yàn)，本節(jié)討論BHMap的適用場(chǎng)景。在不同的桶數(shù)目下，隨著β的增大，unordered_ map、HashFunc、BList、BHMap的運(yùn)行時(shí)間和內(nèi)存使用情況如圖11、圖12所示。

從圖11中可以看出，對(duì)于unordered_map和BHMap，一般都是桶數(shù)目越多，碰撞越小，運(yùn)行時(shí)間越少，效果越好。但是現(xiàn)實(shí)數(shù)據(jù)并不總是這樣，在桶數(shù)目有限、數(shù)據(jù)量很大的情況下，要減少α來(lái)加速HashMap就很困難。前3個(gè)子圖充分說(shuō)明了這種情況，尤其是前兩個(gè)子圖，在β接近記錄總數(shù)時(shí)，桶數(shù)目不同而引起的時(shí)間消耗差距已達(dá)到5倍左右。

本文介紹的優(yōu)化方法，充分考慮到這種情況，在使用Block_List之后，運(yùn)行時(shí)間對(duì)桶數(shù)目的敏感性降低。BHMap在數(shù)據(jù)的重復(fù)率比較低的情況下，優(yōu)化后的數(shù)據(jù)結(jié)構(gòu)在桶數(shù)目為1 048 576時(shí)，已經(jīng)超過(guò)了桶數(shù)目為10 777 216時(shí)的性能。

圖12說(shuō)明，桶的數(shù)目越多，運(yùn)行時(shí)占用的內(nèi)存越多。相比之下，使用了Block_List的BHMap要比使用鏈表解決沖突unordered_map多占用內(nèi)存。在桶數(shù)目為16 777 216的情況下，當(dāng)數(shù)據(jù)的重復(fù)率比較低，β接近記錄總數(shù)時(shí)，內(nèi)存使用量突然大幅度增加。從后兩個(gè)子圖可以看出，對(duì)于桶數(shù)目比較少的情況，優(yōu)化的BHMap能夠控制內(nèi)存的急劇增加。

從以上3個(gè)實(shí)驗(yàn)，總結(jié)出了BHMap的適用場(chǎng)景，是對(duì)一般優(yōu)化方法通過(guò)降低α來(lái)加快HashMap訪(fǎng)問(wèn)速度的補(bǔ)充。為了節(jié)約時(shí)間和空間，桶的數(shù)目一般固定，并且不會(huì)設(shè)置得太大。在動(dòng)態(tài)增加桶的數(shù)量時(shí)，會(huì)造成重新哈希，從而增加時(shí)間開(kāi)銷(xiāo)。而在桶數(shù)量不變的情況下，隨著n的增加，平均裝載因子就會(huì)上升，從而造成key值沖突的概率增大。本文優(yōu)化也能表現(xiàn)出很好的效率。

Fig.11　Time consumption comparison of optimization effect on different bucket_num圖11　不同桶數(shù)目下優(yōu)化版本的時(shí)間消耗比較

Fig.12　Memory consumption comparison of optimization effect on different bucket_num圖12　不同桶數(shù)目下優(yōu)化版本的內(nèi)存消耗比較

在處理的數(shù)據(jù)重復(fù)率比較高的情況下，unordered_ map和BHMap的性能都比較好，但是對(duì)于數(shù)據(jù)重復(fù)率比較低的情況，BHMap的優(yōu)勢(shì)非常明顯。

5　BHMap在列存儲(chǔ)數(shù)據(jù)庫(kù)中的應(yīng)用

優(yōu)化后的BHMap調(diào)用接口類(lèi)似于unordered_ map，可以在任何適用的場(chǎng)合方便地調(diào)用。本文以列存儲(chǔ)數(shù)據(jù)庫(kù)查詢(xún)語(yǔ)句中兩個(gè)重要的查詢(xún)——分組和連接，來(lái)舉例說(shuō)明BHMap的使用。

5.1分組查詢(xún)實(shí)現(xiàn)

分組部分，主要實(shí)現(xiàn)group by語(yǔ)句，該語(yǔ)句結(jié)合合計(jì)函數(shù)，根據(jù)一個(gè)或者多個(gè)列進(jìn)行分組。結(jié)合BHMap，本文定義適合的哈希分桶函數(shù)以及匹配函數(shù)，將要分組的列放在一個(gè)結(jié)構(gòu)體key_set中，作為Hash-Map的key值，對(duì)其進(jìn)行分桶和匹配。

算法3 group by

SELECT關(guān)鍵字之后存儲(chǔ)列的結(jié)構(gòu)體，從源文件的第index行，讀出value值放在臨時(shí)結(jié)果變量tmpresult中。再根據(jù)tmpresult.key_set作為鍵值分桶，如果桶已經(jīng)存在，則計(jì)算合計(jì)函數(shù)。

5.2連接查詢(xún)實(shí)現(xiàn)

連接部分，用于根據(jù)兩個(gè)或者多個(gè)表中列之間的關(guān)系，從這些表中查詢(xún)數(shù)據(jù)。

hash join將兩個(gè)表中較小的一個(gè)在內(nèi)存中構(gòu)造一個(gè)哈希表，掃描另一個(gè)表，與內(nèi)存中的小表進(jìn)行比較，找出與之匹配的行。

讀入存放小表的文件build_files，將其存入數(shù)組B_Array中，與group by算法類(lèi)似，將其以主鍵分桶；之后，對(duì)大表數(shù)據(jù)對(duì)應(yīng)的P_Array中的每一個(gè)數(shù)據(jù)，從BHMap匹配小表中的數(shù)據(jù)，如果找到，記錄其在B_Array和P_Array的下標(biāo)，找出結(jié)果。

6　結(jié)束語(yǔ)

本文提出的BHMap結(jié)構(gòu)適用于兩種情況：桶數(shù)目一定，而key值重復(fù)率比較低；或者數(shù)據(jù)一定，但是可用的桶數(shù)目比較少。

BHMap的優(yōu)化包括哈希分桶、沖突解決以及key值匹配的整個(gè)過(guò)程。在哈希分桶過(guò)程中，選取合適的哈希函數(shù)，用“位與”操作代替?zhèn)鹘y(tǒng)的“取?！辈僮鱽?lái)得到桶編號(hào)，提高了運(yùn)算效率。在沖突解決階段，定義了存儲(chǔ)結(jié)構(gòu)Block_List來(lái)代替?zhèn)鹘y(tǒng)的鏈表，提高存儲(chǔ)效率以及插入效率。在key值匹配過(guò)程中，預(yù)緩存hashcode值，匹配過(guò)程中用整型數(shù)據(jù)代替字符串，節(jié)省了對(duì)指針內(nèi)存的遍歷時(shí)間。

本文考慮到存儲(chǔ)體系中Cache的命中率對(duì)CPU查詢(xún)效率的影響，考慮緩存敏感性，相對(duì)于傳統(tǒng)的鏈地址法，每個(gè)節(jié)點(diǎn)可以連續(xù)存儲(chǔ)多個(gè)值，存儲(chǔ)密度增加，CPU檢索數(shù)據(jù)不需要頻繁地進(jìn)行指針尋址，查詢(xún)速度明顯提高。同時(shí)設(shè)計(jì)Block大小時(shí)，使其接近裝載因子，使沖突數(shù)據(jù)能一次讀入緩存，也可以減少空間的浪費(fèi)。

在存儲(chǔ)方面，由于在每個(gè)節(jié)點(diǎn)中多存儲(chǔ)了hashcode值，相比較傳統(tǒng)的unordered_map，會(huì)增加一定的存儲(chǔ)空間。但是由于多存儲(chǔ)的hashcode值是整型數(shù)據(jù)，運(yùn)行時(shí)不會(huì)占用太多內(nèi)存，在桶數(shù)目比較少的情況下，該消耗是可以接受的。

對(duì)于數(shù)據(jù)庫(kù)中一些主要的查詢(xún)操作，如分組、連接等比較耗時(shí)的語(yǔ)句，本文提出的優(yōu)化方法可以作為unordered_map的補(bǔ)充，根據(jù)查詢(xún)數(shù)據(jù)的特點(diǎn)，選取結(jié)構(gòu)進(jìn)行查詢(xún)，可在某些應(yīng)用場(chǎng)景下提高查詢(xún)性能。

References:

[1]Boncz P A,Zukowski M,Nes N.MonetDB/X100:hyperpipelining query execution[C]//Proceedings of the 2nd Biennial Conference on Innovative Data Systems Research, Asilomar,CA,Jan 4-7,2005:225-237.

[2]Abadi D J.Query execution in column-oriented database systems[D].Massachusetts Institute of Technology,2008.

[3]Owolabi O.Empirical studies of some hashing functions[J]. Information&Software Technology,2003,45(2):109-112.

[4]Ma Rulin,Jang Hua,Zhang Qingxia.An improved fast searching method of Hash table[J].Computer Engineering&Science,2008,30(9):66-68.

[5]Li Xiaotang,Zhan Feng.An improved hash map realization method[J].Journal of Shenzhen Institute of Information Technology,2010,8(2):80-83.

[6]Albutiu M C.Scalable analytical query processing[D]. München:Technische Universit?t München,2013.

[7]Singhal R,Nambiar M.Extrapolation of SQL query elapsed response time at application development stage[C]//Proceedings of the 2012 Annual India Conference,Kochi,India, Dec 7-9,2012.Piscataway,USA:IEEE,2012:35-41.

[8]Balkesen C,Alonso G,Teubner J,et al.Multi-core,mainmemory joins:sort vs.hash revisited[J].Proceedings of the VLDB Endowment,2013,7(1):85-96.

[9]Graefe G.New algorithms for join and grouping operations[J]. Computer Science-Research and Development,2012,27(1): 3-27.

[10]Qin Xiongpai,Wang Huiju,Li Furong,et al.New landscape of data management technologies[J].Journal of Software,2013,24(2):175-197.

[11]Ailamaki A,Dewitt D J,Hill M D,et al.DBMSs on a modern processor:where does time go?[C]//Proceedings of the 25th International Conference on Very Large Data Bases, Edinburgh,UK,Sep 7-10,1999.San Francisco,USA:Morgan Kaufmann Publishers Inc,1999:266-277.

[12]Han Xixian,Yang Donghua,Li Jianzhong.DBCC-join:a novel cache-conscious disk-based join algorithm[J].Chinese Journal of Computers,2010,33(8):1500-1511.

[13]Shatdal A,Kant C,Naughton J F.Cache conscious algorithms for relational query processing[D].University of Wisconsin-Madison,Computer Sciences Department,1994.

[14]He Bingsheng.Cache-oblivious query processing[D].Hong Kong University of Science and Technology,2008.

[15]He Bingsheng,Luo Qiong.Cache-oblivious hash joins[R]. Hong Kong University of Science and Technology,2006.

[16]He Bingsheng,Luo Qiong.Cache-oblivious nested-loop joins[C]//Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management,Arlington,USA,Nov 5-11,2006.New York:ACM,2006:718-727.

[17]Manegold S,Boncz P A,Kersten M L.Optimizing mainmemory join on modern hardware[J].IEEE Transactions on Knowledge and Data Engineering,2002,14(4):709-730.

[18]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms[M].Cambridge,USA:MIT Press,2001.

附中文參考文獻(xiàn)：

[4]馬如林,蔣華,張慶霞.一種哈希表快速查找的改進(jìn)方法[J].計(jì)算機(jī)工程與科學(xué),2008,30(9):66-68.

[5]李曉堂,詹峰.一種改進(jìn)的hash map實(shí)現(xiàn)方式[J].深圳信息職業(yè)技術(shù)學(xué)院學(xué)報(bào),2010,8(2):80-83.

[10]覃雄派,王會(huì)舉,李芙蓉,等.數(shù)據(jù)管理技術(shù)的新格局[J].軟件學(xué)報(bào),2013,24(2):175-197.

[12]韓希先,楊東華,李建中.DBCC-join:一種新的高速緩存敏感的磁盤(pán)連接算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(8):1500-1511.

MU Hongfen was born in 1990.She is an M.S.candidate at Beijing University of Chemical Technology,and the student member of CCF.Her research interests include database and query algorithm optimization.

母紅芬（1990—），女，云南大理人，北京化工大學(xué)碩士研究生，CCF學(xué)生會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)，查詢(xún)算法優(yōu)化。

LI Zheng was born in 1974.He received the Ph.D.degree from King?s College London in 2009.Now he is a full professor at Department of Computer Science,Beijing University of Chemical Technology,and the senior member of CCF.His research interest is software analysis and testing.He has published more than 30 papers,and has taken charge of 3 projects funded by National Natural Science Foundation of China.

李征（1974—），男，河北清苑人，2009年于英國(guó)倫敦國(guó)王學(xué)院獲得博士學(xué)位，現(xiàn)為北京化工大學(xué)計(jì)算機(jī)系教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)檐浖治黾皽y(cè)試。發(fā)表學(xué)術(shù)論文30多篇，先后主持3項(xiàng)國(guó)家自然科學(xué)基金項(xiàng)目。

HUO Weiping was born in 1970.He is the vice president and chief engineer of Business-Intelligence of Oriental Nations Corporation.His research interests include data analysis,data warehouse and business intelligence of telecommunications and financial industry,etc.

霍衛(wèi)平（1970—），男，山西朔州人，北京東方國(guó)信科技股份有限公司副總經(jīng)理、總工程師，主要研究領(lǐng)域?yàn)殡娦?、金融行業(yè)的大數(shù)據(jù)分析、數(shù)據(jù)倉(cāng)庫(kù)、商業(yè)智能等。

JIN Zhenghao was born in 1971.He received the M.S.degree from University of Chinese Academy of Sciences.Now he is the vice president of R&D center in Business-Intelligence of Oriental Nations Corporation.His research interests include system analysis and development in big data of telecommunications industry.

金正皓（1971—），男，吉林長(zhǎng)春人，中國(guó)科學(xué)院數(shù)學(xué)和系統(tǒng)科學(xué)研究院碩士，現(xiàn)為北京東方國(guó)信科技研發(fā)中心副總經(jīng)理，主要研究領(lǐng)域?yàn)殡娦判袠I(yè)的大數(shù)據(jù)分析系統(tǒng)的規(guī)劃和開(kāi)發(fā)工作。

Hash Map Optimization and Its Application in Column-Oriented Database Query?

MU Hongfen1,LI Zheng1+,HUO Weiping2,JIN Zhenghao2
1.Department of Computer Science,Beijing University of Chemical Technology,Beijing 100029,China
2.Business-Intelligence of Oriental Nations Corporation,Beijing 100102,China
+Corresponding author:E-mail:lizheng@mail.buct.edu.cn

MU Hongfen,LI Zheng,HUO Weiping,et al.HashMap optimization and its application in column-oriented database query.Journal of Frontiers of Computer Science and Technology,2016,10(9)：1250-1261.

HashMap has been widely used to retrieve big data because of its constant level in average performance of dictionary operations.Block_HashMap(BHMap)is based on C++HashMap,in which three optimizations are introduced:Hash function selection,conflict resolution and keyword matching.Conflict resolution is the core of optimization,where Block_list,a storage structure based on the chain address method,is proposed to use cache efficiently and save matching time by store hashcode.In the situation of limited bucket number and low data repetition rate,experiments show that although it consumes a small amount of memory,BHMap has a 3.5 times of C++unordered_map and 10 times of Map in terms of query speed.In column-oriented database,group by and join are the most commonly used,in which bucket keywords,resolving conflict and matching keywords are all Hash based.Finally the application of BHMap in the query of column-oriented database is provided.

HashMap;group by;join;cache-conscious;cache-oblivious;column-oriented database;BHMap

2015-07,Accepted 2015-10.

*The National Natural Science Foundation of China under Grant Nos.61170082,61472025(國(guó)家自然科學(xué)基金);the New Century Excellent Talents Foundation from MOE of China under Grant No.NCET-12-0757(教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃);the Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education Ministry of China under Grant No.LXJJ201303(教育部留學(xué)回國(guó)人員科研啟動(dòng)基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-29,http://www.cnki.net/kcms/detail/11.5602.TP.20151029.1704.002.html

A

TP311.132.3