HashMap優化及其在列存儲數據庫查詢中的應用*

母紅芬，李　征+，霍衛平，金正皓

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

HashMap優化及其在列存儲數據庫查詢中的應用*

母紅芬1，李征1+，霍衛平2，金正皓2

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

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

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

1　引言

隨著云計算與大數據的廣泛應用，大數據集的實時動態分析成為研究熱點。高效的數據查詢、分析操作是實現該目標的重要技術手段。

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

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

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

國內外對HashMap的研究主要集中在使用該結構體實現數據的高效查詢和插入，大部分直接使用封裝好的接口，很少對該結構進行優化。

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

本文通過一個基準的計數應用在千萬級數據集上驗證BHMap的性能，并與C++標準庫的Map和unordered_map進行比較，結果顯示，當桶數有限，數值重復率較低時，BHMap只在增加少部分內存消耗的情況下，查詢速度就能比unordered_map快3.5倍以上，比Map快10倍以上。本文給出了BHMap的優化方法以及調用API，通過在列存儲數據庫的分組和連接查詢中使用該數據結構，說明其在大數據查詢中的適用性。

2　背景及相關工作

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

2.1哈希技術

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

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

2.2哈希技術在列存儲數據庫查詢中的應用

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

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

2.2.1分組和連接

計算分組函數中時間開銷最大的部分是執行group by子句，它結合合計函數（max，min，avg，sum），根據一個或多個列對結果集進行分組。

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

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

連接基于兩個或多個表中列之間的關系執行查詢操作。比較經典的連接算法有嵌套循環連接、歸并排序連接和哈希連接。

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

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

2.2.2Cache利用率

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

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

3　HashMap優化

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

3.1哈希函數分桶

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

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

本文優化的哈希函數代碼如圖1所示。

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

Fig.1　Code of Hash function圖1　哈希函數代碼

3.2塊鏈地址法解決沖突

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

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

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

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

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

考慮遍歷鏈表（List）的時間開銷和Cache的敏感性，本文提出了鏈塊地址法，定義一個新的結構Block_List來代替List，該結構轉變如圖2所示。

Block之間通過鏈表鏈接，Block中的數據連續存儲。每個Block的內容如圖3所示。

Fig.3　Contents of block圖3 Block存儲內容

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

算法1沖突化解

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

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

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

3.3預緩存hashcode提高匹配效率

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

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

算法2是預緩存hashcode值匹配算法的具體實現。

算法2預緩存hashcode值匹配算法

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

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

3.4BHMap

結合以上優化策略，本文提出存儲結構BHMap,該存儲結構如3.2節中圖2和圖3所示。

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

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

4　實驗設計與結果分析

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

Fig.4　Benchmark test case圖4 基準測試案例

該案例實現一個單一的計數功能。采用該基準測試，可以避免其他因素對實驗結果的影響。

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

實驗1比較3種數據結構在不同α、β下的性能：①Map，該結構體是C++標準的Map結構，實現原理是平衡二叉樹；②unordered_map,該結構在C++ Boost庫中實現，用鏈表法解決沖突；③本文提出的BHMap。

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

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

對于實驗1、實驗2、實驗3，統計比較各種情況下的運行時間和占用內存情況。

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

4.1比較3種數據結構性能

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

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

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

Fig.5　Time consumption of 3 data structures圖5　3種數據結構時間消耗比較

Fig.6　Time consumption of 3 data structures圖6　3種數據結構時間消耗比較

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

圖7、圖8對比了3個數據結構在不同桶數目下運行的內存使用情況。

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

Fig.7　Memory consumption of 3 data structures圖7　3種數據結構內存消耗比較

Fig.8　Memory consumption of 3 data structures圖8　3種數據結構內存消耗比較

內存方面，BHMap在可用桶數目比較多的情況下，會比unordered_map多消耗內存。這一點也說明了Block_HashMap更適用于桶數目比較少的情況。

4.2優化效果測試

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

Fig.9　Time consumption comparison of optimization effect 圖9 優化時間性能比較

Fig.10　Memory consumption comparison of optimization effect 圖10　優化內存使用比較

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

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

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

4.3適用場景驗證

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

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

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

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

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

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

Fig.12　Memory consumption comparison of optimization effect on different bucket_num圖12　不同桶數目下優化版本的內存消耗比較

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

5　BHMap在列存儲數據庫中的應用

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

5.1分組查詢實現

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

算法3 group by

SELECT關鍵字之后存儲列的結構體，從源文件的第index行，讀出value值放在臨時結果變量tmpresult中。再根據tmpresult.key_set作為鍵值分桶，如果桶已經存在，則計算合計函數。

5.2連接查詢實現

連接部分，用于根據兩個或者多個表中列之間的關系，從這些表中查詢數據。

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

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

6　結束語

本文提出的BHMap結構適用于兩種情況：桶數目一定，而key值重復率比較低；或者數據一定，但是可用的桶數目比較少。

BHMap的優化包括哈希分桶、沖突解決以及key值匹配的整個過程。在哈希分桶過程中，選取合適的哈希函數，用“位與”操作代替傳統的“取模”操作來得到桶編號，提高了運算效率。在沖突解決階段，定義了存儲結構Block_List來代替傳統的鏈表，提高存儲效率以及插入效率。在key值匹配過程中，預緩存hashcode值，匹配過程中用整型數據代替字符串，節省了對指針內存的遍歷時間。

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

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

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

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].計算機工程與科學,2008,30(9):66-68.

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

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

[12]韓希先,楊東華,李建中.DBCC-join:一種新的高速緩存敏感的磁盤連接算法[J].計算機學報,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—），女，云南大理人，北京化工大學碩士研究生，CCF學生會員，主要研究領域為數據庫，查詢算法優化。

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年于英國倫敦國王學院獲得博士學位，現為北京化工大學計算機系教授，CCF高級會員，主要研究領域為軟件分析及測試。發表學術論文30多篇，先后主持3項國家自然科學基金項目。

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.

霍衛平（1970—），男，山西朔州人，北京東方國信科技股份有限公司副總經理、總工程師，主要研究領域為電信、金融行業的大數據分析、數據倉庫、商業智能等。

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—），男，吉林長春人，中國科學院數學和系統科學研究院碩士，現為北京東方國信科技研發中心副總經理，主要研究領域為電信行業的大數據分析系統的規劃和開發工作。

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(國家自然科學基金);the New Century Excellent Talents Foundation from MOE of China under Grant No.NCET-12-0757(教育部新世紀優秀人才支持計劃);the Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education Ministry of China under Grant No.LXJJ201303(教育部留學回國人員科研啟動基金).

CNKI網絡優先出版:2015-10-29,http://www.cnki.net/kcms/detail/11.5602.TP.20151029.1704.002.html

A

TP311.132.3