数据结构小记【Python/C++版】——散列表篇

一，基础概念

散列表，英文名是hash table，又叫哈希表。

散列表通常使用顺序表来存储集合元素，集合元素以一种很分散的分布方式存储在顺序表中。

散列表是一个键值对(key-item)的组合，由键(key)和元素值(item)组成。键和它对应的元素值基于散列函数(hash function)进行一对一的映射，基于键查找到的元素值也可以称为散列值，查找公式：item = hash(key)。其中item可以是具体的值，也可以是具体的值对应的内存地址，也可以是链表或者链表的指针。

注意，有的教程里面喜欢把键值对称为(key, item)，有的教程里面喜欢把键值对称为(index, value)，其实是相同的意思。

散列表和数组相似的地方在于，都可以基于下标快速的访问数据，数组的下标是索引，散列表的下标是键。

散列表结构在生活中的抽象模型：一个班级所有学生的姓名和对应的学号。

二，散列表的图示结构

图一，key -> hash function -> hash table（key, item）