操作系统 目录实现

有许多算法可以实现目录。然而，选择适当的目录实现算法可能会显著影响系统的性能。

目录实现算法根据它们使用的数据结构进行分类。目前主要使用两种算法。

1. 线性列表

在此算法中，目录中的所有文件都被维护为单链表。每个文件都包含指向分配给它的数据块和目录中下一个文件的指针。

特点

1. 创建新文件时，必须检查整个列表，以确定新文件名是否与现有文件名匹配。如果不存在，则文件可以创建在开头或结尾。因此，寻找唯一名字是一个重要问题，因为遍历整个列表需要时间。
2. 在文件的每个操作（创建、删除、更新等）中，都需要遍历列表，因此系统变得低效。

2. 哈希表

为了克服目录的单链表实现的缺点，有一种另外的方法是使用哈希表。这种方法建议将哈希表与链表一起使用。

对于目录中的每个文件，都会生成一个键值对并存储在哈希表中。可以通过对文件名应用哈希函数来确定键，而键指向存储在目录中的对应文件。

现在，由于现在只需要检查哈希表条目而不是在每次操作中搜索整个列表，所以搜索变得更高效。使用键检查哈希表条目，如果找到条目，则使用值获取相应的文件。