跳至內容

自由表

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

自由表(英語:free list[1]是一種用來實現特定動態主記憶體分配方案的數據結構,也稱自由列表。自由表的核心原理是將若干未分配的主記憶體塊用鏈結串列連接起來,將未分配區域的第一個作為指向下一個未分配區域的指標使用。自由表非常適合用來實現主記憶體池,因為主記憶體池中對象的大小都是相同的。

用自由表實現主記憶體的分配和回收非常簡單:回收主記憶體時只需將主記憶體塊鏈入自由表;分配時也只需從自由表的一端取下即可直接使用。如果主記憶體塊的大小不一,則分配前還需要在自由表中搜尋足夠大的主記憶體塊,可能有一定的額外消耗。

因為自由表使用了鏈結串列結構,所以也繼承了它的劣勢:訪問局部性低下,難以利用快取

另見

參考資料

  1. ^ freelist - 自由表. 國家教育研究院雙語詞彙、學術名詞暨辭書資訊網. [2018-07-13]. (原始內容存檔於2018-09-10).