Bitmap hash tries: copy paths for immutable alert maps

Last updated: 4 Oct 20269 min read

tutorial

A hash-array mapped trie selects a child from successive chunks of a key's hash. This bounded model uses two four-bit chunks from an eight-bit integer digest. Each branch stores a bitmap of present slots and a dense tuple of children. Counting the set bits below a slot yields its tuple index. A leaf holds the original key and value, so lookup checks key equality rather than trusting a hash alone. Equal digests from distinct IDs end in a collision tuple. Updating a key allocates new tuples only along its route; unchanged subtrees remain shared by earlier roots. The map is immutable at its public boundary: set returns a new map instead of changing the old one. Its tiny deterministic digest makes collisions easy to demonstrate, not suitable for hostile inputs or a general-purpose hash table.

Operational case

Alert IDs 47 and 303 have the same low eight bits. They occupy a collision node, yet each retrieves its own state because the terminal scan compares full IDs. Revision one stores 47 as open and 303 as review. Revision two changes only 47 to closed. Looking through revision one still returns open, while revision two returns closed and preserves the 303 value. A stored value of None is still a legitimate value because absence raises a KeyError; the lookup does not use None as a missing sentinel. Branch tuples hold only occupied slots, but Python tuple and integer overhead are not a measured compact-memory result.

Working Python program

class PersistentAlertMap:
    def __init__(self, root=None):
        self.root = root

    @staticmethod
    def _hash(alert_id):
        if not isinstance(alert_id, int) or alert_id < 0:
            raise ValueError("alert ID must be a nonnegative integer")
        return alert_id & 255

    @classmethod
    def _assoc(cls, node, alert_id, state, digest, shift):
        if node is None:
            return ("leaf", alert_id, state, digest)
        kind = node[0]
        if kind == "leaf":
            if node[1] == alert_id:
                return ("leaf", alert_id, state, digest)
            if shift == 8:
                return ("collision", ((node[1], node[2]), (alert_id, state)))
            branch = cls._assoc(None, node[1], node[2], node[3], shift)
            return cls._assoc(("branch", 1 << ((node[3] >> shift) & 15), (branch,)),
                              alert_id, state, digest, shift)
        if kind == "collision":
            pairs = dict(node[1])
            pairs[alert_id] = state
            return ("collision", tuple(sorted(pairs.items())))
        bitmap, children = node[1], node[2]
        slot = (digest >> shift) & 15
        bit = 1 << slot
        index = (bitmap & (bit - 1)).bit_count()
        if bitmap & bit:
            updated = list(children)
            updated[index] = cls._assoc(children[index], alert_id, state, digest, shift + 4)
            return ("branch", bitmap, tuple(updated))
        updated = list(children)
        updated.insert(index, ("leaf", alert_id, state, digest))
        return ("branch", bitmap | bit, tuple(updated))

    def set(self, alert_id, state):
        digest = self._hash(alert_id)
        return PersistentAlertMap(self._assoc(self.root, alert_id, state, digest, 0))

    def get(self, alert_id):
        digest = self._hash(alert_id)
        node = self.root
        shift = 0
        while node is not None:
            kind = node[0]
            if kind == "leaf":
                if node[1] == alert_id:
                    return node[2]
                raise KeyError(alert_id)
            if kind == "collision":
                for stored_id, state in node[1]:
                    if stored_id == alert_id:
                        return state
                raise KeyError(alert_id)
            slot = (digest >> shift) & 15
            bit = 1 << slot
            if not node[1] & bit:
                raise KeyError(alert_id)
            index = (node[1] & (bit - 1)).bit_count()
            node = node[2][index]
            shift += 4
        raise KeyError(alert_id)


revision_zero = PersistentAlertMap()
revision_one = revision_zero.set(47, "open").set(303, "review")
revision_two = revision_one.set(47, "closed")
print("old=", revision_one.get(47), " new=", revision_two.get(47),
      " collision=", revision_two.get(303), sep="")

Output

old=open new=closed collision=review

Time, space, and tradeoff

There are at most two branch levels in this eight-bit model. A branch insertion copies at most sixteen child references per level, and a collision node may copy and sort K key-value pairs, costing O(K log K). Lookup costs O(D + K) in the worst collision path for D hash chunks; here D is two. A new revision shares unaffected branches and adds O(D times 16 + K) references in the worst update. Keeping V revisions can retain old nodes and values until those roots are released. A larger fixed-width digest increases depth but does not remove adversarial collision risk without a suitable hash policy.

Common Mistakes

Do not equate equal digests with equal keys.
Do not mutate a shared child tuple after issuing an old revision.
Do not claim constant-time lookup when an entire collision bucket must be scanned.
Do not call this eight-bit teaching digest resistant to chosen-key attacks.

Connected lessons

Compare lookup and update behavior with Ternary search trees: branch by character and continue prefixes, Binary radix routing: choose the longest matching prefix, Extendible hashing: split buckets through a shared directory, then run the index audit and contract quiz.

Persistent radix vectors: copy one indexed path per revision adds a related structure with a different operation boundary.

Reduced ordered decision diagrams: share identical rule branches adds a related structure with a different operation boundary.

Zero-suppressed diagrams: share sparse dispatch set families adds a related structure with a different operation boundary.

data structures

range-query-structures