[Lua] 程式設計教學：實作雜湊表 (Hash Table) 和集合 (Set)

雜湊表 (Hash Table)

由於 Lua 的表 (table) 內部即是雜湊表 (hash table)，另外再以表重新模擬雜湊表的意義不大；請各位讀者自列參考本系列文章有關表的章節即可。

集合 (Set)

集合是指數學上有關集合論 (set theory) 的概念；理論上，很多資料結構都可以用來實作集合，若考量效率，使用雜湊表 (hash table) 或樹 (tree) 來實作較佳；由於 Lua 的表即為雜湊表，會比另外實作樹好一些。通常筆者會將集合包成物件，因為集合論一些基本的操作，包括聯集、交集、差集等，若直接操作表會過於瑣碎。

由於程式碼略長，我們在這裡展示完整程式碼，讀者可自行前往閱讀。我們接著會分段展示相關程式碼。

首先，撰寫建構函式。此處我們撰寫兩種建構函式，一種建立空集合，一種從表中初始化集合：

function Set:new()
    self = {}
    self._set = {}
    setmetatable(self, Set)
    return self
end

function Set:fromData(data)
    local s = self:new()

    for _, e in ipairs(data) do
        s:add(e)
    end

    return s
end

由於集合儲存不重覆的元素，我們內部不儲存元素數量，僅儲存元素存在的狀態：

function Set:add(e)
    self._set[e] = true
end

利用表可以快速檢查元素是否存在：

function Set:contains(e)
    return self._set[e] == true
end

利用表也可以快速移除元素：

function Set:remove(e)
    if self._set[e] == true then
        self._set[e] = nil
    end
end

在檢查集合是否相等時，我們利用運算子重載簡化公開介面：

Set.__eq = function (a, b)
    for e in a:iter() do
        if not b:contains(e) then
            return false
        end
    end

    for e in b:iter() do
        if not a:contains(e) then
            return false
        end
    end

    return true
end

我們用先前提到的迭代器的手法走訪集合：

function Set:iter()
    local out = {}

    for k, _ in pairs(self._set) do
        table.insert(out, k)
    end

    local n = 0

    return function ()
        n = n + 1

        if n <= #out then
            return out[n]
        else
            return nil
        end
    end
end

我們將聯合 (union) 運算包在物件中，簡化外部公開介面：

Set.union = function (a, b)
    local out = Set:new()

    for e in a:iter() do
        out:add(e)
    end

    for e in b:iter() do
        out:add(e)
    end

    return out
end

有關交集 (intersection) 和差集 (difference) 的部分可自行觀看我們所附的連結。