18.散列表上（Hash Table）

数组的一种拓展，利用数组支持按照下标随机访问数据的特性。通过散列函数把元素键值映射为下标，将数据存储在数组中对应下标的位置。

key --hash function--> table

【散列函数设计要求】

• 计算得到的散列值是非负整数
• key1=key2，then hash（key1）==hash（key2）
• key1！=key2，then hash（key1）！=hash（key2）

【散列冲突】

开放寻址法（open addressing）

线性探测（Linear Probing）存储位置被占用时，从当前位置开始依次往后寻找

hash（key）+0，hash（key）+1，hash（key）+2……（步长为1）

二次探测（Quadratic probing）

hash（key）+0，hash（key）+1^{2，hash（key）+2}2……（步长为二次方）

双重散列（Double hashing）

再用一个散列函数直到找到空闲的存储位置

装载因子（load factor表示空位多少）=填入表中的元素个数/散列表长度
装载因子大=空闲位置少=冲突多性能下降

链表法（chaining）

桶(bucket)/槽(slot)对应一条链表，散列值相同的元素放到相同槽位对应的链表
时间复杂度与链表长度k成正比O(k)