刚接触哈希的时候, 哈希表(hash table)、哈希(hashing)、哈希函数(hash function)、哈希算法(hashing algorithm)、字典(dictionary)、键(key)、值(value)、索引(index)、哈希码(hash code)、哈希值(hash value)这些名词总是在脑海里成为一团麻, 但又太过基础, 没有人清晰地帮我们辨析. 别担心! 本文将一一为你解答.
首先让我们回顾一下数据结构的概念.
我们都知道抽象数据类型(Abstract Data Type, ADT), 是指一种面对用户的纯理论的数学模型, 不涉及具体的实现. 而数据结构(data structure)则包含了实现ADT的具体数据及其方法. 举例来说, 堆栈是一种抽象数据类型,当我们定义了它是一个拥有push和pop接口的一个数据集合时. 而我们在具体实现时, 选择了array或者linked list这些数据结构.
在哈希表这个主题下, 字典(dictionary)/关联数组(associative array)/映射(map)是哈希表(hash table)的抽象数据类型. 因此, 当我们在说键(key)和值(value)的时候, 我们是在dictionary这个上层概念的范围内描述的. 对于用户来说, 他只关心如何用字典来存放他的数据, 而无需关心下层的hash table是怎么实现的. 举例来说, 假设有一个人想要存储一群人的信息, 他可以选择使用字典来存放, 将每个人的姓名作为key, 而将生日、国籍、职业这些信息作为value. 通过字典, 便可以轻松操作这群人的信息. 但这个人并不知道, 他所方便使用的字典的下层, 其实是一个哈希表在服务这个字典.
哈希表是什么? 首先, 哈希表中的数据是存放在一个数组(array)当中的, 这个数据拥有索引(index). 而这个index也被我们称为哈希码(hash code)或哈希值(hash value). 其次, 哈希表如何帮助实现字典中通过key获取value这样的方法的呢? 答案就是哈希! 哈希(hashing)是指使用哈希函数获得数组的索引(或者说获得哈希值)的过程. 其中,哈希函数(hash function)的输入是用户的key, 输出是数组的index, 或者说是hash code. 用数学符号表示就是 index = h(key). 其中h代表hash function. 当获得数组的index, 我们便可以访问数组中存放的对应的value. 总结来说, 哈希函数的计算和通过索引访问数组数据, 这两步的时间复杂度都是常数, 因而使用哈希表访问数据的时间复杂度为常数. 而哈希算法(hashing algorithm)就是哈希函数的别称.
总结, 在哈希这个话题下:
用户能看到的只有键(key)和值(value).
一些同义而不同名的专业名词总结如下:
索引(index)==哈希值(hash value)==哈希码(hash code)
哈希函数(hash function)==哈希算法(hashing algorithm)
希望对大家有所帮助! 有什么问题请在评论区提出:)