Bijective Dictionary in Swift

During a recent project, I encountered a situation where the standard Dictionary collection from the standard library could not offer the performance characteristics I needed.

The task involved performing address translation for a program interfacing with hardware: given a logical address, the program needed to find its corresponding physical address to communicate with the hardware. Later, once the hardware responds, the program must perform a reverse lookup to find the logical address corresponding to the physical address.

In the initial implementation, I used a standard dictionary. Since Dictionary offers efficient key-value lookups in O(1) time using an underlying hash table, the forward translation step was simple and efficient:

let addressTable = [
    1: 4,
    2: 3,
    3: 2,
    // Additional entries...
]

let logical = 2
guard let physical = addressTable[logical] else { return }

print("\(logical) → \(physical)") // Prints "2 → 3"

let addressTable = [
    1: 4,
    2: 3,
    3: 2,
    // Additional entries...
]

let logical = 2
guard let physical = addressTable[logical] else { return }

print("\(logical) → \(physical)") // Prints "2 → 3"

However, to perform the reverse lookup, I had to iterate over the dictionary’s values to find the correct entry, which runs in O(n) time in the worst case:

let original = addressTable.values
    .first(where: { $0.value == physical })!.key

print("\(original) ← \(physical)") // Prints "2 ← 3"

let original = addressTable.values
    .first(where: { $0.value == physical })!.key

print("\(original) ← \(physical)") // Prints "2 ← 3"

During testing, I discovered this inefficient reverse lookup resulted in observable, real-world performance issues. The address table could become quite large, and lookups (and corresponding reverse lookups) could reach rates exceeding one thousand times per second. Reducing the table size or lookup frequency was not possible due to project requirements; a more efficient reverse lookup was needed.

My solution involved maintaining two dictionaries: one for forward lookups and another for reverse lookups. This meant the reverse lookup dictionary was keyed by physical addresses, allowing the reverse lookup to also run in O(1) time. This solution required double memory usage since all keys and values are stored twice. However, this was an acceptable tradeoff for this application.

After testing verified this solution did indeed fix the performance issues, I encapsulated it in a data structure called BijectiveDictionary, allowing this solution to be reused in other applications with the same performance requirements.

Bijective dictionary closely mirrors the standard dictionary type from the standard library, sharing many of the same initializers, methods, and properties. The key difference in the public API is that a bijective dictionary’s keys and values are referred to as “left values” and “right values” respectively, to avoid confusion, since either can be used to access the other. The example from above can be rewritten using a bijective dictionary as follows:

let addressTable: BijectiveDictionary = [
    1: 4,
    2: 3,
    3: 2,
    // Additional entries...
]

let logical = 2
guard let physical = addressTable[left: logical] else { return }
print("\(logical) → \(physical)") // Prints "2 → 3"

let original = addressTable[right: physical]!
print("\(original) ← \(physical)") // Prints "2 ← 3"

let addressTable: BijectiveDictionary = [
    1: 4,
    2: 3,
    3: 2,
    // Additional entries...
]

let logical = 2
guard let physical = addressTable[left: logical] else { return }
print("\(logical) → \(physical)") // Prints "2 → 3"

let original = addressTable[right: physical]!
print("\(original) ← \(physical)") // Prints "2 ← 3"

This rewrite only involves two small changes:

• Annotate addressTable with BijectiveDictionary—the generic parameters Left and Right will both be inferred as Int from context.
• Use the left and right subscripts for lookups.

The source code for the BijectiveDictionary package is available on GitHub and up-to-date documentation is viewable on the Swift Package Index.