1
A
回答
1
是,哈希表!所以你有一个大的散列表,其中包含空闲块的大小作为键,值是数组,指向相应大小的块。所以,每次释放一个块:
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)插入和删除。
相关问题
- 1. 编辑另一个可变长度列表中的可变长度列表
- 2. Codeigniter可变长度参数列表
- 3. 可变长度参数列表
- 4. 可变长度模板参数列表?
- 5. 使用printf的可变长度空间
- 6. 如何访问R中列表中的可变长度列表
- 7. 转换可变长度列表分成边列表的igraphř
- 8. 传递变量的可变长度的参数列表在PHP
- 9. fscanf()/ sscanf() - 匹配可变长度空格?
- 10. 可变长度的静态阵列
- 11. SQL中的可变长度int列
- 12. 连续,固定长度的可变长度序列批次
- 13. 可变蜱长度
- 14. Tensorflow可变长度
- 15. Power Query - 按可变字段长度拆分列 - 占空值
- 16. SilverStripe 3.1:将列表划分为垂直列(可变长度)
- 17. 含有重新排列可变长度
- 18. 未知长度的可变参数列表的问题
- 19. 可变长度的String.Format
- 20. PhysicalAddress的可变长度
- 21. 可变长度的NVARCHAR?
- 22. 可变长度的子串
- 23. 创建ctypes的可变长度ARG列表
- 24. 传递可变长度的参数列表AngularJS指令
- 25. 功能的可变长度参数列表
- 26. 带有可变长度输出的列表理解
- 27. 如何存储列表的长度为可变
- 28. 带有多个可变长度元素的Python列表理解?
- 29. Erlang函数参数列表的可变长度
- 30. 在MATLAB中创建可变长度数组的列表
有很多不同的选择,从基本的,但简单的代码,线性表,因为你已经提到的,它由一系列平衡树的散列桶来隔离不同大小的分配,这是一个“清单”要正确编写代码相当困难,并且其中还有许多其他选项。这一切都取决于你需要什么,你愿意花费多少工作来获得它 - 编程中的一个常见主题...... – twalberg
@twalberg用例大致是这样的:我有一个图,其中每个节点(和边缘)可以具有与它们中的每一个相关联的任意数量的键值对。我需要将这些文件存储在一个文件中,这样我可以a)根据节点+密钥对O(1)值进行访问,b)有一种方法可以知道与节点相关的所有密钥。所以对于a)哈希表将很好地工作,但它不允许b)。因此我需要以某种方式以不同的方式存储它。 – Resurrection