关键词: 哈希图, 分组, 连接, 缓存感知, 缓存不敏感, 列存储数据库, BHMap

Abstract: 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.

Key words: HashMap, group by, join, cache-conscious, cache-oblivious, column-oriented database, BHMap