今天我们继续学习新的数据结构-散列表。
01 、定义
我们先来了解一些常见概念名词解释。
散列 ：散列表的实现叫做散列，是一种实现以常数级时间复杂度执行查找、插入和删除的技术；
散列值 ：通过散列函数对输入值（key）计算出来的结果，用来表示key的唯一性，它通常是一个长度固定的值，即无论key多大，散列值的长度都是固定的；
散列地址 ：通过散列值计算出来的存储位置，即存储value的位置，通常使用散列值和散列表的大小取模得到散列地址。
碰撞 ：也叫 冲突 ，指两个不同的key，经过散列函数计算后得到相同的散列值；
负载系数 ：也叫 负载因子 ，用来衡量散列表填充程度，通过散列表已存储的元素个数除以散列表的大小计算可得；
散列函数 ：也叫 哈希函数 ，指将key映射为散列值的函数；
散列表又称哈希表，是以「key-value」形式存储数据的数据结构。可以理解为任意的key都可以唯一对应到内存中的某个地址，而这个地址就存放着value，通过key快速查找到value。也可以把散列表理解为一种高级的数组，其中key就相当于数组下标，此数组下标不但可以是整数，还可以是浮点数、字符串、结构体等，其中value就相当于数组元素值。
通过前面的数据结构学习，我们知道数组是查找容易、插入和删除困难；链表是查找困难、插入和删除容易；而散列表是集两者之大成，做大查找、插入、删除都容易的一种数据结构。
本质上来说散列表就是一个数组。虽然上面把key比作数组下标，但是key并不真的是数组下标。因此这中间就需要一个转换工具把key转换为数组下标，而这个工具就是散列函数。
如下图，展示了在散列表中如何通用key获取到value的过程。输入key4通过散列函数计算得到数组索引3，最后通过数组下标取出value4。
标签：游戏攻略
