C++ | 五、哈希表 Hash Table

哈希表基础

• 哈希表是一种数据结构（哈希表包含数组，和前两篇文章叙述的字符串、链表平级）
• 哈希表概念：类似于Python里的字典类型，哈希表把关键码key值通过哈希函数来和哈希表上的索引对应起来，之后输入key值可直接定位到对应索引位置，然后进行取值
• 哈希表的好处：主要为查找方便，可快速判断一个元素是否在集合中
• 哈希函数：即关键码key值和存储位置（索引）的对应关系，一个散列函数，比如把小明映射为0，小李映射为1，如图
  • 
• 哈希碰撞
  • 定义：当哈希函数的映射关系把多个关键码映射到了同一个哈希表索引上时，这种现象称为哈希碰撞，如图所示（哈希碰撞有时候是因为关键码的数量大于哈希表的长度，这时不可避免发生碰撞；但是也可能是哈希函数的对应关系不合理，使得即便仍有空索引，还是把部分关键码分配到了同一索引上）
    • 
  • 其实发生哈希碰撞不见得是个坏事，如果是因为关键码的数量大于哈希表的长度，说明此时哈希表的所有索引都被完全利用，没有发生内存浪费
  • 解决方案一：拉链法
    • 当发生冲突时，在对应索引位置通过链表结构储存多个关键码，如图所示
      • 
  • 解决方案二：线性探测法
    • 如果是哈希函数的对应关系不合理，使得即便仍有空索引，还是把部分关键码分配到了同一索引上，此时可以利用线性探测法，从发生冲突的索引位置开始，线性查找找到下一个空索引，然后把多余的关键码分配过去，如图所示
      • 

常见的三种哈希表结构

• 数组
• set集合
• map映射