In which case would you use a hashtable and which case would you use an array?
1 Like
What? I don’t understand what you mean here. Can you be more clear?
5 Likes
local assets = {}
table.insert(assets, item)
or
assets[item] = true
3 Likes
if you’d like to index something directly without having to try to find it with loops, use the latter. other than that, moreso personal preference.
2 Likes
Arrays are useful if you want to have a list of things where you don’t need any specific thing from that list. Dictionaries (or “hash tables”) are useful where you need to get specific pieces of information from a table. When you would use them is purely contextual because they’re both dynamic and useful in their own respects.
3 Likes
To extend this response:
Arrays are particularly useful when order is important.
Maps/Dictionaries/Hashtables do not have a defined order, however if you are grabbing specific elements from the table by key, these methods would work better just like @Dekkonot mentioned.
8 Likes
A case in which you could use dictionaries to their advantage to achieve O(1) time (takes the same time to execute regardless of the input’s size) would be awarding users admin:
Array - O(n)
local playersService = game:GetService("Players")
local adminIds = {1234567890, 0987654321, 123, 1337}
playersService.PlayerAdded:Connect(function(player)
local userId = player.UserId
local isAdmin = false
for _, adminId in ipairs(adminIds) do
if userId == adminId then
isAdmin = true
end
end
if not isAdmin then return end
giveAdmin(player)
end)
Dictionary - O(1)
local playersService = game:GetService("Players")
local adminIds = {
1234567890 = true,
0987654321 = true,
123 = true,
1337 = true,
}
playersService.PlayerAdded:Connect(function(player)
if not adminIds[player.UserId] then return end
giveAdmin(player)
end)
The latter also has the advantage of being much more readable and easy to understand at a glance.
3 Likes
It really depends on the situation.
If I want to check if something is in the Dictionary really quick
local Dictionary = {['John'] = true}
print(Dictionary['John'])
instead of iterating through all of it’s content
I would use an Array to keep a list of items in a specific order and when it has to be iterated though all of it’s content
I would use a MixedTable for checking of something is in it really quick and also keeping it in a specific order.
Keep in mind that MixedTable (& MetaTables) are somewhat annoying to deal with while handling it cross Server - Client boundaries with Remote & Bindable Instances because of their limitations but there is a work around
Overall Tables are very useful
I recommend against using mixed tables. As well as the issues you mentioned, it is troublesome to iterate over them. Simply use two separate tables, each either an array or dictionary style.
I don’t see it as a problem, I can either extract the Mixtable into an Array and a Dictionary then send both to the Client or Server then recombine them that solves the issue I mentioned, or simply use a module.
and their’s no problem with iterating over them
local MixedTable = {
['John'] = true,
'John'
}
print(MixedTable['John'])
for i = 1, #MixedTable do
local v = MixedTable[i] -- Stuff in Array
local vv = MixedTable[v] -- Stuff in Dictionary
end
I like to keep things simple and in one place so I prefer this
The only real troublesome issue is you can’t save it to DataStore.
EDIT: Was recently made aware that this post is inaccurate. Lua’s hashing means that maps are not O(n) but not quite O(1) either.
An array is O(1). Looking up an individual item from a true Lua array is instant. A Lua dictionary is O(n). Indexing a Lua hashmap/dictionary internally iterates over its contents, which means it has to check most elements often times.
What you’re referring to is manual iteration, but lookup speed is generally a lot faster for arrays in Lua. Lua tables are internally represented with both a dictionary and array part. When something is within the array part, it’s often simply retrieved by having a single size check and an indexing of a C array.
8 Likes
Yes, I’m referring to the manual iteration over an array compared to a hash table lookup.
This is new to me - is there any reason that Lua does not use the standard key > hash function > bucket model, or am I missing something?
Lua dictionaries are not magic; just like the standard map or standard unordered map, even if it’s bucketted it’ll still need to iterate and check for the value you need. Arrays, on the other hand, are a single size check and offset.
1 Like
With my current understanding, hash maps are only O(n) in their worst case scenario, caused by collisions. Are you referring to iterating over the result of a collision? If not, where does the iterating come into play?
1 Like
Dictionaries (speaking generally, not just Lua’s impl) can not store contiguous random access memory based on their keys. This explanation gets a big technical because this is all handled on the lower level end.
A real array, in practice, is a line of memory of a single memory type. The reason access is O(1) for a C array is because there is no lookup involved. You have an index and that gets translated to an offset. Roughly speaking, if you had an array of integers you would internally index it like this.
arrayMemAddress + index * sizeof(int)
Because you know both the size of the type and index number beforehand, you can calculate where in memory your item is.
A hashmap or dictionary on the other hand, can’t do the same. Even if you hash the indexes into integers, you might end up with really large numbers, and you can’t really have an array big enough to cover all those cases. So what do we do? Store key value pairs in memory. Whether you hash bucket it or not you still need to iterate over the bucket list (if it’s solely hash based) and the contents of the bucket (if there is a collision for the first hashing). You also can’t have a lot of buckets if you’re aiming for memory efficiency. Bucketting also often gives up map ordering.
It’s a bunch of different tradeoffs. Lua tables are a combination of both an actual array and its own dictionary implementation.
4 Likes