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

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

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

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

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

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

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

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

1　引言

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

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

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

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

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

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

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

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

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

2.1哈希技術(shù)

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

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

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

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

在列存儲數(shù)據(jù)庫的查詢操作中，分組（group by）和連接（join）是最主要的，同時也是最費時的操作。

2.2.1分組和連接

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

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

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

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

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

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

2.2.2Cache利用率

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

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

3　HashMap優(yōu)化

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

3.1哈希函數(shù)分桶

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

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

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

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

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

3.2塊鏈地址法解決沖突

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

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

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

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

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

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

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

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

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

算法1沖突化解

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

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

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

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

列存儲數(shù)據(jù)庫的key值通常是不定長的字符串，當(dāng)新的(key,value)值插入進來時，需要用新key值與Block中每一個key進行比較。

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

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

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

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

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

3.4BHMap

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

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

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

4　實驗設(shè)計與結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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ù)目比較多的情況下，會比unordered_map多消耗內(nèi)存。這一點也說明了Block_HashMap更適用于桶數(shù)目比較少的情況。

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

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

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

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

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

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

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

4.3適用場景驗證

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

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

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

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

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

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

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

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

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

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

5.1分組查詢實現(xiàn)

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

算法3 group by

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

5.2連接查詢實現(xiàn)

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

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

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

6　結(jié)束語

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

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

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

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

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

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.

附中文參考文獻：

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

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

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

[12]韓希先,楊東華,李建中.DBCC-join:一種新的高速緩存敏感的磁盤連接算法[J].計算機學(xué)報,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é)生會員，主要研究領(lǐng)域為數(shù)據(jù)庫，查詢算法優(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年于英國倫敦國王學(xué)院獲得博士學(xué)位，現(xiàn)為北京化工大學(xué)計算機系教授，CCF高級會員，主要研究領(lǐng)域為軟件分析及測試。發(fā)表學(xué)術(shù)論文30多篇，先后主持3項國家自然科學(xué)基金項目。

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—），男，山西朔州人，北京東方國信科技股份有限公司副總經(jīng)理、總工程師，主要研究領(lǐng)域為電信、金融行業(yè)的大數(shù)據(jù)分析、數(shù)據(jù)倉庫、商業(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—），男，吉林長春人，中國科學(xué)院數(shù)學(xué)和系統(tǒng)科學(xué)研究院碩士，現(xiàn)為北京東方國信科技研發(fā)中心副總經(jīng)理，主要研究領(lǐng)域為電信行業(yè)的大數(shù)據(jù)分析系統(tǒng)的規(guī)劃和開發(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(國家自然科學(xué)基金);the New Century Excellent Talents Foundation from MOE of China under Grant No.NCET-12-0757(教育部新世紀(jì)優(yōu)秀人才支持計劃);the Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education Ministry of China under Grant No.LXJJ201303(教育部留學(xué)回國人員科研啟動基金).

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