哈希表(散列表)
哈希表有时候也被称作散列表，它是怎么来的呢？在之前我们介绍过了顺序表，他的查找是O（1）的，但是他的删除和插入是O（n）的，虽然双端链表的按照节点的删除和插入是O（1）的，但是他的按值查找是O（n）的，其实都不是很理想，那么有没有删除和查找都很快的数据结构呢？
这个时候就有了哈希表。
哈希表是什么原理呢？
举个例子，如果我们这里有一个数组，他包含13个元素，我们先定义一个简单的哈希函数，就用插入元素的值对13取模运算，然后我们拿到取模的值按照该值进行相同的索引插入，但是插了几个数字之后我们发现不同的插入元素有着相同的取模运算的结果，那么就遇到了我们的第一个问题，也就是哈希冲突，怎么解决呢？可能有些同学已经想到了，我们再通过加入一点算法让这个取模运算后的值变大或者变小，总之就是让该取模值找到一个空的位置可以插入，科学家就在此基础上提出了三种解决方法，分别是线性探查、二次探查和双重散列，三者本质上都是在原有基础上对取模值加上某值再次进行取模运算（还有一种传统方法，就是对冲突的值的位置上建立一个链表结构，但是数据大了是不可取的，这里不多介绍），这个时候我们再次插值，但是快结束的时候我们发现数组大小不够用了，基于这个科学家又提出了负载因子的概念，负载因子说的普通点就是要插入的元素除以数组的大小，一般负载因子大小超过80%的时候我们就要进行重哈希操作，重哈希就是扩大数组的大小，这个由个人决定了，Cpython一般是扩大两倍。
哈希表本质上就是这样一个东东，在实现的时候我们要注意一点，也就是插槽的三种状态，第一种是从来没有被插入过元素的，第二种是插入过元素然后被删除的，第三种是已经被插入值的槽。为什么要把第二种拿出来说呢？因为我们在某个槽插入节点后，把该槽的节点删除的时候，他的key和value是none，在查找值的过程中是无法判断我们要搜索的值是否等于none的，因为none是无法判断的。