散列思想

散列表==>Hash Table==>哈希表==>Hash 表
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表
键(关键字）key===>散列函数（哈希函数）===> 散列值（Hash值）
散列表利用数组随机访问时间复杂度为O(1)的特性。
通过散列函数的键值映射为下标
读取的时候，通过散列函数转化键值为下标，从数组对应位置读取数据

散列函数

如何构造散列函数？三个要求

散列函数计算得到的散列值是一个非负整数
如果key1 = key2,那hash(key1) == hash(key2)
如果key1 != key2,那hash(key1) != hash(key2)

前两个要求容易达到，第三个要求几乎不可能，著名的hash算法MD5\SHA\CRC等哈希算法也无法避免散列冲突

散列冲突

散列冲突无法避免，怎么解决？

开放寻址法

核心思想 如果出现散列冲突，就重新探测一个空闲位置，将其插入，如何探测（线性探测），从当前位置依次往后查找，直到找的空闲位置
数据结构与算法---散列表
查找的过程中，通过散列函数映射key到下标，对比下标中的key是否和查找的key相同，不同就依次往下找，直到找到一个空闲位置，还没找到就说明该元素不在散列表中
删除操作，不能直接把要删除的元素设置为空，不然线性探测方法会失效，可以将删除的元素标记为deleted
数据结构与算法---散列表
存在问题当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。
还有两种经典的探测方法二次探测（探测的步长变为原来的二次方），双重散列（使用多个散列函数，当地一个散列函数位置被占领，使用第二个散列函数）