本文共 2048 字,大约阅读时间需要 6 分钟。
下面所讲内容hash_map的案例代码实现以及附加数据
我们知道hash_map是利用hash table实现的一种数据结构,能够快速根据KEY值查找对应的VALUE。hash_map特点是查找快,但是占用内存高,因为hash_map在初始化的时候需要为每个桶分配一块连续的内存块。所以适用于要求快速查找,同时不计较内存消耗的情形中。
使用c++实现sql语句:
select c_nationkey, c_mktsegment, count(*), max(c_acctbal) from aaa_customer_1g group by c_nationkey, c_mktsegment order by c_nationkey, c_mktsegmentaaa_customer_1g表中的数据:
我们使用hash_map来实现group by的操作。
因为 group by后面有2个字段,所以我们自定义一个struct结构体作为KEY:
struct KEY { int c_nationkey; std::string c_mktsegment; bool operator==(const KEY & my) const { return (my.c_nationkey == c_nationkey) && (my.c_mktsegment.compare(c_mktsegment) == 0); }};
上面结构体中operator==就是我们所构建的equal_function。c_nationkey字段中的值记为nk,c_mktsegment字段中的值记为mg。group by利用hash_map实现:找出相同的nk所对应的行rows1,然后在row1中找出相同的mg所对应的行rows2,然后对rows2进行统计处理,在本例中统计rows2的行数(count(*))、rows2中最大的c_acctbal(max(c_acctbal) )。
下面的结构体是我们上面的sql语句要输出的数据:
struct VALUE { int c_nationkey; string c_mktsegment; int count; double max_c_acctbal;};
下面这段程序中RSHash_new函数是众多hash function一种,选择不同,hash map执行的性能也会不同。主要从两方面考虑:1、选择的hash function尽量不要让桶内的数据产生倾斜,也就是让数据均匀分布到各桶中;2、选择的hash function时间复杂度要小,也就是让其执行时间缩小,这是因为每个记录(行)都会执行hash function,当数据量变得越来越大时,hash function整体消耗时间也会变得很大。
unsigned int RSHash_new(const KEY& key) { unsigned int b = 378551; unsigned int a = 63689; unsigned int hash = 0; for(std::size_t i = 0; i < key.c_mktsegment.length(); i++) { hash = hash * a + key.c_mktsegment[i]; a = a * b; } hash = hash * a + key.c_nationkey; return hash;}struct str_hash{ size_t operator()(const KEY& key) const { return RSHash_new(key); }};
如果你不好确定上面2个因素,那你就选择不同的hash function,测出他们运行的时间,选择最小时间的hash function。
Notice:现在绝大多数的hash function输入参数都是字符串的形式,但是实际中是不同类型的组合(本例是int、string),需要把int、string类型强制转换组合成一个string类型,然后再使用hash function,这样严重违背了上面我所讲到的第2点,hash_map执行性能严重下降。
hash_map> _hash_data;
下面的下载地址是我的完整程序并附有数据,我是在linux下开发的,执行下面指令进行编译:
g++ main.cpp parserXML.h hash_function.h tinyxml/libtinyxml.a -o main