Garry's Mod Wiki

Home / History for Tables - Hashmap Usage

Revision Difference

List-Styled_Tables#561928

<cat>Dev.Lua</cat> <title>Tables - Value Indexed Lists</title>⤶ ## What is a List? ⤶ ⤶ Value-indexed tables are a commonly-neglected technique in Lua:⤶ ⤶ ```⤶ local tbl = { [1] = "a", [2] = "b", [3] = "c" } -- this is a normal sequential table. ⤶ -- Checking if a value is in a normal table:⤶ function table.HasValue( tbl, value ) -- O(n) worst-case complexity⤶ for _, v in ipairs( tbl ) do⤶ if v == value then⤶ return true⤶ end⤶ end⤶ ⤶ return false⤶ <title>Tables - Hashmap Usage</title>⤶ ⤶ # Replacing Arrays with Hashmaps⤶ ⤶ In Lua, a table is, at its core, composed of two components.⤶ 1. An array (otherwise referred to as a list or sequential table)⤶ 2. A hashmap (otherwise referred to as a dictionary) ⤶ An array is a linear sequence of elements, so:⤶ ```lua⤶ local array = {"A", "B", "C"}⤶ ```⤶ ⤶ As you can see were purely defining elements and letting the language determine the keys for us. This is useful in situations where you dont have a necessarily deterministic way of retrieving this data. If for instance we wanted to find the player named `"Jeff"` in the following array declaration.⤶ ⤶ ```lua⤶ ---⤶ --- Table contains a linear array of more tables⤶ ---⤶ local array = {⤶ --- Player index 1, since its the first in the table⤶ {⤶ "Goober" --- Name⤶ 21, --- Money⤶ },⤶ ⤶ --- Player index 2, and so on⤶ {⤶ "Pedro",⤶ 42,⤶ },⤶ ⤶ {⤶ "Jeff",⤶ 32,⤶ },⤶ ⤶ {⤶ "Nyaaa",⤶ 2442242424⤶ }⤶ }⤶ ```⤶ ⤶ We could do the following:⤶ ⤶ ```lua⤶ for k, v in pairs(array) do⤶ if v[1] != "Jeff" then⤶ continue -- If their name; first key, is not Jeff, then skip to the next loop iteration⤶ end⤶ ⤶ print("Jeff has $" .. v[2] .. "! Jeff has a player index of " .. k)⤶ end ⤶ local list = { ["a"] = true, ["b"] = true, ["c"] = true } -- this is a value-indexed version of that table.⤶ ⤶ --Checking if a value is in a value-indexed table:⤶ function ListHasValue( tbl, value ) -- O(1) worst-case complexity⤶ return tbl[ value ]⤶ ```⤶ ⤶ But this seems a little sloggish, doesn't it? Why do we have to iterate over every single person in `array` to just find one! Although this may be performant, and work just fine in most cases, why is there not an easier way?... well there is! This is where we get into hashmaps!⤶ ⤶ Imagine this being structured a little differently, where instead of the player index being tied to where/when it was defined in the table, it is the name!⤶ ⤶ ```lua⤶ local hash = {⤶ --- Name = Money⤶ Goober = 21,⤶ Pedro, = 42,⤶ Jeff, = 32,⤶ Nyaaa, = 2442242424,⤶ }⤶ ```⤶ ⤶ This may seem like a benign change considering you can treat this nearly identically to the old solution to finding the player, but this opens up an entirely new way!⤶ ⤶ ```lua⤶ print("Jeff has $" .. hash["Jeff"] .. "!")⤶ ```⤶ ⤶ No need for iteration, makes life substantially better considering you now can find values without the need for a function to return them, or a temporary variable to set the found player too after iteration.⤶ ⤶ # Notes⤶ ⤶ ## Dots vs Brackets⤶ As you read above, we did `hash["Jeff"]` to retrieve Jeff from the table, but everywhere in the API when you get something from a table you do `vgui.Create`, not `vgui["Create"]`... Right? Well they're the same thing, the only difference is the syntax and one has a magic power. That power is allowing you to use an "Expression" (a piece of code that returns something) to index instead of a constant value, so.⤶ ⤶ ```lua⤶ local function GetCreate()⤶ return "Create"⤶ end ⤶ local pnl = vgui[GetCreate()]("DPanel")⤶ ``` ⤶ We'll call them Lists, for short. They're incredibly useful! The idea is that by using the actual value we intend to store in the table as the key itself, we can retrieve and remove it from the table much easier and faster. This has many uses:⤶ ⤶ * Good for when the order of data saved is unimportant and each value is unique within the table.⤶ * Creating a table in which the same value can't exist more than once. * Rapidly checking whether a value is stored in a table without the use of iteration (seen above).⤶ ⤶ ## Two-Dimensional Lists ⤶ ⤶ We can take it one step further with 2D Lists:⤶ ⤶ ```⤶ -- A 2D sequential table holding players' friends as {guy=player, friends={their friends}}⤶ local friendTbl = {⤶ {⤶ guy = Entity(1),⤶ friends = {⤶ Entity(2),⤶ Entity(3)⤶ }⤶ },⤶ {⤶ guy = Entity(2),⤶ friends = {⤶ Entity(1)⤶ }⤶ },⤶ {⤶ guy = Entity(3),⤶ friends = {⤶ Entity(1)⤶ }⤶ }⤶ }⤶ ⤶ function TwoPlayersAreFriends( ply1, ply2 )⤶ for _, v in ipairs( friendTbl ) do⤶ if v.guy == ply1 then⤶ for _, friend in ipairs( v.friends ) do⤶ if friend == ply2 then⤶ return true⤶ end⤶ end⤶ ⤶ return false⤶ end⤶ end⤶ ⤶ return false⤶ ⤶ Yes, in this case, it is useless; however, this is extremely powerful, probably the most powerful thing about hashmaps entirely. Allowing you to dynamically index values makes it so you can use user input to find a value, get a player by its internal values you can only know at runtime, ect. You couldnt do the following could you?⤶ ⤶ ```lua⤶ local function GetCreate() return "Create"⤶ end ⤶ --And this is a 2D list which holds the same data as above. local friendList = {⤶ [Entity(1)] = { Entity(2) = true⤶ Entity(3) = true⤶ },⤶ [Entity(2)] = { Entity(1) = true⤶ }, [Entity(3)] = { Entity(1) = true⤶ }⤶ ⤶ local pnl = vgui.GetCreate()("DPanel") ```⤶ ⤶ It doesnt make sense! ⤶ ## ipairs⤶ The <page>Global.ipairs</page> iterator function is used the exact same way as <page>Global.pairs<page/>, except <page>Global.ipairs</page> only iterates through sequential keys. Meaning, if it runs across `nil` in the sequential portion of a table, it will stop iterating.⤶ ⤶ ```lua⤶ local array = { [1] = "A",⤶ [2] = "B", -- [3] = nil, [4] = "D"⤶ } ⤶ --Checking if a value is in a value-indexed table:⤶ function TwoPlayersAreFriends( ply1, ply2 ) return friendList[ ply1 ][ ply2 ]⤶ ⤶ for k, v in ipairs(array) do⤶ print(v) end ``` ⤶ Look at how much faster and simpler that is! If you wanted to, you could even replace `true` in the list with some kind of data. This makes the list into a dictionary.⤶ ⤶ So remember: **Any time you need to save distinct data in an unordered table, opt to use a List instead!**⤶ ⤶ This would output `A B`, not `A B D`, because it encountered `nil` on key `3`. The workaround for this is⤶ 1. Using <page>Global.pairs</page>, which iterates over **everything** not `nil`, without stopping.⤶ 2. Not allowing `nil` in the sequential table to begin with. Try <page>table.remove</page>⤶

Account Management

Special Pages

Wiki List