Implementing Sets in Lua Using Tables and Metatables

March 26, 2026 · 16 min read ·Updated May 31, 2026 ·intermediate

setsdata-structurestableslua

Lua ships with tables — versatile structures that act as arrays, maps, or dictionaries depending on how you use them. What it does not ship with is a built-in Set type. Fortunately, tables are flexible enough that you can build one yourself in a few lines of idiomatic Lua. Implementing sets in Lua means taking advantage of hash-table lookups to deliver O(1) membership checks without external libraries. In this tutorial, you’ll build sets from scratch, learn the standard operations, avoid the common pairs() ordering trap, and cap it off with a read-only proxy pattern for cases where mutation just shouldn’t happen.

Prerequisites

You’ll need a working Lua 5.1+ interpreter — PUC Lua, LuaJIT, and Luau all handle table-backed sets identically. No external modules are required. You should understand basic table syntax: creating tables with {}, assigning values with bracket notation, and looping with pairs(). If you’re new to those concepts, read the tables introduction first.

What is a set?

A set is a collection of unique values where order doesn’t matter and membership is the primary operation. The classic question a set answers is: “Is X in this collection?” — answerable in constant time, not by scanning the whole thing.

In Lua, the convention is to use a table where keys are members and every value is true. This is sometimes called the “true sentinel” pattern.

local fruits = { apple = true, banana = true, cherry = true }

Why keys rather than values? If you stored members as values in an array-style table, a membership check would require scanning the whole table — O(n). By using keys, Lua’s hash table lookup gives you O(1) membership checks. The true value is just a convention; any truthy value works, but true is the clearest choice.

You can also build a set incrementally:

local primes = {}
primes[2] = true
primes[3] = true
primes[5] = true
primes[7] = true
-- primes is now the set {2, 3, 5, 7}

This is the foundation everything else in this tutorial builds on.

It’s worth understanding why the O(1) lookup matters in practice. When Lua resolves primes[7], it hashes the key 7 and jumps directly to the bucket where that key lives — no looping, no scanning. This is the same mechanism that makes table field access and global variable lookups fast across the entire language. Once you internalise the sentinel pattern, you’ll start spotting places where an array scan can be replaced with a table key check. The pattern scales cleanly: a set with ten thousand members still resolves membership in the same constant time as a set with three members.

Basic Operations

Once you understand the sentinel pattern, the basic operations fall out naturally.

Adding an element

set[key] = true

Because setting a key that already exists overwrites the value with true, adding an element to a set is idempotent — inserting the same value twice has no extra effect.

Idempotence is a useful property for set construction because it means you can throw values at a set from multiple sources without worrying about duplicates or side effects. The hash table handles the write in constant time regardless of whether the key was already present, so repeated insertions carry no performance penalty. This is especially helpful when you’re aggregating results from several computations and want the final collection to contain each distinct value exactly once.

Removing an element

set[key] = nil

Setting a key to nil deletes it from the table entirely. This is idiomatic Lua cleanup. There’s no remove method needed, no special API call — just assign nil.

This nil-as-deletion convention is one of Lua’s design strengths — the garbage collector automatically reclaims the memory occupied by the removed entry during its next collection cycle. Unlike languages where you must call an explicit delete method or free memory manually, Lua’s approach is both memory-safe and concise. The key simply ceases to exist for all subsequent lookups and iterations, as if it were never inserted in the first place.

Checking membership

if set[key] then
    print("key is in the set")
end

Since nil is falsy and true is truthy, a direct lookup works as a membership test. No comparison against a special value needed.

This design takes advantage of Lua’s truthiness rules: only nil and false are falsy; everything else — including 0, empty strings, and empty tables — evaluates as true. Because your set stores true as the sentinel value, the expression set[key] returns true for members and nil for non-members, aligning perfectly with the boolean semantics Lua’s if statement expects. There’s no risk of confusing a valid member with a falsey sentinel, which would be a problem if you used false as the marker value instead of true.

Here are those three operations wrapped in small helper functions to make your intent explicit:

local function add(set, key)
    set[key] = true
end

local function remove(set, key)
    set[key] = nil
end

local function contains(set, key)
    return set[key] ~= nil
end

local vowels = {}
add(vowels, "a")
add(vowels, "e")
add(vowels, "i")
add(vowels, "o")
add(vowels, "u")

print(contains(vowels, "a"))  --> true
print(contains(vowels, "z"))  --> false

remove(vowels, "e")
print(contains(vowels, "e"))  --> false

With the three core operations in place, you have everything needed to build higher-level set algebra. The helper functions are deliberately thin wrappers — they don’t validate input types or guard against nil tables because Lua’s convention is to let errors propagate naturally rather than paying for defensive checks on every call. If you pass a non-table value as the first argument, Lua will raise an error when it tries to index it, and the stack trace points directly at the offending call site. This lightweight style is idiomatic Lua: trust the caller, let the runtime catch mistakes, and keep the code free of defensive noise.

Set Operations

You’ll often need to combine or compare sets. The standard operations — union, intersection, difference, and subset check — are all implementable with a few lines of Lua.

Union — elements in either set (or both)

local function union(a, b)
    local result = {}
    for k in pairs(a) do result[k] = true end
    for k in pairs(b) do result[k] = true end
    return result
end

local set_a = { x = true, y = true }
local set_b = { y = true, z = true }
local set_u = union(set_a, set_b)
-- set_u = { x = true, y = true, z = true }

Intersection — elements in both sets

The union implementation above copies every key from both source tables into a fresh result table, producing a new set rather than mutating either input — the safer default for functional-style composition. Notice that the function iterates both sets unconditionally without checking which is larger. In performance-sensitive code where one set is significantly larger than the other, you might iterate the smaller set first to reduce the number of hash insertions into the result, but for most use cases the straightforward double-pass approach is fast enough.

local function intersection(a, b)
    local result = {}
    for k in pairs(a) do
        if b[k] then result[k] = true end
    end
    return result
end

local set_a = { x = true, y = true }
local set_b = { y = true, z = true }
local set_i = intersection(set_a, set_b)
-- set_i = { y = true }

Difference — elements in A but not in B

The intersection implementation uses a double-lookup pattern: it iterates over set a with pairs() and checks b[k] for each key. This runs in O(n) time where n is the size of set a, with each membership check in b costing O(1) thanks to the hash table. The result only ever grows to the size of the smaller input set, which makes intersection the most memory-efficient of the three set operations — in the worst case where the two sets share no elements, the result is an empty table.

local function difference(a, b)
    local result = {}
    for k in pairs(a) do
        if not b[k] then result[k] = true end
    end
    return result
end

local set_a = { x = true, y = true }
local set_b = { y = true, z = true }
local set_d = difference(set_a, set_b)
-- set_d = { x = true }

Subset check

The difference operation is directional: difference(A, B) returns elements in A that are not in B, but swapping the arguments gives you the complementary result. This asymmetry makes difference useful for tasks like detecting which items were removed between two snapshots of a collection, or filtering a candidate set against a blocklist. Like intersection, it iterates over exactly one input set — the first argument — and performs O(1) lookups into the second via the hash table.

local function is_subset(sub, super)
    for k in pairs(sub) do
        if not super[k] then return false end
    end
    return true
end

local small = { a = true, b = true }
local large = { a = true, b = true, c = true, d = true }
print(is_subset(small, large))  --> true
print(is_subset(large, small))  --> false

The subset check short-circuits: as soon as it finds a key in sub that is missing from super, it returns false immediately rather than continuing to scan. This means is_subset on a non-subset often finishes faster than a full scan. An empty set is always a subset of any set — the for loop never executes, and the function returns true. The implementation iterates over the smaller set (the candidate subset), which is the efficient choice since the loop body runs only once per potential member that must be verified.

All of these iterate with pairs(), which brings us to a critical gotcha.

Iteration with `pairs()`: the ordering trap

pairs() iterates over all key-value pairs in a table. For sets, the values are always true, so pairs() gives you the keys — which is what you want. The problem is iteration order.

local vowels = { a = true, e = true, i = true, o = true, u = true }

for letter in pairs(vowels) do
    print(letter)
end

This will print the vowels, but not in alphabetical order. The order is implementation-defined — it might be insertion order today, hash bucket order tomorrow, and different again in a different Lua version. You cannot rely on it.

If order matters for your use case, you need to sort explicitly:

local sorted = {}
for k in pairs(vowels) do table.insert(sorted, k) end
table.sort(sorted)
for _, v in ipairs(sorted) do print(v) end
-- a, e, i, o, u — guaranteed sorted

Note that ipairs() only works with sequential integer-keyed tables. It cannot iterate over a set’s string keys. Once you’ve sorted the keys into an array, ipairs() handles the ordered traversal correctly.

This is one of the most common sources of surprising behaviour when people first use tables-as-sets in Lua. The rule of thumb: if you need ordered output, sort before iterating.

Sets vs arrays: when to use which

Sets and arrays (which in Lua are just tables with sequential integer keys) serve different purposes. Here’s a quick decision guide:

Scenario	Best choice
Checking if a value exists	Set — O(1) lookup
Traversing values in insertion order	Array — `ipairs()`
Deduplicating a list of values	Set — keys are naturally unique
Collecting unique items	Set — inserting the same key twice is a no-op
Storing an ordered sequence	Array — integer keys preserve order
Fast edge lookup in a graph	Set per node
Tracking tags or flags	Set — `tags["urgent"] = true`

The telltale sign that you should switch from an array to a set: if you find yourself doing this:

-- Array with a manual linear scan for membership
local items = { "apple", "banana", "cherry" }
local function contains(arr, val)
    for _, v in ipairs(arr) do
        if v == val then return true end
    end
    return false
end

Replace it with a set and the lookup becomes a single hash access:

The performance difference is substantial as your collection grows. An O(n) linear scan through 10,000 items averages 5,000 comparisons per lookup, while the hash-based set lookup stays at one hash computation and one bucket access regardless of size. This is why sets are the right choice whenever your primary operation is membership testing — the constant-time guarantee holds even as your data scales, and Lua’s table implementation handles hash collisions internally so you never need to tune it yourself.

local items = { apple = true, banana = true, cherry = true }
if items["banana"] then
    -- O(1) — done
end

Read-only sets with metatables

Sometimes you want a set that’s fixed after creation — a constant set that nothing can modify. This is common when modelling things like operators, keyword sets in a lexer, or valid configuration values.

Lua’s metatable mechanism lets you create a proxy around a table that intercepts writes and throws an error.

local function readonly_set(source)
    local proxy = {}
    local mt = {
        __index = function(_, k) return source[k] end,
        __newindex = function(_, _, _)
            error("cannot modify a read-only set", 2)
        end
    }
    setmetatable(proxy, mt)
    return proxy
end

local operators = readonly_set({
    ["+"] = true, ["-"] = true,
    ["*"] = true, ["/"] = true
})

print(operators["+"])   --> true
print(operators["%"])   --> nil (not in the set)
operators["+"] = nil    --> error: cannot modify a read-only set
operators["^"] = true  --> error: cannot modify a read-only set

Here’s how it works:

__index forwards any read to the underlying source table, so the proxy behaves exactly like the original set.
__newindex fires whenever code tries to assign to any key — including proxy["+"] = nil. It throws an error with a two-level stack trace (2) so the error points to the caller’s line, not the metamethod itself.
The source table lives in the closure and is never exposed directly, so there’s no way for external code to bypass the proxy.

One thing to be aware of: if any other code holds a direct reference to the underlying source table, it can still modify it. The proxy only guards access through the proxy itself. Keep the source table private.

The practical payoff for this pattern is clean, safe constant sets:

local KEYWORDS = readonly_set({
    ["and"] = true, ["break"] = true, ["do"] = true,
    ["else"] = true, ["elseif"] = true, ["end"] = true,
    ["false"] = true, ["for"] = true, ["function"] = true,
    ["if"] = true, ["in"] = true, ["local"] = true,
    ["nil"] = true, ["not"] = true, ["or"] = true,
    ["repeat"] = true, ["return"] = true, ["then"] = true,
    ["true"] = true, ["until"] = true, ["while"] = true
})

local function is_keyword(word)
    return KEYWORDS[word] ~= nil
end

This is the pattern you’ll see in lexers and parsers across the Lua ecosystem.

Practical Examples

Let’s look at three scenarios where sets genuinely earn their keep.

Deduplication

If you receive a list of values and need only the unique ones:

The deduplication approach uses a two-phase strategy: first, build a set by iterating over the input list, then extract the unique keys back into a sorted array for ordered output. Because set keys are naturally unique, the first phase produces exactly one entry per distinct value — duplicate insertions are silently absorbed, as each unique[v] = true simply overwrites the same true value. The table.sort call on the output array is optional but valuable when the consuming code expects deterministic ordering of the unique results.

local input = { "apple", "banana", "apple", "cherry", "banana", "apple" }

local unique = {}
for _, v in ipairs(input) do
    unique[v] = true
end

local result = {}
for k in pairs(unique) do
    table.insert(result, k)
end
table.sort(result)

for _, v in ipairs(result) do
    print(v)
end
-- apple, banana, cherry (sorted, deduplicated)

Token classification in a lexer

When parsing text, you often need to quickly decide whether a character is a valid operator:

Lexers are a natural fit for sets because they perform thousands of membership checks per second during parsing. Using a read-only operator set means the classification table stays constant throughout the parse — no accidental mutation can introduce bugs mid-stream. The tokenize_operator function demonstrates a common two-character lookahead pattern: first try matching a two-character operator like == or <=, then fall back to a single-character operator, and finally return nil if neither matches. This greedy two-then-one approach handles multi-character operators correctly without backtracking.

local operators = readonly_set({
    ["+"] = true, ["-"] = true, ["*"] = true, ["/"] = true,
    ["="] = true, ["<"] = true, [">"] = true,
    ["=="] = true, ["~="] = true, ["<="] = true, [">="] = true
})

local function tokenize_operator(chars, i)
    local two = chars[i] .. (chars[i + 1] or "")
    if operators[two] then
        return two, i + 2
    end
    local one = chars[i]
    if operators[one] then
        return one, i + 1
    end
    return nil, i
end

-- Test it
print(tokenize_operator({"=", "="}, 1))  --> ==  3
print(tokenize_operator({"+"}, 1))        --> +   2
print(tokenize_operator({"x"}, 1))        --> nil 1

Graph node neighbours

In a graph represented as adjacency lists, storing each node’s neighbours in a set gives fast edge existence checks:

The adjacency-set representation is a space-time tradeoff: it uses more memory than a simple list of neighbour nodes, but it makes the edge-existence query O(1) instead of O(degree). For dense graphs or algorithms that repeatedly check edge existence — like triangle counting or cycle detection — this constant-time lookup pays for itself. The double-index pattern graph[from] and graph[from][to] safely handles missing nodes by short-circuiting on the first nil, avoiding the error you’d get from indexing a nil value directly.

local graph = {
    A = { B = true, C = true },
    B = { A = true, D = true },
    C = { A = true, D = true },
    D = { B = true, C = true }
}

local function has_edge(from, to)
    return graph[from] and graph[from][to] == true
end

print(has_edge("A", "B"))  --> true
print(has_edge("A", "D"))  --> false

Summary

Sets in Lua are tables used in a specific way: keys are members, values are true. This simple convention gives you O(1) membership testing, idiomatic nil-based deletion, and a clean foundation for implementing union, intersection, difference, and subset operations.

The key takeaways:

Use set[key] = true to add, set[key] = nil to remove, and if set[key] to check membership.
pairs() iteration order is not guaranteed — sort keys explicitly if order matters.
Reach for a set whenever you’re doing repeated membership checks on a collection.
Use a metatable proxy when you need an immutable set.

If you’re building data structures in Lua, you’ll also find it useful to understand how hash maps work in Lua — since that’s what your sets are built on — and how arrays and lists handle ordered data that sets deliberately don’t care about.

Next steps

Sets are a fundamental building block. Once you’re comfortable with table-backed membership checks, explore linked lists for ordered sequential data and stacks and queues for LIFO and FIFO patterns — both complement sets in real Lua programs.