个人哈希表笔记

前言：

��为本人正在学习C++,所以这个笔记只涉及哈希表的简单介绍，以及C++中unordered_map的使用方面，后续学习的更多，笔记会做的更完善。

哈希表简介

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

    也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

    这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

进一步解释

散列函数 

因为哈希表的底层逻辑仍然是数组，那么仍然保留有数组的相关特点：连续的，有固定下标。查找元素的时间复杂度小。而哈希表的结构表面上就是键-值两个元素，打眼一看与数组好像没什么关系，但哈希表具有查找元素的高效性的原因，就是因为散列函数。

具体可以理解为，对表中key 的离散化，将其离散到固定的数组下标，再映射到value从而找到它。

从这几张图就可以很清楚的看到哈希表的存储方式了。

键值对

哈希表存放的就是键值对，可以通过key快速的访问value的值。 

键值对就是 key-value的组合

 

unordered_map

介绍

c++的容器——unordered_map，它是一个关联容器，内部采用的是hash表结构，拥有快速检索的功能。

特性：

• 关联性：unordered_map是一个将key和value关联起来的容器，通过key去检索value，而不是通过绝对地址（和顺序容器不同），它可以通过键直接访问值，查找数据更为高效。 
• 无序性：unordered_map存储元素是没有顺序的，只是根据key的哈希值， 将元素存在指定位置，所以根据key查找单个value时非常高效，平均可以在常数时间内完成。
• key值应该是唯一的，key和value的数据类型可以不相同。
• unordered_map查询单个key的时候效率比map高，但是要查询某一范围内的key值时比map效率低。

  使用

  构造unordered_map

  #include     //unordered_map的头文件/*构造哈希表*/unordered_map hashmap_1;     //构造空的容器unordered_map hashmap_2 = {{"apple", 1}, {"grape", 2}, {"chery", 3}};    //直接构造unordered_map hashmap_3(hashmap_2);    //复制初始化，注意：使用复制初始化，两个容器内元素的类型要相同unordered_map hashmap_4(hashmap_2.begin(), hashmap_2.end());    //范围初始化unordered_map hashmap_5["pear"] = 1;    //使用键值作为下标的形式，向表中添加元素 

  容量操作

  /*容量操作*/cout {"strawberry", 4}};pair