Re:Hash Array Mapped Tries (HAMT) to the Rescue
by riwsky on Monday September 07, 2020 @04:57PM
(#24402792)
It is not clear from the article that the author needed a persistent data structure.
It’s also, frankly, not clear they‘d benefit from using an HAMT at all: the only measurements they present are of their problem domain, not of any implementations—and many of the asymptotics they cite are also true of hashmaps.
If their initial hashmap approach did have O(N) inserts because they copied the whole map for “immutability” every time, then sure, HAMTs will beat the pants off of it—but did it?
It’s also, frankly, not clear they‘d benefit from using an HAMT at all: the only measurements they present are of their problem domain, not of any implementations—and many of the asymptotics they cite are also true of hashmaps.
If their initial hashmap approach did have O(N) inserts because they copied the whole map for “immutability” every time, then sure, HAMTs will beat the pants off of it—but did it?