哈希表-散列表数据结构-Toy模板网

这篇具有很好参考价值的文章主要介绍了哈希表-散列表数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

哈希表也叫散列表，哈希表是根据关键码值(key value)来直接访问的一种数据结构，也就是将关键码值(key value)通过一种映射关系映射到表中的一个位置来加快查找的速度，这种映射关系称之为哈希函数或者散列函数，存放记录的数组称之为哈希表。

哈希表采用的是一种转换思想，其中一个中要的概念是如何将「Key」转换成数组下标？

在哈希表中，这个过程有哈希函数来完成，但是并不是每个「Key」都需要通过哈希函数来将其转换成数组下标，有些「Key」可以直接作为数组的下标。

举例：

用哈希表来存放员工信息，我们可以利用员工号作为「Key」就可以直接作为数据的下标，不需要通过哈希函数进行转化。

如果我们用员工姓名作为「Key」，这时候我们就需要哈希函数来帮我们转换成数组的下标。

换句话说，哈希函数是帮我们把非int 的「Key」转化成 int，用来做数组的下标。

哈希表-散列表数据结构,C/C++,数据结构,散列表,哈希表

在 uthash 开源C代码中，哈希函数主要使用了以下几种：

哈希表-散列表数据结构,C/C++,数据结构,散列表,哈希表

详细可以参考 https://troydhanson.github.io/uthash/userguide.html

哈希表提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)，因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表，例如拼音检查器。

· 事先不需要排序。

· 搜寻速度与数据多少无关。

举例：

linux 跑起来的时候有很多进程，那有很多 task_struct 怎么连接呢？

linux里面有三种数据结构来连接task_struct , 链表（方便遍历的时候用），树（方便找父进程），哈希表（方便从pid 找到task_struct）。

uthash 是用宏实现的一个头文件，即可实现哈希表的一些列操作。

https://troydhanson.github.io/uthash/userguide.html#_a_hash_in_c

GitHub - troydhanson/uthash: C macros for hash tables and more

参考：

图文并茂详解数据结构之哈希表 - 知乎文章来源地址https://www.toymoban.com/news/detail-812998.html

到了这里，关于哈希表-散列表数据结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

哈希表-散列表数据结构