数据结构（三）：散列表

本系列为数据结构学习笔记，如有错误请指正~
数据结构（一）：数组和链表
数据结构（二）：栈和队列

一、基本概念

• 散列表：也叫哈希表（hash table），提供键（key）和值（Value）的映射关系

• Hash函数：散列表在本质上是一个数组，每个key都会对应一个数组下标，hash函数就是负责将key转换为数组下标

• 键值对（Entry）

  • 键（Key）：一个可以被快速得到的值，用来定位元素
  • 值（Value）：与key所匹配的值

二、应用场景

散列表适合做一本字典。

一本字典，我们需要查什么字，只需要根据目录便可快速定位到某个字的位置，不管是查找规则还是效率都很高。而散列表也有着同样的功能，只要给出一个Key，便可以高效查找对应的Value，时间复杂度接近O(1)。

三、读写

因为散列表的本质，所以读写其实就是根据hash函数将key变为下标的过程

1. 写

通过hash函数将key转换成数组下标，如果该下标对应的位置没有值，则将数据插入进去；如果有值的话，则会发生哈希冲突，我们需要解决哈希冲突

解决哈希冲突常见的主要有两种方法：开放寻址法、链表法
1）开放寻址法

比如数组下标为2的位置已经有值了，那么就看看下标为3的位置是否有数据，有的话插入，没有的话继续往下找，直到找到为止，如果一直找不到就需要扩容了。

2）链表法

Java中的HashMap就是采用的此方法。

数组的每个元素都与一个链表对应，也就是说HashMap数组中的每一个元素不仅是一个键值对，还是一个链表的头节点。这样的话，通过哈希函数将key转换为数组下标后就不用担心该位置是否有值了，即使有值也只需要在该位置对应的链表中插入数据即可

2. 读

通过给定的Key，在Hash表中查找对饮的Value，只需要通过Hash函数将Key转换为数组下标，然后找到对应的值即可。