哈希表

哈希表（Hash Table），也称为散列表，是一种数据结构，它可以提供非常快速的数据插入和查找操作。哈希表通过一个称为哈希函数（Hash Function）的算法，将键（Key）转换为数组索引，从而能够快速定位到数据的存储位置。

在哈希表中，每个键值对（Key-Value Pair）都被哈希函数映射到表中的一个位置，以便快速访问。但是，由于不同的键可能会被映射到同一个位置，这就产生了所谓的哈希冲突（Hash Collision）。为了解决冲突，有几种方法可以使用，如链地址法（Chaining）和开放地址法（Open Addressing）。

链地址法是在冲突发生的索引处使用链表来存储所有映射到该索引的元素。而开放地址法则是寻找另一个空闲的位置来存储冲突的元素。

哈希表的性能很大程度上取决于哈希函数的设计和冲突解决机制的效率。设计良好的哈希表可以在接近 O(1) 的时间复杂度内完成插入和查找操作，这使得哈希表成为一种非常高效的数据结构。

​

C++ STL 之 哈希表

如何使用STL库中的哈希表

（1）导入头文件   #include<unordered_map> （2）哈希表的声明和初始化     1）声明

unordered_map<elemType_1, elemType_2> var_name; //声明一个没有任何元素的哈希表，
//其中elemType_1和elemType_2是模板允许定义的类型，如要定义一个键值对都为Int的哈希表：
unordered_map<int, int> map;

2）初始化     以上在声明哈希表的时候并没有给unordered_map传递任何参数，因此调用的是unordered_map的默认构造函数，生成一个空容器。初始化主要有一下几种方式：      a）在定义哈希表的时候通过初始化列表中的元素初始化:

unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
//如果知道要创建的哈希表的元素个数时，也可以在初始化列表中指定元素个数
unordered_map<int, int> hmap{ {{1,10},{2,12},{3,13}},3 };

b）通过下标运算来添加元素:

//当我们想向哈希表中添加元素时也可以直接通过下标运算符添加元素，格式为: mapName[key]=value;
//如：hmap[4] = 14;
//但是这样的添加元素的方式会产生覆盖的问题，也就是当hmap中key为4的存储位置有值时，
//再用hmap[4]=value添加元素，会将原哈希表中key为4存储的元素覆盖
hmap[4] = 14;
hmap[4] = 15;
cout << hmap[4];  //结果为15

c）通过insert()函数来添加元素:

//通过insert()函数来添加元素的结果和通过下标来添加元素的结果一样，不同的是insert()可以避免覆盖问题，
//insert()函数在同一个key中插入两次，第二次插入会失败
hmap.insert({ 5,15 });
hmap.insert({ 5,16 });
cout << hmap[5];  //结果为15

d）复制构造，通过其他已初始化的哈希表来初始新的表:

unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
unordered_map<int, int> hmap1(hmap);

STL中哈希表的常用函数

(1) begin( )函数：该函数返回一个指向哈希表开始位置的迭代器

unordered_map<int, int>::iterator iter = hmap.begin(); //申请迭代器，并初始化为哈希表的起始位置
cout << iter->first << ":" << iter->second;

(2) end( )函数：作用于begin函数相同，返回一个指向哈希表结尾位置的下一个元素的迭代器

unordered_map<int, int>::iterator iter = hmap.end();

(3) cbegin() 和 cend()：这两个函数的功能和begin()与end()的功能相同，唯一的区别是cbegin()和cend()是面向不可变的哈希表

const unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
unordered_map<int, int>::const_iterator iter_b = hmap.cbegin(); //注意这里的迭代器也要是不可变的const_iterator迭代器
unordered_map<int, int>::const_iterator iter_e = hmap.cend();

(4) empty()函数：判断哈希表是否为空，空则返回true，非空返回false

bool isEmpty = hmap.empty();

(5) size()函数：返回哈希表的大小

int size = hmap.size();

(6) erase()函数： 删除某个位置的元素，或者删除某个位置开始到某个位置结束这一范围内的元素， 或者传入key值删除键值对

unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
unordered_map<int, int>::iterator iter_begin = hmap.begin();
unordered_map<int, int>::iterator iter_end = hmap.end();
hmap.erase(iter_begin);  //删除开始位置的元素
hmap.erase(iter_begin, iter_end); //删除开始位置和结束位置之间的元素
hmap.erase(3); //删除key==3的键值对

(7) at()函数：根据key查找哈希表中的元素

unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
int elem = hmap.at(3);

(8) clear()函数：清空哈希表中的元素

hmap.clear()

(9) find()函数：以key作为参数寻找哈希表中的元素，如果哈希表中存在该key值则返回该位置上的迭代器，否则返回哈希表最后一个元素下一位置上的迭代器

unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
unordered_map<int, int>::iterator iter;
iter = hmap.find(2); //返回key==2的迭代器，可以通过iter->second访问该key对应的元素
if(iter != hmap.end())  cout << iter->second;

(10) bucket()函数：以key寻找哈希表中该元素的储存的bucket编号（unordered_map的源码是基于拉链式的哈希表，所以是通过一个个bucket存储元素）

int pos = hmap.bucket(key);

(11) bucket_count()函数：该函数返回哈希表中存在的存储桶总数（一个存储桶可以用来存放多个元素，也可以不存放元素，并且bucket的个数大于等于元素个数）

int count = hmap.bucket_count();

(12) count()函数： 统计某个key值对应的元素个数， 因为unordered_map不允许重复元素，所以返回值为0或1

int count = hmap.count(key);

(13) 哈希表的遍历: 通过迭代器遍历

unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
unordered_map<int, int>::iterator iter = hmap.begin();
for( ; iter != hmap.end(); iter++){
 cout << "key: " <<  iter->first  << "value: " <<  iter->second <<endl;
}

————————————————

                        版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/Peealy/article/details/116895964