这是本次数据结构学习的最后一篇博客。

散列

还是按照之前的学习思路，来学习本次内容。
为什么需要创造“散列”这个ADT？
散列的结构与特点？
散列的种类？
散列的应用？

为什么创造“散列”这个ADT

散列的价值在于散列查询的速度，通过其定义可窥知一二：散列是一种用以常数平均时间执行插入、删除、和查找的技术。

散列的结构与特点？

基本思想：以关键字key为自变量，通过一个确定的函数 h（散列函数），计算出对应的函数值hash码，作为数据对象的存储地址。
但是随之而来会出现不同的key对应同一个hash码，于是出现冲突，即h(keyi) = h(keyj)（当keyi ≠keyj），称为“冲突(Collision)”。

散列的种类

由于在 创建散列函数、处理冲突 有不同方法，于是作以下分类：
散列函数：
是一个将关键字和散列地址对应的函数。
散列函数一般要考虑的两个因素：
（1）计算简单以便提高转换速度。（2）关键词对应的地址分布均匀，尽量减少冲突。
种类：
直接定址法、除留余数法、数字分析法… 等等
冲突解决办法：
开放地址法：思想是 当利用hash函数插入某个元素发生地址冲突时，就按照某种规则去寻找另一个地址
通用公式:
若发生第i次冲突，则 hi(Key) = ( h(key) + di ）mod TableSize 其中（i=1，2，…，TableSize）
根据di的不同，可以将开放地址法分为
线性探测： di = i
平方探测： di = i^2
双散列探测法：di = i * h2(key)
分离链接法：思想是 将相同位置上冲突的关键词存储在同一个单链表中

具体实现在这里不做说明

散列的应用

暂且不写