检查文件是否在C中唯一的好方法

Question

我正在编写一个C程序，用于计算给定目录中文件的总大小。我知道每个文件都指向一个inode，因此我打算使用stat来查找inode值和文件大小。由于我想避免错误的计算，当有多个硬连接和/或sym连接到一个inode时，我想将inode存储在一个数组中。问题是，现在要检查inode对于给定文件是否是唯一的，我将不得不遍历inode数组，给出大约n^2的运行时间。我想避免过度复杂的结构，如RB树。有没有更快，更聪明的方式来实现这一点？我知道有这样的系统工具，我想知道他们是如何实现这样的。

Answer 1

即使二叉树是一个不错的选择，因为根据随机数据他们是相对平衡。这也是一个非常简单的实施结构。

通常，选择的结构是具有恒定平均搜索时间的散列表。这里面临的挑战是为您的数据找到一个好的散列函数。散列表的实现并不困难，我想你可以找到很多好的库来实现它们。

但是，如果你愿意等待，直到你存储在阵列中的所有inode，那么你可以排序这个数组，为了找到重复遍历它..

编辑：

Inode包含一个引用计数。这将计算硬链接的数量。因此，您可以检查参考计数> 1的inode中的重复项。

Answer 2

使用散列表。这是O（1）（虽然对于小套来说有点贵）。当然，你可能会发现这个“过于复杂”，正如你对红黑树所说的那样，但是如果你想要好的最坏情况的表现，你需要做一些比普通数组更复杂的东西（顺便说一下尽管理论上的时间复杂性更差，但是对于小集合来说最快）

如果没有一个已有（这是C毕竟）哈希表的实现呢，有几个在这里的概述：https://stackoverflow.com/a/8470745/4323