Grokking Hash Array Mapped Tries (HAMTs)
Previous to understanding HAMTs, you’ll want to know how hash tables and tries work. I already made a fundamental intro to hash tables which you’ll be able to entry right here:
A terrific introduction and overview of what tries are is supplied beneath:
A Hash Array Mapped Trie (HAMT) is a knowledge construction that mixes the advantages of hash tables and tries to effectively retailer and retrieve key-value pairs. It’s generally utilized in laptop science to implement associative arrays or dictionaries.
In a HAMT, keys are hashed to find out their storage location inside an array, known as a hash array. Every entry within the hash array can retailer a number of key-value pairs, permitting environment friendly reminiscence utilization. If a number of keys hash to the identical array index, a trie-like construction is used to resolve collisions.
Suppose now we have a HAMT that shops phrases and their corresponding definitions. For simplicity, we’ll use a easy hash desk that solely has 4 slots for storing values and which we index utilizing two bits.
As an instance we wish to retailer the next key-value pairs:
Initially, the HAMT is empty.
We begin by inserting the primary key-value pair, “apple” -> “a fruit”. The important thing “apple” is hashed, and the ensuing index within the hash array is decided. Let’s assume that the hash for “apple” consists of 32 bits, however we use the primary 2 bits to be able to discover the proper index in our desk. On this occasion, let’s assume that the primary 2 bits of our hash are 01. For the reason that array on the calculated index is empty, we retailer the key-value pair instantly in that place.
Subsequent, we insert “banana” -> “a tropical fruit”.
Once more, the bottom line is hashed, and the corresponding index is discovered within the hash array. Let’s assume that the computed hash worth for our key begins with 10. We will see that this index in our array is as soon as once more empty, so we as soon as once more retailer our price instantly inside the hash desk:
Lastly, we insert “cat” -> “a small animal”. The hot button is hashed, and the corresponding index is decided. Let’s assume that the primary 2 bits of the hashed worth for cat seems to as soon as once more be 01 (the identical worth that we used for apple). We now have a collision!!
Usually, when the hash desk will get large, we have to allocate a bigger and greater hash desk and recalculate all of our hash values. This generally is a gradual and costly course of! Is there any method that we will keep away from having to carry out this step?
As a substitute of performing a resize on our desk, we merely allocate a brand new hash desk (which additionally has 4 empty slots) and we hyperlink our collision slot (01) to level to this new desk:
Now, we will add “cat” to our second desk, however now we have a slight downside. We have to use extra bits to be able to get hold of our hash worth. On this occasion, we merely use the first 4 bits as a substitute of simply the first two (which we used for apple and banana).
Let’s assume that the primary 4 bits of our hashed worth for “cat” map to 0110. We already used the primary 2 bits (01) to attempt to index our price in our first hash-table. Now, we use the subsequent 2 bits (3rd and 4th bits → 10) to be able to index our aspect inside our 2nd hash desk:
The above methodology of hashing eliminates the necessity for us to do re-hashing. If we proceed like this, we will add as many values as we like without having to allocate extra reminiscence.
To discover a worth, we first merely calculate the hash. We then have a look at the bottom two bits and go to the foundation desk to attempt to discover our price. If a worth exists at that place and it matches our key, we return it. In any other case, we all know that that isn’t the worth we have been searching for so we proceed with the subsequent two bits and use these to discover a reference in our second desk and so forth and so forth.
On this method, the HAMTs effectively deal with collisions through the use of a trie-like construction inside the hash array. In essence, they’re a mix of a binary search tree and hash desk however with none of their annoyances. Binary search bushes require for us to stability the tree each time we insert one thing resulting from the truth that we wish to maintain our search-paths logarithmic and environment friendly. In an HAMT, the positions are decided by the hash, so the positions will likely be extra random and don’t require balancing. As for hash tables, we already talked about the annoyance of the needing to re-allocate extra reminiscence and to re-hash values in cases when our desk is full. An HAMT by no means will get full resulting from the truth that it is a tree. In cases the place we have to allocate a brand new worth, we simply proceed including extra youngster nodes.
HAMTs are often utilized in useful programming languages, reminiscent of Clojure and Scala to be able to implement persistent knowledge buildings like maps and units. HAMTs present environment friendly lookup, insertion, and deletion operations whereas making certain immutability. They’re additionally well-suited for concurrent environments the place a number of threads or processes entry and modify shared knowledge buildings concurrently. Their structural sharing property permits for environment friendly copying and sharing of knowledge, decreasing the necessity for costly locking mechanisms.
Please notice that this instance gives a simplified rationalization of HAMT’s working rules, and precise implementations might contain extra complicated optimizations and particulars.
You’ll be able to grok the opposite nuances and the varied optimizations which can be found inside HAMTs by studying the wonderful weblog put up linked beneath:
You may also discover a superb implementation of a HAMT within the repo supplied beneath: