What type of search algorithm is used when indexing a table?

Help and Feedback Scripting Support
#1

Hello, I recently learned about Data Structures from freeCodeCamp, there I learned about all the various types that a table can be and how keys/indexes could be searched efficiently by analyzing the table through BigO notation or time complexity equation. So that got me wondering what type of search algorithm is used when calling a key/index from a table

Sorry if I don’t know, it’s just Lua or Luau is the first programming language I have written code in before I ever took any computer science courses.

Is linear search being use when doing…

local foo = {1,2,3,4,5,6,7,8}
local i = foo[5]
-- which is equal to this function
local i = function(index)
   for i,v in ipairs(foo) do
      if i == index then
         return v
      end
   end
end

That means it starts from the top of the table and goes down until it finds the 5th index.

or like in Binary Search finds the middle index of the table and checks if its the 5th index if not, it checks if 5 is above the middle index if true remove half of the table to be scanned and focus on the part that has the 5.

local foo = {1,2,3,4,5,6,7,8}
local i = foo[5]
-- is equal to
foo = {1,2,3,4,5,6,7,8} -- 4 is the middle index, 5 is above 4
foo = {4,5,6,7,8} -- Removes indexes that doesn't have 5, foo{1,2,3} removed.
foo = {4,5,6} -- foo{6,7,8} doesn't have 5.
foo = 5 -- index 5 is in the middle

Imagine foo had 119 Million indexes. Now imagine the name of foo is replaced with RobloxUsers.

#2

I am no expert in lua, so I cannot tell you what exactly happens behind the scenes throughout internal processes. However, I can perhaps give you the basic idea.

Arrays are actually dictionaries with ascending numbers as keys. The difference between a single key in array and dictionary is that array indexes may only be positive integers.

Which means:

-- Array structure:
local array = {
    [1] = "pencil";
}
-- Dictionary structure:
local dictionary = {
    ["item_1"] = "pencil"
}

You already mentioned linear search. It is a way of searching for an element (value) of an array that is used by table.find(). Its equivalent operation is looping through the whole table until value we are looking for is found. Best case scenario, also marked as O(1), is when element is the first in line. Conversly, worst case scenario, respectively O(n), is the slowest possible, because element is last in line.

When tables are small in size, linear search is extremely fast. However, if they contain millions or billions of elements, seaching may take seconds or even minutes. The numbers vary across different languages (lua is pretty fast, but python, for example, is much slower).

Dictionaries are saved differently: so called hashing is involved. Keys, which may be unordered numbers or strings, are hashed - they are transformed into integers in the background, such as:

local t = {}
t["apple"] = true --[[ >>]] apple - 1 --[[ >> ]] t[1] = true

Sort of a map is created. Each element (apple in above example) is assigned some sort of coordinates inside a table. There is also kind of a map legend present. When we search for apple, algorithm can return the value immediately, because keys are assigned so called hash values.

Even if table is billions of elements long, the dictionaries can lookup the value stored with desired key in the same time as in small tables.

It may be worth to mention that table.insert is equivalent to (but slower on micro level than)

local t = {}
t[#t+1] = element we are inserting

Same goes for table.remove.

t[1] = nil

There is no binary search happening. It’s not about numerical approximation method we meet when we work with polynomials.

When index is used to find an element, algorithm knows exactly what the value is without any search delays.

Hopefully this clears any confusion. Have a great day!

EDIT @S0MBRX
Same goes for indexing numbers in arrays.

local t {"Roblox"}
t[1] --> Roblox

Hashing is used again. Keys and their positions in table are already known to the internal algorithm, meaning they can access values without any searching, binary or linear.

1 Like
#3

its probably just a linear search keep in mind other searching methods require the table to be in an ordered form so it can only really be linear

u can write your own binary search if you are wanting to use a binary search

1 Like
#4

No search is being done. It’s the difference between “Find Walmart in this city” and “What building is located at 1000N 3000W”
The computer is wired to go straight to coordinates, so it does. To find Walmart though, the computer needs to go to every single address in the city until it finds Walmart.

1 Like
#5

I’m going to assume that in actuality, a lua table stores different coordinates to those values rather than put them inside a single container, like getting variables separately.