How does a Roblox Dictionary work?
I recently decided to explore "Dictionaries", and have found them to be extremely useful. Dictionaries are like arrays, but with key-value pairs. You call the dictionaryname[key], and it gives you to value. Way easier than setting up a for loop for an array to find an item.
I was wondering: When you do something like "dictName[key]", what is that doing? Is it running a method with a hidden for loop, or does it directly find the key/value if they exist?
Thanks!
1
2 answers
Interesting question!
I did some research, and here's what I got from this documentation report and this source code for Lua tables.
Tables in Lua (and thus, RBX.Lua too!) have two parts to them, which are hidden from us at our level: a hash part, and an array part. Elements in the table that have integer keys are stored internally in the array part, while elements with strings or other objects for keys are stored in the hash table.
What do those mean?
Arrays
You may have heard of these before, but Lua "arrays" are not the same as arrays in other programming languages. Arrays have elements stored in order, and their indices are implicitly defined (i.e. based on where they are in relation to the first element) like cat, dog, bird, rather than stored like 1 = cat, 2 = dog, 3 = bird, etc.. If you define this table:
local t = {"cat", "dog", "bird"}
or this one:
local t = {[1] = "cat", [2] = "dog", [3] = "bird"}
, all of those elements are stored internally as an array.
Hash Tables
...But you didn't ask about arrays, you asked about dictionaries. If you made this table:
local t = {cat = "fluffy", dog = "groomed", bird = "flappy"}
internally, Lua's going to store that as a hash table. This is a great video explaining what a hash table is. Basically though, you have a function Hash that returns a unique number for every element you give it, and will always give you that same number.
So if you say Hash("doodilydo") and get the number 124 out of it, you will always get the number 124 for Hash("doodilydo"). A hash table is a big array with a lot of slots in it, and you would put "doodilydo" in slot 124.
Then, when you later want to find "doodilydo" you can just look at the index in hash_table given by Hash("doodilydo"). Repeat for all the non-integer-indices in a Lua Table, and you have the internal storage of dictionaries.
tl;dr: No, no for loop is taking place. dictName[key] runs the hash function on key and returns the element at that index in the hash table.
disclaimer: I am not an expert on this and it is likely to be wrong on several accounts, but it's probably a decent approximation.
0
0
According to some of Lua's source code their table implementation is that of a hash table, also commonly called hash map. I'll try to explain them a bit but you can likely find better information about them elsewhere.
Hash tables are multidimensional arrays. Each key that is used in a hash table go through a hash function, which return a byte or number equivalent of the key that determine where the pair are stored. Let's say our hash function only returns 4 unique values to keep this simple. This will make our arrays look like:
arrays = {
[0] = {};
[1] = {};
[2] = {};
[3] = {};
}
If we put 100 pairs into this hash table then each underlying array would hold about 25 pairs each (unlikely to be equally divided due to pseudo random hashing). To get a value given a key from this you first calculate the hash of the key and then iterate over the inner array associated with it until you find the matching key. This makes it so you only compare about 1/4 of the original 100.
In my experience Lua tables are very fast with fetching a value from a given key. Due to how hash tables work, getting a value from a 1M element table won't be much different from 10 elements.
0
0