Why You Should Love Hash Array Mapped Tries

[00:02] some point they will be blessed with encountering a data structure that is so wonderful so beautiful so aesthetically pleasing that they can't help but fall in love with it this has happened to me twice and I wish to introduce to you one

[00:17] of my most beloved data structures the hash array mat try or hamat however witnessing the Hammer with an unprepared mind would overwhelm it so I'm going to

[00:30] explain some lesser data structures so you will be ready to observe full wonder of the hamat all of these data structures that I talk about solves the structures that I talk about solves the problem of looking up a value via a key

[00:45] we call the data structures that allow us to do this a lookup table or an index and with the information that is being stored are called records this is an

[00:57] extremely common thing that a computer needs to do most of the time solving this problem is already done for us these are handled by libraries or built-in functionality of the computer language that you're using I could tell

[01:12] you that knowing about how these things operates will allow you to know which library is best to use and make you a better programmer but that is bogus I am telling you this because these things have a captivating abstract Wonder to

[01:28] them and I need to share my joy with you the simplest way to implement a lookup table is to write key value pairs in memory one after the other whenever we

[01:40] memory one after the other whenever we want to look up a record we simply check each key until we find the correct one however this is ugly and bad on average every time we want to look up a record we are going to have to search through

[01:54] half of the keys to find it this also has horrendous scaling problem if we double the number of Records we have we also double the number of steps we have to do to find our record for anything other

[02:08] than a tiny number of Records this search is going to be too slow to be useful if we look at a graph of time taken versus the number of Records it forms a straight line things with this type of scaling operate in what we call

[02:25] linear time this solution to a lookup table is called linear search after it's horrendous performance we can do a lot better than that if our keys are an

[02:37] unbroken sequence of counting numbers starting from zero and going up then we can store the records according to their key we put record zero in the zeroth key we put record zero in the zeroth spot record one in the next slot

[02:52] Etc then it is a simple matter of multiplying Key by the size of the record and adding the memory location of the zeroth record allowing us to jump directly to the record we are interested in this means that the lookup takes the

[03:07] same amount of time no matter how many records there are this type of scaling is called constant time scaling and is the best possible scaling we can get for lookups this structure is called an array but it has downsides if our index

[03:24] has gaps in it then such a system would be very wasteful we could end up with a situation where the array would be larger than the amount of memory that we have in the computer but it would mostly be empty sometimes if our key range is

[03:39] be empty sometimes if our key range is small and our records have gaps in it we small and our records have gaps in it we can use a modification of an array first as a part of our index structure we set aside a section of memory as a map of

[03:53] our data structure a map made of bits a bitmap in this bitmap each bit bitmap in this bitmap each bit corresponds to a possible key so if our bitmap is a 16-bit number the least significant bit will correspond to the

[04:08] key value of zero and the most significant bit will correspond to the significant bit will correspond to the key value of 15. if the record with the corresponding key is present the bits value will be set to 1 and if it's

[04:20] absent the bit value will be set to zero you can know which record is present by checking if the bitmap value is set and we can work out the memory location of

[04:32] we can work out the memory location of the record by counting all the bits set to the right of this this tells you how many records you'll need to skip over to many records you'll need to skip over to find your needed record bit counting is

[04:46] required for certain code breaking techniques and a certain U.S government techniques and a certain U.S government agency has required this feature as a built-in operation all the computers that it buys course of this bit counting

[05:02] is supported as an assembly command in most CPUs and gpus this is the bitmapped sparse array the bitmap sparse array is a good solution if we have less than

[05:16] about 64 Keys more than that all of our clever bit trickery won't work as well clever bit trickery won't work as well however since there are so many big gaps there is a way to make use of that you could allocate a region of space in

[05:30] memory and if a key goes out of that range just have it wrapped back on itself if we are lucky then all of the records will fall into the gaps if we are unlucky we could end up with records being allocated to the same place a

[05:45] problem that is called a collision we can mitigate a collision by having the colliding element be placed in the next memory slot afterwards then you would basically do a linear search once you've jumped to near the right place there is

[06:02] other rooms for improvement as well wrapping the key around corresponds to the modulus or remainder function however it is not a good function for

[06:14] this role if 2 if you have to have two keys key separated by a multiple of the size of the memory they would Collide so what we really want is a function that ensures that records are scattered evenly over the allocated space the

[06:30] functions that are good at reducing Keys down to our limiter range are called hash functions and we call this type of structure a hash table hash functions

[06:42] have some great advantages they can take a key of any size and convert it down to a constant size so we can use any string as a key rather than it having to be a number most of the time a hash table has a constant lookup time

[06:59] a hash table has a constant lookup time like an array however there are a few unpleasant downsides if a hash table has a lot of collisions or is almost full then the behavior Can degrade to being as bad as a linear search if our hash

[07:16] table becomes full and we wish to expand it the size of the hash table is a part of the calculation that dictates where the item gets stored so when we expand

[07:28] the item gets stored so when we expand the space we have to move everything out the space we have to move everything out around to new places because of how long around to new places because of how long a hash table takes to store and retrieve

[07:41] a hash table takes to store and retrieve records is dependent on what the keys records is dependent on what the keys are in the hash table it is possible to determine what keys are present in the hash table by using carefully

[07:55] constructed keys this allows information to be leaked from a hash structure and can present privacy and cyber security issues if we wish to list everything in

[08:10] a hash table the order that the items come out in is going to be random what is even worse is if you do something while stepping through the items that causes the hash table to grow or Shrink in size The Ordering of the elements

[08:26] inside the hash table are going to change you might end up hitting the same element twice or missing elements in that case that being said for many applications hash tables are the best lookup structures however the downside

[08:42] lookup structures however the downside means we should also look at other structures that may be better we can take the records and store them in order of their keys now when you are searching for a record you can start in the middle

[08:57] then you can compare the keys if the record is below your target key then you can eliminate half of the records and you don't need to search them the same if the record key is above your target now you can treat the smaller range just

[09:12] like you treated the larger range go to the middle compare the keys you keep doing this until you reach the record that you are looking for because at each point you are making a decision that cuts the problem into halves this is

[09:27] called a binary search a sorted list with a binary search is very efficient and has great scaling properties if you double the number of Records you only have to add one more step the graph of its speed is logarithmic however it has

[09:44] some downsides you have to sort the records which is okay if you have to do it once and you're doing many searches afterwards but if you are doing many inserts you have to sort and move around all the records every time you do an

[10:00] insert however the records don't have to be in the order that they are in physical memory for the binary search algorithm to work all the computer needs to know is which record to jump to when things are lower or

[10:17] higher we could add to the record the memory location to go to if the target key is smaller and the memory location to go to if the target key is larger

[10:29] these memory location records that point to the next record are called pointers diagramming the memory like this is kind of hard to follow and since the physical of hard to follow and since the physical location in memory no longer matters how

[10:43] about we just look at the structure abstractly because the structure branches off from itself computer scientists call this a tree the place where everything starts is called the root and computer scientists normally

[10:57] draw a tree with the root at the top of the page and the branch is going down because they spend too much time indoors and don't know what trees actually look like each point where branches split off is called a node and the nodes that are

[11:12] linked below a particular node are called that node's children likewise the node above is called that node's parent because these type of trees have two children they called binary trees if there is any hint of anything to Schnitz

[11:32] Peter related is get the word binary prefix to it if a binary tree is totally balanced this tree would have the same speeds as a sorted list and have equally

[11:46] fast times for inserting new records however if we are not careful when constructing our tree it could become imbalanced and we could end up with a situation where the tree is just as slow as a linear search there are a great

[12:02] number of variants and adjustments to the binary tree which solve this issue of imbalance by creating ways of detecting and correcting the imbalance some with more branches per node are more efficient with the memory cache red

[12:18] more efficient with the memory cache red black trees B trees and the like are all fascinating topics which I'm not going to cover in this video however we've gotten to the point where I can introduce my love to you for

[12:32] simplicity's sake I am going to describe to you the 16-bit implementation of the hash array mapped try but typically implementations use 32 or 64 bits in The

[12:47] 16-bit implementation of the hammat the key use is a 16-bit integer if we want to use a larger key or something that is not an integer then we would use a hash

[13:01] not an integer then we would use a hash to reduce that value down to a 16-bit integer for convenience we will be thinking of this 16-bit integer as a four digit HEX number in the ham at each node has 16 children when we start from

[13:18] node has 16 children when we start from the root node or records whose Keys end with zero will be under the zeroth node all records whose Keys end with a 1 will all records whose Keys end with a 1 will be under the next child and so on on the

[13:33] next layer down the nodes will be split based on the second rightmost digit again splitting them into 16 groups again for the third and at the fourth

[13:45] layer the links will go to the records with this structure we can find any with this structure we can find any record with only four steps but its current form is a bit wasteful we have a lot of nodes and most of them won't even

[14:01] lead to stored records however we don't have to allocate nodes that don't have records below them we can make use of the trick we talked about before with

[14:13] the bitmap sparse array so each node of the hamat would look like this to find an item in this structure on the topmost Node we look at the least four bits we

[14:26] Node we look at the least four bits we then look up the nth bit of the bit map if it is zero then we know the thing we are looking for isn't in the structure if it is one then we can count the number of bits to the right and Skip

[14:40] number of bits to the right and Skip forward to the nth item and jump to the address there we can then use the second last four bits and repeat this action we can do this four times and get to the stored value no matter how much data is

[14:55] stored in our system it takes a constant time to look something up if the key is ordered then we can iterate through the values in an ordered fashion it is also possible to implement this as an append only structure where we add new data on

[15:13] top rather than modifying the previous values in place doing this makes implementing concurrency and transactions very clean it is so elegant and effective how could you not love such a wonderful data structure and if

[15:31] you love this data structure just as much as I do okay that's impossible if you love this data structure even a little bit even a little bit please share your love by subscribing to

[15:44] please share your love by subscribing to this channel