algorithm - 使用哪种数据结构

Question

我的系统的本地驱动器(例如:c、d、e)中有数百万个文件。现在要搜索文件，我们可以使用 Windows 的内置工具或 linux 中的“查找”等命令。如果我想设计我自己的“查找”程序，它应该首先扫描所有目录并将信息存储在某个文件或数据库中。现在每当我想搜索一个文件时，我们首先需要从数据库或文件中加载信息，然后进行搜索。

我需要建议来决定使用哪个数据结构来存储目录结构，然后可以加载目录结构并查询给定的文件名。

由于搜索是基于文件名的，所以我想到了使用 Hashmap，其中键是文件名，值是完整路径。使用 Trie 会使搜索变慢。另一个想法是使用倒排索引。但不确定哪个更好。

谢谢。

Answer 1

哈希表对此非常有用，因为它的查找(以及插入和删除)时间复杂度为 O(1)。但问题是您不能使用哈希表进行“范围搜索”。 “范围搜索”类似于“查找所有以扩展名 cpp 结尾的文件”。如果这对您来说不是问题，那么我建议实现哈希表。