可变长度的空闲列表

的free list的概念通常用于重新使用空间，所以如果我有一个完整的固定长度值的文件，我删除一个，我把它放在一个空闲列表上。然后当我需要插入新的价值时，我从列表中拿出一个并放在那个位置上。可变长度的空闲列表

不过我有点困惑，如何实现是可变长度值的空闲列表。如果我删除了这个值，并且我把这个位置和它的长度放在了空闲列表中，我该如何检索新值的“最佳”候选者？

使用普通名单将O(n)时间复杂度。使用树（长度作为关键）将使该log(n)。有什么更好的，会给O(1)？

2016-07-15 Resurrection

有很多不同的选择，从基本的，但简单的代码，线性表，因为你已经提到的，它由一系列平衡树的散列桶来隔离不同大小的分配，这是一个“清单”要正确编写代码相当困难，并且其中还有许多其他选项。这一切都取决于你需要什么，你愿意花费多少工作来获得它 - 编程中的一个常见主题...... – twalberg

@twalberg用例大致是这样的：我有一个图，其中每个节点（和边缘）可以具有与它们中的每一个相关联的任意数量的键值对。我需要将这些文件存储在一个文件中，这样我可以a）根据节点+密钥对O（1）值进行访问，b）有一种方法可以知道与节点相关的所有密钥。所以对于a）哈希表将很好地工作，但它不允许b）。因此我需要以某种方式以不同的方式存储它。 – Resurrection

是，哈希表！所以你有一个大的散列表，其中包含空闲块的大小作为键，值是数组，指向相应大小的块。所以，每次释放一个块：

hash[block.size()].append(block.address())

而且每次分配空闲块：

block = hash[requested_size].pop()

这种方法的问题是有太多的可能的块大小。因此散列会填满数百万个密钥，浪费大量内存。

因此，你可以有一个列表，并遍历它找到一个合适的块：

for block in blocks: 
    if block.size() >= requested_size: 
     return blocks.remove(block)

内存使用效率，但是缓慢的，因为你可能有过百万块进行扫描。

所以你要做的就是结合这两种方法。如果将分配量设置为64，那么包含256个大小类的散列可以用于最大64 * 256 = 16 kb的所有分配。大于您存储在树中的块，该树会给您O（日志N）插入和删除。

来源

2016-10-23 16:16:04

可变长度的空闲列表

回答

相关问题