编程参考 - C++使用hashmap

C++标准库里的container包含了ordered和unordered的map(std::map和std::unordered_map)。

在ordered map中各个单元(elements)根据key排序插入和访问的复杂度是O(log n)。标准库的ordered map的内部实现一般是使用红黑树(red black trees)是一种平衡二叉树( balanced binary search tree)。

但这属于实现细节不影响我们的使用。

在unordered map中插入和访问(insert and access)操作的复杂度是O(1)。可以认为仅仅名称和hashtable不一样而已在Java的标准库中使用的类名就是hashtable。

使用hash方法只是内部实现的细节在C++标准并没有规定必须使用hashtable来实现unordered map而且使用unordered_map的抽象名称表示的更准确。

ordered map维持了元素的排序方便你按顺序从头到尾遍历各个元素而unordered map中是没有顺序可言的。

使用std::map的例子

#include <map>

#include <iostream>

#include <cassert>

int main(int argc, char** argv)

{

  std::map<std::string, int> m;

  m["hello"] = 23;

  // check if key is present

  if(m.find("world") != m.end())

    std::cout << "map contains key world!\n";

  // retrieve

  std::cout << m["hello"] << '\n';

  std::map<std::string, int>::iterator i = m.find("hello");

  assert(i != m.end());

  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';

  return 0;

}

输出

23

Key: hello Value: 23

如果你需要使用的容器类的内容进行排序时间复杂度O(log n)也没问题的话就使用std::map。但需要注意每个元素里的key要能使用小于号的运算符即实现了operator<。

否则的话你应该要用hash-tableinsert/access的时间复杂度是O(1)。在C++里相应的类就是std::unordered_map它的API和std::map类似。还有一点每个元素的key对象要有hash函数一般int和string对象是有默认现成的哈希函数的但有些对象没有的话就要自己实现。还要能用等号运算符即实现了operator==。

unordered_map的这个container是在C++ 11标准中引入的。所以你的编译器要支持才行。比如在GCC 4.8中就需要在CXXFLAGS中加入选项-std=c++11。

注CXXFLAGS和CFLAGS常用作C/C++程序构建时所使用的编译器选项的环境变量(compiler flags)。

甚至在C++11发布之前GCC就支持unordered_map不过是在命名空间std::tr1中。因此对于老的GCC编译器你可以尝试这样使用它

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

使用说明

具体的使用方法请参见cplusplus.com或en.cppreference.com上关于此类的说明文档包含了各个类成员的介绍。

std::unordered_map - cppreference.com

https://cplusplus.com/reference/unordered_map/

常用的 成员函数分为Capacity、Iterators、Element access、Element lookup、Modifiers、Buckets、Hash policy和Observers几类。

包括如下成员函数

empty -  判断是否为空

size - 元素数量

begin - 遍历开始

end - 遍历结尾

operator[ ] - 元素访问如果key不存在则添加最常用函数而不是用at访问元素

at - 元素访问如果key不存在则报异常不捕捉会导致程序crash退出

find - 查找元素

emplace - 构造新元素并添加如果元素已存在则返回的bool值为false且操作不成功否则为true并添加元素

insert - 插入元素如果元素已存在则返回的bool值为false且操作不成功否则为true并添加元素

erase - 删除元素

clear - 清除全部元素无返回值没有异常情况

swap - 两个map交换内容

成员函数使用举例

  mymap.erase ( mymap.begin() );      // erasing by iterator

  mymap.erase ("France");             // erasing by key

  mymap.erase ( mymap.find("China"), mymap.end() ); // erasing by range

  mymap.emplace("PINK", "#222222");  // std::map<std::string, std::string>

insert函数使用举例

// unordered_map::insert

#include <iostream>

#include <string>

#include <unordered_map>

int main ()

{

  std::unordered_map<std::string,double>

              myrecipe,

              mypantry = {{"milk",2.0},{"flour",1.5}};

  std::pair<std::string,double> myshopping ("baking powder",0.3);

  myrecipe.insert (myshopping);                        // copy insertion

  myrecipe.insert (std::make_pair<std::string,double>("eggs",6.0)); // move insertion

  myrecipe.insert (mypantry.begin(), mypantry.end());  // range insertion

  myrecipe.insert ( {{"sugar",0.8},{"salt",0.1}} );    // initializer list insertion

  std::cout << "myrecipe contains:" << std::endl;

  for (auto& x: myrecipe)

    std::cout << x.first << ": " << x.second << std::endl;

  std::cout << std::endl;

  return 0;

}

输出

myrecipe contains:

salt: 0.1

eggs: 6

sugar: 0.8

baking powder: 0.3

flour: 1.5

milk: 2

程序例子

#include <iostream>

#include <string>

#include <unordered_map>

int main(){

    // Create an unordered_map of three strings (that map to strings)

    std::unordered_map<std::string, std::string> u = {

        {"RED","#FF0000"},

        {"GREEN","#00FF00"},

        {"BLUE","#0000FF"}

    };

    // Add two new entries to the unordered_map

    u["BLACK"] = "#000000";

    u["WHITE"] = "#FFFFFF";

    std::cout << "\nOutput values by key:\n"

                 "The HEX of color RED is:[" << u["RED"] << "]\n"

                 "The HEX of color BLACK is:[" << u["BLACK"] << "]\n\n";

    std::cout << "Use operator[] with non-existent key to insert a new key-value pair:\n";

    std::cout << "Key:[" << "new_key" << "] Value:[" << u["new_key"] << "]\n";

    // Assign new value for "new key"

    std::cout << "\nSet value for new_key: #111111.\n";

    u["new_key"] = "#111111";

    

    std::cout << "\nIterate and print key-value pairs, using `auto`;\n"

                 "new_key is now one of the keys in the map:\n";

    u.emplace("PINK", "#222222");  

    u.insert(std::make_pair<std::string,std::string>("YELLOW", "#222222"));

    for( const auto& n : u ) {

        std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";

    }

    

    return 0;

}

输出结果

Output values by key:

The HEX of color RED is:[#FF0000]

The HEX of color BLACK is:[#000000]

Use operator[] with non-existent key to insert a new key-value pair:

Key:[new_key] Value:[]

Set value for new_key: #111111.

Iterate and print key-value pairs, using `auto`;

new_key is now one of the keys in the map:

Key:[YELLOW] Value:[#222222]

Key:[new_key] Value:[#111111]

Key:[BLUE] Value:[#0000FF]

Key:[RED] Value:[#FF0000]

Key:[GREEN] Value:[#00FF00]

Key:[BLACK] Value:[#000000]

Key:[WHITE] Value:[#FFFFFF]

Key:[PINK] Value:[#222222]

HashTable简单原理介绍

针对一个key对象使用hash函数计算得到一个整数值也叫hash值或哈希值。

相同的key对象得到的是相同的hash值。不同的key对象计算的值一般都是不同的如果相同就认为是碰撞(collisions)发生了这不是我们所希望见到的情况。

使用计算得到整数值也就是hash值唯一标记了一个对象根据hash值就能快速判断两个对象是否相等如果hash值不同则一定不同如果hash相等可以进一步比较对象内容来判断是否相同。

除此以外也可以使用hash值来作为索引访问和此对象相关的内容这就是map中的key和value。

上面计算出的hash值的范围是由hash算法决定的因为尽可能不同的对象所计算出的hash值是不同的那这个整数hash值就不会太小。如果直接作为索引需要的空间就会很大。

所以一般是先确定一个空间大小然后用hash值对这个空间大小取模来存放和访问相关信息。

如果取模以后的整数值相同而对象却不同就发生了碰撞就要再使用一个公式寻找一个新位置。当位置不够了就要增加整个空间的大小。

实际使用举例以及注意事项

1直接定义map没有问题。

#include <map>

typedef struct {

unsigned char BD_ADDR0;

unsigned char BD_ADDR1;

unsigned char BD_ADDR2;

unsigned char BD_ADDR3;

unsigned char BD_ADDR4;

unsigned char BD_ADDR5;

} BD_ADDR_t;

int main()

{

  std::map<BD_ADDR_t, int> mymap;

  return 0;

}

2但如果使用map就会出现编译错误比如添加一个元素。

int main() {

  BD_ADDR_t addr = {1,2,3,4,5,6};

  std::map<BD_ADDR_t, int> mymap;

  mymap[addr] = 1;

  return 0;

}

错误信息

$ g++ -o main main.cpp

In file included from /usr/include/c++/9/bits/stl_tree.h:65,

                 from /usr/include/c++/9/map:60,

                 from main.cpp:2:

/usr/include/c++/9/bits/stl_function.h: In instantiation of ‘constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = BD_ADDR_t]’:

/usr/include/c++/9/bits/stl_map.h:497:32:   required from ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = BD_ADDR_t; _Tp = int; _Compare = std::less<BD_ADDR_t>; _Alloc = std::allocator<std::pair<const BD_ADDR_t, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = BD_ADDR_t]’

main.cpp:18:13:   required from here

/usr/include/c++/9/bits/stl_function.h:386:20: error: no match for ‘operator<’ (operand types are ‘const BD_ADDR_t’ and ‘const BD_ADDR_t’)

  386 |       { return __x < __y; }

      |                ~~~~^~~~~

只要使用要访问元素的函数都会出错比如find函数也一样。但其他函数可能运行正常比如调用empty函数的话就能正常编译过。

3看到提示是因为这个key类型没有定义operator<。我们一般使用int和string类型是有这个运算符的如果使用其他的类型就可能需要自己实现operator<。

添加一个operator<函数再试一下这个也叫operator overloadingC++里的运算符重载

bool operator<(BD_ADDR_t a,  BD_ADDR_t b) {return false;}

int main()

{

  bool flag;

  BD_ADDR_t addr = {1,2,3,4,5,6};

  std::map<BD_ADDR_t, int> mymap;

  mymap[addr] = 2;

  flag = mymap.empty();

  return 0;

}

现在编译运行都成功。所以当使用map的访问元素的功能时编译器在根据模板生成代码时就会去寻找key对象的小于号操作符如果找不到就会报错。

只需要一个小于号就能比较两个对象分三种情况

a<b, 直接判断出

a>b, 使用b<a的运算来判断。

a==b如果a<b为假b<a也为假就是a==b或者表达为 !(a<b || b<a)

4如果是unordered_map仅仅是定义就会出错

#include <unordered_map>

typedef struct {

unsigned char BD_ADDR0;

unsigned char BD_ADDR1;

unsigned char BD_ADDR2;

unsigned char BD_ADDR3;

unsigned char BD_ADDR4;

unsigned char BD_ADDR5;

} BD_ADDR_t;

int main()

{

  BD_ADDR_t addr = {1,2,3,4,5,6};

  std::unordered_map<BD_ADDR_t, int> mymap;

  return 0;

}

       

编译错误里有出现

/usr/include/c++/9/bits/hashtable_policy.h:1096:7: error: use of deleted function ‘std::hash<BD_ADDR_t>::hash()’

所以需要给BD_ADDR_t对象定义一个hash函数语法如下

unordered_map<KeyType, ValueType, MyHashType> um;

例子代码

#include <unordered_map>

typedef struct {

unsigned char BD_ADDR0;

unsigned char BD_ADDR1;

unsigned char BD_ADDR2;

unsigned char BD_ADDR3;

unsigned char BD_ADDR4;

unsigned char BD_ADDR5;

} BD_ADDR_t;

class MyHashFunction{

public:

  size_t operator()(const BD_ADDR_t & p) const

  {

    return p.BD_ADDR0 + p.BD_ADDR1 + p.BD_ADDR2 + p.BD_ADDR3 + p.BD_ADDR4 + p.BD_ADDR5;

  }

};

int main()

{

  BD_ADDR_t addr = {1,2,3,4,5,6};

  std::unordered_map<BD_ADDR_t, int, MyHashFunction> mymap;

  return 0;

}

现在的代码就可以编过了。这里定义了一个类对()运算符进行重载对BD_ADDR_t类型对象进行计算hash值返回一个size_t类型。

5在给unordered_map添加了hash function之后再调用访问元素的函数发现还会出错提示的编译错误是在模板代码进行扩展时没有找到operator==的定义。

例子代码和编译错误显示如下

#include <unordered_map>

typedef struct {

unsigned char BD_ADDR0;

unsigned char BD_ADDR1;

unsigned char BD_ADDR2;

unsigned char BD_ADDR3;

unsigned char BD_ADDR4;

unsigned char BD_ADDR5;

} BD_ADDR_t;

class MyHashFunction{

public:

  size_t operator()(const BD_ADDR_t & p) const

  {

    return p.BD_ADDR0 + p.BD_ADDR1 + p.BD_ADDR2 + p.BD_ADDR3 + p.BD_ADDR4 + p.BD_ADDR5;

  }

};

int main()

{

  BD_ADDR_t addr = {1,2,3,4,5,6};

  std::unordered_map<BD_ADDR_t, int, MyHashFunction> mymap;

  mymap[addr] = 123;

  return 0;

}

编译错误

main.cpp:30:13:   required from here

/usr/include/c++/9/bits/stl_function.h:356:20: error: no match for ‘operator==’ (operand types are ‘const BD_ADDR_t’ and ‘const BD_ADDR_t’)

  356 |       { return __x == __y; }

      |                ~~~~^~~~~~

这个是因为unordered_map和map的对元素的访问原理不同。map的每个key的位置也都按顺序排好所以需要根据小于号来找到位置遍历二叉树的元素时判断是当前节点的左分支还是右分支或者就是当前节点。

而unordered_map是hash值计算后直接得到位置再进行访问但有可能出现碰撞碰撞时要判断两个对象是否一样所以就需要等号运算符。

6添加一个operator==函数。

#include <unordered_map>

typedef struct {

unsigned char BD_ADDR0;

unsigned char BD_ADDR1;

unsigned char BD_ADDR2;

unsigned char BD_ADDR3;

unsigned char BD_ADDR4;

unsigned char BD_ADDR5;

} BD_ADDR_t;

class MyHashFunction{

public:

  size_t operator()(const BD_ADDR_t & p) const

  {

    return p.BD_ADDR0 + p.BD_ADDR1 + p.BD_ADDR2 + p.BD_ADDR3 + p.BD_ADDR4 + p.BD_ADDR5;

  }

};

bool operator==(const BD_ADDR_t & a, const BD_ADDR_t & b){

  return (a.BD_ADDR0 == b.BD_ADDR0) && (a.BD_ADDR1 == b.BD_ADDR1) &&

          (a.BD_ADDR2 == b.BD_ADDR2) && (a.BD_ADDR3 == b.BD_ADDR3) &&

          (a.BD_ADDR4 == b.BD_ADDR4) && (a.BD_ADDR5 == b.BD_ADDR5);

}

int main()

{

  bool flag;

  BD_ADDR_t addr = {1,2,3,4,5,6};

  std::unordered_map<BD_ADDR_t, int, MyHashFunction> mymap;

  mymap[addr] = 123;

  return 0;

}

编译成功可以正常使用了。

参考

What is the best way to use a HashMap in C++? - Stack Overflow

c++ - what the difference between map and hashmap in STL - Stack Overflow

map vs. hash_map in C++ - Stack Overflow

How to create an unordered_map of user defined class in C++? - GeeksforGeeks