散列表（Hash Table）中的散列函数和散列冲突解决

散列表的英文叫“Hash Table”，平时也叫它“哈希表”或“Hash表”。散列表是用数组支持按照下标随机访问数据的特性。

将键（key）转化为数组下标的映射方法就叫作散列函数，而散列函数计算得到的值就叫作散列值。

散列函数

定义为hash（key），其中key表示元素的键值，hash（key）的值表示经过散列函数计算得到的散列值。

散列函数设计的基本要求：

    1 散列函数计算得到的散列值是一个非负整数。

    2 如果key1 = key2，那hash( key1 ) == hash( key2 )。

    3 如果key1 ≠ key2，那hash( key1 ) ≠ hash( key2 )。

散列冲突

在真实情况下要想找到一个不同的key对应的散列值都不一样的散列函数，几乎是不可能的，无法完全避免散列冲突，常用的散列冲突的解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

1 开放寻址法

核心思想：如果出现了散列冲突，就重新探测一个空闲位置，将其插入。

探测方法：线性探测（Linear probing）、二次探测（Quadratic probing）、双重探测（Double hashing）

    1）线性探测：往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到位置。

        hash(key)+0，hash(key)+1，hash(key)+2 ……

    2）二次探测：每次探测的步长变成原来的二次方。

        hash(key)+0，hash(key)+1^2 ，hash(key)+2^2 ……

    3）双重探测：使用一组散列函数，依次使用散列函数，直到找到空闲的存储位置。

        hash1(key)，hash2(key)，hash3(key) ……

为了尽可能保证散列表的操作效率，一般会尽可能保证散列表中有一定比例的空闲槽位，用装载因子来表示空位的多少。装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

2 链表法

在散列表中，每个桶或者槽会对应一条链表，通过散列函数计算出对应的散列槽位，所有散列值相同的元素都放到相同槽位对应的链表中。