C++ 数据结构哈希表_c++要背的表是什么表

1.什么是哈希表

“散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

举例子：

比如说，我现在给你个电话本，上面记录的有姓名和对应的手机号，我想让你帮我找王二的手机号是多少，那么你会怎么做呢？

你可能会说，那挨个找呗。

确实可以，那么你有没有想过，如果这个王二是在最后几页，那你去岂不是前面几页都白找了，有没有更快的方式呢？

是不是可以按照人名给分个类，比如按照首字母来排序，就abcd那样的顺序，这样根据王二我就知道去找w这些，这样不久快很多了。

我们取姓名的首字母作为一个标志，就可以很快的找到以这个字母开头的人名了，那么王二也就能更快的被我们找到，我们也不用再费力气去找什么张二和李二的，因为人家的名字首字母都不是w。

这里我们用到了一种方法：那就是取姓名的首字母做一个排序，那么这是不是就是通过一些特定的方法去得到一个特定的值，比如这里取人名的首字母，那么如果是放到数学中，是不是就是类似一个函数似的，给你一个值，经过某些加工得到另外一个值，就像这里的给你个人名，经过些许加工我们拿到首字母，那么这个函数或者是这个方法在哈希表中就叫做散列函数。

所以说：哈希表就是通过将关键值也就是key通过一个散列函数加工处理之后得到一个值，这个值

就是数据存放的位置，我们就可以根据这个值快速的找到我们想要的数据。

2.unordered_map的用法

它是一个关联容器，内部采用的是哈希表结构，拥有快速检索的功能。

关联性：通过key去检索value，而不是通过绝对地址（和顺序容器不同）

无序性：使用hash表存储，内部无序

Map : 每个值对应一个键值

键唯一性：不存在两个元素的键一样

动态内存管理：使用内存管理模型来动态管理所需要的内存空间

unordered_map的官方定义：

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

主要使用的也是模板的前2个参数<键，值>

unordered_map<const Key, T> map;

unordered_map的迭代器是一个指针，指向这个元素，通过迭代器来取得它的值

unordered_map<Key,T>::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair<const Key,T>) 

其中it->first返回的是key值，it->second返回的是value值

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
    //创建 umap 容器
    unordered_map<string, string> umap{
        {"Python教程","http://c.biancheng.net/python/"},
        {"Java教程","http://c.biancheng.net/java/"},
        {"Linux教程","http://c.biancheng.net/linux/"} };
    cout << "umap 存储的键值对包括：" << endl;
    //遍历输出 umap 容器中所有的键值对
    for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
        cout << "<" << iter->first << ", " << iter->second << ">" << endl;
    }
    //获取指向指定键值对的前向迭代器
    unordered_map<string, string>::iterator iter = umap.find("Java教程");
    cout <<"umap.find(\"Java教程\") = " << "<" << iter->first << ", " << iter->second << ">" << endl;
    return 0;
}

注意，遍历打印后是乱序的，unordered map是hash表。不是排序的。只有map是排序的，但是map打印也和构造的顺序不一样。

所以键值对的容器一般用来查找，而不是顺序存储。

构造函数：

unordered_map<int,int>hashmap_1;//构造空的容器
unordered_map<string,int>hashmap_2{{"Jan",44}, {"Jim", 33}, {"Joe", 99}};//直接构造
unordered_map<string,int>hashmap_3(hashmap_2);// 复制初始化
unordered_map<string,int>hashmap_4(hashmap_2.begin(),hashmap_2.end());// 范围初始化

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
 
typedef unordered_map<string,string> stringmap;
 
int main ()
{
  stringmap first;                              // 空
  stringmap second = {{"apple","red"},{"lemon","yellow"}};       // 用数组初始
  stringmap third = {{"orange","orange"},{"strawberry","red"}};  // 用数组初始
  stringmap fourth (second);                    // 复制初始化
  stringmap sixth (fifth.begin(),fifth.end());  // 范围初始化
 
  cout << "sixth contains:";
  for (auto& x: sixth) cout << " " << x.first << ":" << x.second;
  cout << endl;
 
  return 0;
}

size返回unordered_map容器中的元素数量

mymap.size()

max_size返回unordered_map容器可以容纳的元素的最大数量

mymap.max_size()

empty判断容器是否为空

mymap.empty()

find查找元素

//查找key所在的元素。
//- 找到：返回元素的迭代器。通过迭代器的first和second属性获取值
//- 没找到：返回unordered_map::end
string input = "mom";
unordered_map<string, double>::const_iterator got = mymap.find(input);
if(got == mymap.end())
    cout << "not found";
else
    cout << got->first << " is " << got->second;

insert插入元素

unordered_map<string,double> myrecipe;
unordered_map<string,double> mypantry = {{"milk",2.0},{"flour",1.5}};
pair<string,double> myshopping ("baking powder",0.3);
myrecipe.insert (myshopping);                        // 复制插入
myrecipe.insert (make_pair<string,double>("eggs",6.0)); // 移动插入
myrecipe.insert (mypantry.begin(), mypantry.end());  // 范围插入
myrecipe.insert ({{"sugar",0.8},{"salt",0.1}});    // 初始化数组插入(可以用二维一次插入多个元素，也可以用一维插入一个元素)
myrecipe["coffee"] = 10.0;  //数组形式插入

clear清空元素

   unordered_map<int,int>mymap = {{1111,1},{1112,2},{1113,4},{1114,6},{1115,8},{1117,10}};
    cout<<mymap.size()<<"  "<<mymap.max_size()<<"   "<<mymap.bucket_count()<<endl;    
    mymap.clear();
    cout<<mymap.size()<<"  "<<mymap.max_size()<<"   "<<mymap.bucket_count()<<endl;  

3.哈希表编程示例

两数之和（力扣第一题），使用哈希表。

给定一个数组和目标值，使得数组中两个数相加等于目标值。

#include <iostream>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
class node{
public:
	vector<int> twosun(vector<int>& nums,int target){
	   unordered_map<int,int> record;
	   for(int i = 0;i<nums.size();i++){
	      int num = target - nums[i];
		  if(record.find(num) != record.end()){
		     return {record[num],i};
		  }
		  record[nums[i]] = i;
	   }
	   return {-1,-1};
	}
};
 
int main(){
 
   node n;
   vector<int> tem;
   vector<int> cur = {5,2,3,7,8};
   tem = n.twosun(cur,9);
   for(int i = 0;i<tem.size();i++){
      cout << tem[i] << " ";
   }
	
   return -1;
}

最长连续序列（力扣128题）：

给定一个数组nums，求最长连续序列的长度。

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
 
class node{
public:
	int longsetconsecutive(vector<int>& nums){
	   unordered_set<int> st(nums.begin(),nums.end());
	   int ans = 0;
	   for(int num:st){
	      if(!st.count(num-1)){
		     int x = num + 1;
			 while(st.count(x)) x++;
			 ans = max(ans,x-num);
		  }
	   }
	   return ans;
	}
};
 
int main()
{
   node n;
   vector<int> ans = {2,1,3,1,4,7,8};
   cout << n.longsetconsecutive(ans) << endl;
	
   return 0;
}