为什么C标准库中没有哈希表？

Question

为什么标准C库中没有Hashtable支持？这是有特定原因吗？

- Shankar Raju

---

这是增加 C 语言开发者就业的战略的一部分。 - Cheeso

如何进行版本控制：https://dev59.com/7m855IYBdhLWcg3wXTAI - Ciro Santilli OurBigBook.com

Answer 1

在今天的标准下，C语言似乎有些不寻常，因为它没有定义任何有用的数据结构。没有。甚至没有字符串——如果你认为C字符串是一种数据结构，那么我们对“数据结构”的理解就存在分歧。

如果你喜欢C语言，那么可以把它看作是一个“空白的画布”……你的整个应用程序都是由你编写的代码和你选择引入的库组成的，再加上一些相当原始的标准库函数，可能会有一两个像qsort这样的例外。如今人们使用C语言来实现诸如Python、Ruby、Apache或Linux内核之类的东西。这些项目都使用自己的数据结构，不太可能使用STL之类的东西。

许多C语言库实现了通用哈希表。有一些权衡，你可以选择自己喜欢的。其中一些可以使用回调进行配置。

• Glib有���个哈希表对象（文档）
• Apache Portable Runtime有一个哈希表（文档）
• 苹果的Core Foundation库有一个哈希表（文档）注意：是的，您可以将任何对象作为键或值插入。
• UTHash是一个哈希表库（文档）
• 另一个哈希表库（链接）

既然有这么多能够实现你想要的功能的库，那么将哈希表添加到C标准中的意义是什么呢？

- Dietrich Epp

---

嗯，我不确定是否同意"C字符串不是一种数据结构"这部分（虽然不足以点踩）-它们具有定义的结构和用于操作它们的函数。除了复杂性之外，我不确定这与B树或哈希表有什么不同。无论如何，我们还有 FILE * :-) - paxdiablo

+1 对于一个能够很好地回答“为什么”部分的答案。 - R.. GitHub STOP HELPING ICE

@paxdiablo：我考虑过提到FILE*...这是一个很好的观点。 - Dietrich Epp

我在此提议使用punchcard_t数据结构作为解决C语言字符串问题的最终方案。该数据结构应定义为typedef struct { char data [81]; } punchcard_t;，并应在stdpunchcard.h中定义。它将成为“从函数返回通用人类可理解的字符串”的解决方案。 - Dmytro

最佳答案。在这个级别上，没有必要创建标准哈希表库，因为你真正关心的是使用哪一个，所以你应该去查看一些开源库或编写自己的库。 - sudo

我喜欢 UTHash；如果你只是想快速实现某些功能，我会推荐它。它非常容易学习，并且可以在不创建大量对象的情况下工作。是的，作者完全滥用了宏来使其工作，但它足够小和简单，以至于我并不在意。 - sudo

Answer 2

标准C库中没有哈希表，因为：

• 没有人向工作组提交提案；或者
• 工作组认为它是不必要的。

这就是ISO的工作方式。提出提案，然后接受或拒绝。

你必须小心添加到标准库中的内容，因为你有两个相互冲突的群体。作为一个用户，你可能希望将所有可能用到的数据结构都添加到标准库中，以使语言更加有用。

但是，作为一名语言实现者（顺便说一下，这些人很可能占据了各种工作组的大部分组成人员，因此他们的观点可能会产生更大的影响），你不希望费劲地去实现可能不会被所有人使用的东西。当C89出现时，所有已经存在的内容都是为了规范现有做法，而不是引入新的做法。从那时起，所有标准的迭代都可以做得更自由一些，但向后兼容仍然是一个重要问题。

其实，我也有矛盾。我希望在C中能够利用Java、C++或Python库的所有功能。当然，这会让新手学习所有内容变得更加困难，而且正如一位评论者所说，可能会使任何代码猴子都能够编写有用的代码，从而降低我的价值 :-)

我几乎已经拥有我需要的所有数据结构，它们来自于我漫长而（大多数情况下）辉煌的职业生涯。对于此类东西，你并不局限于标准库。你可以获得许多第三方工具来完成工作，或者（像我一样）你也可以自己动手。

如果你想知道在每个迭代中为什么做出某些决策，ISO（最初是ANSI，后来被ISO接管）通常会发布理由文档。ANSI的C89文档可以在这里找到。其中的一个美妙之处在于作用域：

本理由主要关注对基础文档中所描述的语言进行的添加、澄清和更改。它不是C语言作为整体的理由：委员会的任务是将现有语言编码，而不是设计新语言。本理由没有试图捍卫语言的现有语法，例如声明的语法或运算符的绑定。

我特别喜欢他们承认他们不负责在标准化之前可能存在的混乱局面。

但是，也许你问题的真正答案在于这一点，这是其中一个指导原则：

---

保持C语言的精神。 委员会的主要目标是保留C语言的传统精神。 C语言的精神有许多方面，但本质上是一个社区对C语言基础原则的情感共鸣。 C语言精神的某些方面可以用以下短语总结：

• 相信程序员。
• 不要阻止程序员做必须做的事情。
• 保持语言小巧简单。
• 只提供一种操作方式。
• 使其快速，即使不能保证可移植性。

---

第三个原则可能是标准化努力未大规模扩展库的主要原因，这也是委员会可能会被标记为C2038而不是C89的原因之一。

- paxdiablo

---

保持语言简洁易懂，提供操作的唯一方法。您所谈论的是仍然使用C语言吗？例如：int或signed int、if-else或?:、if-else或switch、宏函数或函数、continue或break或goto或return;、const int或int const、typedef结构或结构、枚举或const或#define、malloc或calloc、NULL或0或'\0'、*(ptr+n)或ptr[n]等等。等等，这只是冰山一角，我可以继续讲上一整天。 - Lundin

此外，委员会确实做出了令人钦佩的努力，使语言变得毫无必要地复杂。你上次使用以下头文件是什么时候呢：complex.h、errno.h、fenv.h、float.h、inttypes.h、iso646.h、locale.h、signal.h、wctype.h？对我来说，一个包含哈希表的头文件大约比这些有用一百倍。 - Lundin

请看包含“被委托对一种_现有_的语言进行编码，而不是设计一种_新的_语言”的章节。大部分这些内容在ANSI标准之前就已经存在了。在这些头文件中，我通常使用errno、locale和signal，但我从未使用过其他任何头文件，不过话说回来，我并不是全球唯一的C语言程序员 :-) complex、fenv、inttypes、iso646和wctype等内容是后来出现的，与C89的原则无关。您需要查看特定版本的原始文档。 - paxdiablo

因此，如果C90委员会负责编码现有语言，那么人们可能会想知道C99委员会的任务是什么。“提出尽可能多的无意义新功能，同时避免对语言进行任何显着改进”，或类似的任务。显然，他们仍然每年会面几次，谈论过去的美好时光。 - Lundin

如果没有一个良好的复杂算术库，尝试编写用于设计或模拟电子元件的软件可能会很困难。 - evanflash

Answer 3

标准C库没有包含任何大型持久数据结构，包括列表、树、栈和哈希表。

如果没有询问原始C库的作者，很难给出确定的答案。然而，一个合理的解释是实现这种数据结构涉及各种权衡，只有应用程序的作者才能做出这些权衡。

请注意，POSIX标准C库确实指定了通用哈希表函数：hcreate()、hsearch()和hdestroy()；还要注意它们的“一刀切”性质往往使它们不适用于大多数实际用例，从而支持上述论点。

- caf

---

嗯，看起来 POSIX 哈希表只能一次创建一个哈希表。听起来非常有用。 - Dietrich Epp

在实际编码中，POSIX哈希表函数几乎没什么用处。 - R.. GitHub STOP HELPING ICE

请参考hcreate_r，该函数没有这个限制（但它是非POSIX扩展）。 - jjg

Answer 4

由于缺乏模板

这只是一个猜测，但是像C++这样的语言没有模板使得实现容器非常不优雅，因为您需要数十个定义来涵盖所有可能的类型，更不用说用户定义的类型了。

有一些C的策略可以缓解这种情况，比如玩弄void *，但它们会失去编译时的类型检查。

目前我推荐GLib和gnulib这两种实现：在C中实现字典的快速方法

- Ciro Santilli OurBigBook.com

---

为什么不像模板那样使用宏来生成代码呢？ - wingerse

@WingerSendon 或许这是可能的，我从未尝试过，但我有一种直觉，认为如果这是可能的话，生成的代码库会比模板更加疯狂 :-) 很高兴被证明是错误的。 - Ciro Santilli OurBigBook.com

C语言并非没有模板，只是那些不知道如何使用的人而已。看看openssl哈希表的实现，他们使用预处理器做得非常好。 - Yuri Nudelman

我以前用C语言做过基本的“模板”，只需使用#define TEMPLATE_TYPE int，然后跟着#include "templated_binary_tree.h"，每个需要支持的类型都要这样做。头文件在包含时使用任何存在的TEMPLATE_TYPE来创建适合该类型的函数。虽然不太美观，但可以让它正常工作 :-) - paxdiablo

正如我们的朋友Hendrix所说：“有了灵魂的力量，任何事情都是可能的！”@paxdiablo https://youtu.be/W-M16K6UlQg?t=297 XD - Ciro Santilli OurBigBook.com

如我们的朋友Hendrix所说：“凭借灵魂的力量，一切皆有可能！” XD - Ciro Santilli OurBigBook.com