[个人]哈希表学习+map笔记

小白了解了一下哈希表，这位大佬讲得很生动很好理解→原贴地址
以及C++的map函数使用整理，参考了许多不同文章，整理了常用的部分。主要是阅读原贴链接的笔记。

• 一.理论基础与理解
• • 1.哈希表是什么
  • 2.散列函数
  • 3.关键值key
  • 4.键值对
  • 5.哈希表中存储键值对
  • 6.哈希冲突及处理方法
• 二.C++的map容器用法
• • 1.map的功能
  • 2.使用map函数
  • 3.map基本操作函数

又称散列表。哈希表本质上是数组，数组内的元素通过映射函数产生相应的标号，能够直接通过标号指向需要的元素，更方便地查找元素。
百度解释：

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

哈希表的映射关系的映射函数的称呼，又称哈希函数。

可以看做是确定元素特征的值，通过key能确定需要的元素。其通过哈希函数的处理后得到哈希表的下标位置。如下图示例中学号-姓名中的学号，通过学号能够找到姓名，而哈希表是处理学号得到一个特征下标。

即key-value组合对，如下图示例的学号-姓名组合。在不同的环境下可能有别的称呼（如Entry）。

原贴辅助说明图：

key通过哈希函数被处理成一个存储位置（如上图学号被处理为1），键值对存放在这个位置。

哈希冲突：不同的key通过散列函数处理后得到相同的下标地址，此时便产生了哈希冲突。

处理方法：哈希冲突有很多处理方法，需要拓展可以单独搜索。
主要的两种方法：

（1）开放寻址法 ：寻找别的地址存储。
（2） 拉链法：在同样的位置，采用链表，该位置存在另外的指向别的位置地址的指针，指向冲突的其他键值对。

能够自动建立key － value的对应。key 和 value可以是任意你需要的类型，包括自定义类型。

使用map包含头文件，注意STL头文件没有.h

#include 

初始化定义map函数，map对象是模板类，需要关键字和存储对象两个模板参数

std:map a;

这样就定义了一个用int作为索引,并拥有相关联的指向string的指针。