在链表结构中,我们相当于把所有的空闲块连接到了一起,是一条线,但是现在我们试图维护几个桶,把大小相似的块都丢进同一个桶中,维护多个空闲链表,其中每个链表中的块有大致相等的大小,比如说,将大小为 1-2 的空闲块放一起,大小为 3 的空闲块放一起…

如果我们想找一个空间块大小为7 的块,那我们会怎么办?我们又不需要把所有的空闲块的给遍历一遍,刚开始我们是遍历所有的块,然后再优化还是遍历所有的空闲块,现在我们直接去对应的桶(大小类)中寻找,只需要找到大小为 58 空闲块的这个链表,我们去遍历它
大小类
将所有可能的块大小分成一些等价类,也叫做大小类(size class)。有很多种方式来定义大小类。例如,我们可以根据 2 的幕来划分块大小:
或者我们可以将小的块分派到它们自己的大小类里,而将大块按照 2 的幂分类:
分配器
维护着一个空闲链表数组,每个大小类一个空闲链表,按照大小的升序排列。当分配器需要一个大小为 n 的块时,它就搜索相应的空闲链表。如果不能找到合适的块与之匹配,它就搜索下一个链表,以此类推。
有关动态内存分配的文献描述了几十种分离存储方法,主要的区别在于它们如何定义大小类,何时进行合并,何时向操作系统请求额外的堆内存,是否允许分割,等等。为了使你大致了解有哪些可能性,我们会描述两种基本的方法:简单分离存储(simple segregated storage)和 分离适配(segregated fit)