数据结构与算法 - 散列表
《数据结构与算法-王争》学习笔记，记录备查
基本概念
散列表，利用数组支持安下标随机访问的数据特性来访问数据。是数组的一种扩展，可以说没有数组就没有散列表。
散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
散列函数
散列函数 hash(key)，又叫哈希函数。key 叫做键或者关键字，hash(key)得到值叫做散列值。
构造设计散列函数的基本要求：
- 散列函数计算得到的散列值是一个非负整数。
- 如果key1=key2, 那hash(key1)==hash(key2)。
- 如果key2!=key2，那么hash(key1)!=hash(key2)。
前两点很好理解，第三点，当数据量足够大的时候，并不能够完全的保证，不同的key得到的散列值完全不同。而数据的存储空间有限，也会进一步加剧这种冲突。这种冲突有一个名词，叫做散列冲突。
散列冲突无法根本性的避免，我们需要通过其他方法解决，常用的方法主要有两类：开放寻址法(open addressing)和列表法(chaining)。
散列冲突可以理解为根据散列函数计算出数据下标，向数组中插入数据，当数组中有数据时，即发生散列冲突。
散列冲突的概率可以使用装载因子来表示，即散列表的空闲位置越少，散列冲突发生的概率便会越大，反之也成立。
装载因子的公式如下：
散列表的装载因子=填入表中的元素个数/散列表的长度装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
解决散列冲突发放
开放寻址法
中心思想，如果出现散列冲突，就重新探测一个空闲位置，将元素插入。主要有下面几种方法：
线性探测
当数据插入时，根据散列函数得到的下标位置有数据，即发生散列冲突时，往下标大的方向继续探测，直到找到空闲的位置，如果到数组末尾都未找到，则从数据头继续开始查找探测。
当数据查找时，我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
当删除数据时，不能简单的将数组的值为空，这样会影响查找的正确性。我们把删除的位置标记为deleted，这样当查到到该位置时，不会停止退出，而会继续。
二次探测
二次探测和线性探测类型，只是步长是原来的二次方而不是1了。
双重探测
双重探测，是不仅经过一层散列函数，经过多次散列函数直到空闲的位置。
优点：
- 数据都存储在数组中，可有效的利用CPU缓存加速查询速度。
- 不包含链表指针，序列化起来比较简单
缺点：
- 删除数据比较麻烦，需要标记而不是直接置空。
- 因为数据都存储在数组中，装填因子增长速度快，更容器引起散列冲突。
当数据量比较小、装载因子小的时候，适用开发寻址发。
链表法
链表法，如上图，通过散列函数计算拿出来的散列值都已列表的形式挂到对应的槽位上。当我们查到、插入或删除时，只需通过哈希函数计算出对应的槽位，然后再依次遍历对应的链表即可。
插入的时间复杂度时O(1)，查找和删除耗费的时间主要在链表的查找上，所以时间复杂度为O(n)。
优点：
- 内存的利用率相比开发寻址高，因为是用到是才会申请的。
- 对装载因子的容忍度更高，散列冲突几率更小。因为散列值存储在链表中，即使装载因子很大，也只是链表增长而已。
缺点：
- 当存储对象很小时会很耗费内存，因为需要存储额外的指针，小对象无法忽略指针的占用空间。
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
散列表常见的几个问题
如何设计一个好的散列函数
设计一个好的散列函数需要注意一下规则：
- 散列函数的设计不能太复杂；
- 散列函数生成的值要尽可能随机的并列均匀分布；
装填因子过大如何处理
装填因子越大说明散列表中的数据越多，即越容易发生散列冲突。此时，我们便需要申请更大的存储空间来存储散列值，即需要动态扩容。
这里需要注意，散列表的动态扩容不同于数组，在新散列表中的位置是需要用散列函数重新计算来获得的，而不是像数组一样平移。散列表的动态扩容的时间复杂度和数组、栈一样都为O(n)。
为了避免或减少散列冲突，可设置合适的装填因子阈值，当达到这个阈值的时候，就触发动态扩容。
优化动态扩容
在进行动态扩容的时候，当数据量大、装载因子也大的时候，动态扩容搬迁和通过散列函数计算新的位置会非常耗时，使的整个插入操作耗时非常高。可采用如下方式优化：
- 在达到装填因子阈值时，我们只申请空间，不将老的数据搬移过去。
- 将新的数据插入到新的空间。
- 当之后来新的数据插入时，除了插入到新的空间之外，我们搬迁一个老的数据。
这样在多次的插入过程之后，老的数据就全部搬迁到新的空间了。这样处理动态扩容的时间复杂度为O(1)。