How to get any element in a dictionary without a key, O(1) time complexity

[USADevForum1]

@Katrist

Edit: Now I’m not sure if I’m confused what the question was but are they asking how to get a random value from the dictionary? Or are they asking how to search the dictionary if it has a certain value?

The question is the same as the initial thread, but people are explaining solutions that have to do with other aspects, so it kinda gets confusing.

[PerilousPanther]

Haha no worries. I still don’t understand OP’s original question.

[USADevForum1]

@PerilousPanther

But that point is the first iteration, for the worst case. So wouldn’t it be the same as itemId = itemIds[first_index]. Could be wrong, not particularly familiar with Lua internal workings,.

I doubt it is O(1)

I believe this code:

local t = {}
for i, v in t do
  break
end

is a O(n), because luau needs to do a internal search to get the keys and values, which is naturally a O(n) task.

[PerilousPanther]

Perhaps. @Katrist is almost certainly right about using regular methods (a loop) probably not having a massive impact on real runtime. But for sake of argument can you clarify exactly what you want?

1. If you just want arbitrary (random value) in (arguably) O(1) time, why not use the stack implementation I suggested, but use random values to swap top.

2. If you don’t care about random values, and instead just want a value (like you would get from your for loop + break example) why not just use a basic stack or linked list.

[USADevForum1]

@PerilousPanther

If you don’t care about random values, and instead just want a value (like you would get from your for loop + break example) why not just use a basic stack or linked list.

I figured that using a linked list over an array just moves the inefficiencies elsewhere

@USADevForum1

You’re kinda right now that i’m thinking about it, the change from arrays to linked lists means that accessing is faster, but removing an arbitrary element in the list is slower. Not sure should i actually implement the linked list change now, because i remove elements from the list more often than i need to access them…

Yea, i think i’ll use a simple loop as @Katrist said, because changing the data structure just moves the inefficiencies somewhere else -but it’s still there - whether it’s in accessing, searching or removing, there will always be an O(n)

[PerilousPanther]

I agree with your overall sentiment, but accessing is not O(n) - especially not if you keep a top value.

[VegetationBush (FartedWayTooHard)]

Thanks for clarifying!

If I’m understanding correctly, you’re trying to create new items with new item ids during runtime. If that is the case, using the inverse dictionary does work, but, you would just have to edit it with the itemIds. Here’s a mock implementation:

local itemTable = {}
local inverse = {}

local currentId = 0
local function newItem(itemName)
    itemTable[currentId] = itemName
    inverse[itemName] = currentId

    curentId += 1
end
local function findItemKey(itemName)
    return inverse[itemName] --> finding the item key is simply an access to the inverse dict
end
local function removeItem(itemName)
    local key = findItemKey(itemName)
    if index then
        itemTable[index] = nil
        inverse[itemName] = nil
    end
end

Note that this will only work under the assumption that the value of the item (in the provided example, the name of the item) will never be the same. There is an approach with using tables if you multiple ids with the same item name.

[funwolf7]

If you just want to get any key randomly and don’t care which (it seems like that is what you want but it’s hard to tell), then use the next function. Per the Luau Website:

function next<K, V>(t: { [K]: V }, i: K?): (K, V)?

Given the table t, returns the next key-value pair after i in the table traversal order, or nothing if i is the last key. When i is nil, returns the first key-value pair instead.

The last sentence is the most important part. You can get a sorta random (it depends on how the dictionary is structured in memory which isn’t consistent) key-value pair by simply calling next(t).

Honestly though, I wouldn’t worry about time complexity that much. Unless you are working with massive amounts of entries, the overhead from a more advanced solution might end up making the program slower. In this case, next is the fastest way to do this, but it reaches the point where i doubt it even matters.

(By the way, iterating through a dictionary then breaking at the first entry is O(1) in Luau since it doesn’t get every entry before beginning iteration, but rather fetches the next key-value pair before each step of iteration.)

[Astr0Derp (Astr0)]

This implementation has a known length and allows for O(1) access to an nth item (array style, ordered by when the item was added, first to last). Items can also be accessed in O(1) time using a non-sequential, non-continuous itemId (like a dict), which is different than the array index value. Removing values completely (not just changing a value to a new value) is still potentially O(n), like an array, so that action is pushed out of the main execution thread so the function can return immediately. The shuffling of the support array happens separately in another thread (is deferred). Basically, this version should be O(1) for everything except removing an item entirely, which is still O(1) as far as the calling code is concerned because the O(n) table.remove call is run in another thread at a later time.

To support that, the code inserts “dummy” data into the tables to indicate that the entry has been flagged for removal and includes a loop in the getRandom function that tries again if one of these flagged spots was randomly requested. It also uses two tables (an array and a dict), so it takes up more memory, which shouldn’t be an issue unless you have a LOT of entries.

Anyway, something else to maybe play around with for possible ideas.

Parent test script

local RandomHashSet = require(script.Set)

-- Example usage
local randomSet = RandomHashSet.new()

for i = 1, 1000 do
	randomSet:add(i, "a")
end

print("Number of elements", randomSet:numberOfItems())

wait(5)

for i = 1, 1000 do
	local randomId, randomValue = randomSet:getRandomItem()
	print("Random item:", randomId, randomValue)
	print("Number of elements", randomSet:numberOfItems())
end

Test using Runservice

-- This adds and removes every frame (might be slow with prints)
local RunService = game:GetService("RunService")
local RandomHashSet = require(script.Set)
local Rand = Random.new()

local ASCII_A = 65
local ASCII_Z = 90

local ENTRIES_PER_FRAME = 1		-- test will add this many AND rem this many every frame
								-- will be slow because of prints. can turn those off
local strFunction = function() return string.char(Rand:NextInteger(ASCII_A, ASCII_Z)) end

local function getString()
	local n = Rand:NextInteger(1, 20)
	local t = table.create(n)
	for i = 1, n do
		t[i] = Rand:NextInteger(0,1) == 1 and strFunction() or string.lower(strFunction())
	end
	return table.concat(t)
end

-- Example usage
local randomSet = RandomHashSet.new()

for i = 1, 1000 do
	randomSet:add(i, getString())
end
print("Number of elements", randomSet:numberOfItems())

wait(5)

RunService.Heartbeat:Connect(function()
	for i = 1, ENTRIES_PER_FRAME do
		local randomId, randomValue = randomSet:getRandomItem()
		print("Random item:", randomId, randomValue)
		randomSet:add(Rand:NextInteger(2000, 5000), getString())
	end
	print("Number of elements", randomSet:numberOfItems(), "nilCnt", randomSet.nilCount)
end)

--[[
	RandomHashSet
	
	Add key,value pairs and access/remove them randomly

--]]

local NIL_KEY = -1

local RandomHashSet = {}
RandomHashSet.__index = RandomHashSet

function RandomHashSet.new()
	local self = {
		hash_set = {},	-- dict with user key, val pairs 
		elements = {},	-- array with ref to keys
		nilCount = 0,	-- track undeleted entries
	}
	setmetatable(self, RandomHashSet)
	
	return self
end

function RandomHashSet:numberOfItems()
	return #self.elements - self.nilCount
end

function RandomHashSet:add(itemId, value)
	-- check if key is already used
	if not self.hash_set[itemId] then
		-- add entry to elements array
		table.insert(self.elements, itemId)
		-- add key, val to dict
		self.hash_set[itemId] = value
	end
end

function RandomHashSet:remove(itemId)
	local value = self.hash_set[itemId]
	if value then
		-- use the itemId or NIL_KEY as the "needle" in find
		local searchKey = value == NIL_KEY and value or itemId
		local index = table.find(self.elements, searchKey)
		if index then
			-- remove entry from elements array and shrink the array
			table.remove(self.elements, index)
			-- clear entry from dict
			self.hash_set[itemId] = nil
		else
			warn("index not found! (nil)", itemId)
		end
	else
		warn("no value for this key", itemId)
	end
end

function RandomHashSet:getRandomItem()
	local index = NIL_KEY
	
	-- repeat try if grabbed NIL_KEY entry (doesn't repeat often, but can in tight loops)
	while true do
		if self:numberOfItems() > 0 then
			index = math.random(1, #self.elements)
			if self.elements[index] == NIL_KEY then
				--warn("## Collision warning")	-- DEBUG
				task.wait()	-- safety switch in case of runaway situation
			else
				break
			end
		else
			return nil, nil	-- set is empty
		end
	end
	
	-- retrieve the id from elements list and value using dict key
	local id = self.elements[index]
	local value = self.hash_set[id]
	
	-- assign "used" placeholders in elements list
	self.elements[index] = NIL_KEY
	self.hash_set[id] = NIL_KEY
	-- signal that there is a "hole" in the table
	self.nilCount += 1
	
	-- clean up in new thread. This will run when it can (fairly quickly)
	-- and won't interfere with function returning values immediately.
	-- Used entries are set to NIL_KEY values above and are ignored if
	-- retrieved again before cleanup.
	task.defer(function() self:remove(id); self.nilCount -= 1 end)

	-- maybe both don't need to be returned
	return id, value
end

return RandomHashSet

Or something more straight-forward but unordered

--[[
	Hashed Set class using array for items and dict for key access to items
	
	Unique - only one item with a given Id allowed (i.e. a set)
	Unordered - order is not maintained (moves items from end of array to plug holes)
				however, the current index for a given record/key is kept current.				
	Efficient - lookup, insert, delete are all O(1)
	
	* Allows for random access
	* Allows for access to item via it's key (if known)
	* Number of items is known
--]]

local Item = require(script.Item)


--- Module

local SetArray = {}
SetArray.__index = SetArray

function SetArray.new()
	local self = {
		array = {},		-- array of Item objects
		keyDict = {},	-- dict of itemIds
	}
	setmetatable(self, SetArray)

	return self
end

function SetArray:length()
	return #self.array
end

function SetArray:hasItem(itemId)
	if not itemId then return end
	return self.keyDict[itemId]
end

function SetArray:peekAtItem(itemId)
	if not itemId then
		warn("Requested itemId cannot be nil")
		return 
	end
	local item = self.keyDict[itemId]
	if item then
		local tmp = item:peek()
		--print("PEEK AT ITEM", "Id:", tmp.itemId, "Value:", tmp.value, "Index:", tmp.index)
		return tmp
	else
		warn("Requested item does not exist.")
	end
end

function SetArray:peekAtIndex(index : number)
	if index and 0 < index and index <= self:length() then
		index = math.floor(index)
		local item = self.array[index]
		local tmp = item:peek()
		--print("PEEK AT INDEX", "Id:", tmp.itemId, "Value:", tmp.value, "Index:", tmp.index)
		return tmp
	else
		warn("Requested index is missing or out-of-bounds.")
	end
end

function SetArray:add(itemId, value)
	-- set allows only one item for ea Id
	if not self:hasItem(itemId) then
		local item = Item.new(itemId, value)
		table.insert(self.array, item)
		item:setIndex(self:length())
		self.keyDict[itemId] = item
	end
end

function SetArray:_removeAndFill(index)
	if not index then return end

	local len = self:length()
	if index and 0 < index and index <= len then
		index = math.floor(index)
	else
		return
	end

	local rem_item = self.array[index]	-- item being removed
	local end_item = self.array[len]	-- last item in array
	
	self.keyDict[rem_item.itemId] = nil	-- clear "removed item" from keyDict
	rem_item:setIndex(nil)				-- once popped, it has no index
	
	self.array[index] = end_item		-- move last item in array to index (replace "removed item")
	end_item:setIndex(index)			-- update index value in moved item
	
	table.remove(self.array, len)		-- shorten the array
end

function SetArray:remove(itemId)
	local item = self:hasItem(itemId)
	if item then
		self:_removeAndFill(item.index)
	end
end

function SetArray:pop()
	local len = self:length()
	if len > 0 then
		local index = math.random(1, len)
		local item = self.array[index]
		
		self:_removeAndFill(index)
		
		item:setIndex(nil)				
		return item
	end
end

return SetArray

local Item = {}
Item.__index = Item

function Item.new(itemId, value)
	local self = {
		itemId = itemId,
		value = value,
		index = nil,
	}
	setmetatable(self, Item)

	return self
end

function Item:peek()
	return {itemId = self.itemId, value = self.value, index = self.index}
end

function Item:setIndex(index : number?)
	self.index = index and math.floor(index) or nil
end

function Item:setValue(value : any)
	self.value = value
end

return Item

[USADevForum1]

This was looking very promising at first as it has O(1) lookup, removal and insertion, but when i tried to implement it in my item system, i came across one problem. I don’t know the any keys, and any of the values (itemIds). So this inverse dictionary solution won’t work in this case, but i did like the idea.

I have a really simple way to describe this problem now, and hopefully you’ll come up with new ideas:
I have a dictionary dict, but i don’t know any of it’s contents

-- I don't know any keys or values inside. The only thing i know about this is that the values are itemIds
local dict = {
  ["Test"] = 4,
  [Instance.new("Part")] = "dkfjods",
  [5498] = Color3.new(1,0,0.5)
}

Is there any to pull out one value, with time complexity O(1) from the dictionary, without knowing any keys or values in the dictionary

[USADevForum1]

No way! Using the next function actually worked. It allowed me to get key-value pair from the items dictionary even though i didn’t know it’s contents. This was the simplest solution.

@funwolf7

You can get a sorta random (it depends on how the dictionary is structured in memory which isn’t consistent) key-value pair by simply calling next(t).

Yes, this is actually desired. That’s what i mean in the title by “get any element”. A fully random system would be O(n) complexity, but since it’s naturally random by memory location it’s O(1).

@funwolf7

Honestly though, I wouldn’t worry about time complexity that much. Unless you are working with massive amounts of entries, the overhead from a more advanced solution might end up making the program slower. In this case, next is the fastest way to do this, but it reaches the point where i doubt it even matters.

Optimization really did matter here, because in my game, items spawn are an really quick rate (like 200 items/sec), and then are collected at a slightly slower rate. My game can only handle like up to 1000 item/sec before you start to get noticeable lag, which is quite limiting - that’s the reason i’m trying to optimize this.

@funwolf7

(By the way, iterating through a dictionary then breaking at the first entry is O(1) in Luau since it doesn’t get every entry before beginning iteration, but rather fetches the next key-value pair before each step of iteration.)

Okay, thanks for the information. The reason i thought it was O(n), is because in other programming languages, such as Javascript, you need to get all the key value pairs before you can iterate them. The mere act of retrieving them is a O(n) operation, and it is hidden inside the method Object.values() - you’d expect that to be O(1), but it isn’t.

Looping through a dictionary as a result in Javascript, takes 2n steps.

[VegetationBush (FartedWayTooHard)]

If I’m understanding properly, you want to get an arbitrary key with an arbitrary value, and remove it from the table?

The problem with using next is that its’ behavior is undefined. next is also not technically random. It will return the same value for the same unmodified table each time.

If you want to be able to add and remove items with arbitrary values in O(1) time, you can implement a list-based approach with swap to remove instead of shifting every element down:

local itemTable: {
    [number]: {
        key: any,
        value: any,
    }
} = {}

local function newItem(key: any, value: any)
    table.insert(
        itemTable,
        {
            key = key,
            value = value,
        }
    )
end
local function getAndRemoveRandom()
    local length = #itemTable --> this is O(1) time as the length is a constant value stored internally
    local index = math.random(1, length)    
    local entry = itemTable[index] --> retrieving the random item
    local last = itemTable[length] --> retrieving the last element

    -->> swapping and popping
    itemTable[length] = nil
    itemTable[index] = last

    return entry
end

This approach is also nicer as you’re not using different datatypes as table keys, which I believe forces Lua to do some tinkering to make it work in the backend.

[Astr0Derp (Astr0)]

That’s pretty much where I ended up after some more tinkering. Doesn’t seem he needs the keys/itemIds for item retrieval, so they’re really just more data. It’s easy enough to add a hash dict of keys → item tables for key access if needed for things like :hasKey(), assuming it’s meant to be a set (unique itemIds). Swapping the end value to fill holes works since order isn’t important. Efficient and more randomy “random” access.

The multiple datatype observation is an important note beyond extra work Lua might need to do. Having a table that is a catchall can be problematic if it needs to do much of anything beyond hold stuff. Hopefully this random-access collection is meant to be a general-purpose tool applied to one kind of thing at a time and not just a melting pot. Using a diff table for each kind of thing can save on headaches, but that aside, the itemTable above could be a class with an execute method, for example, that would allow for the current thing to do something without the need for a bunch of conditionals to sort out what kind of thing it is every time you pop a new item.

[EmilyBendsSpace]

@USADevForum1

I’m not sure whether the solution you provided will work in my case, because i’d have to create the dictInverse before getting the key ( O(n) time complexity )

Creating the inverse mapping has O(N) complexity, but you do this just once, so that you can remove elements by value from the dictionary in O(1) time. It doesn’t make all removals O(N), because it’s a one-time cost. It does, however, double the amount of memory used.

Without creating the reverse lookup map, removing an arbitrary value from an unordered map is going to be O(N). You can’t do any better than that. Faster options like binary search require the data to be maintained sorted, in an ordered container. In Lua, this would mean maintaining a pure-array table and inserting new Ids in their sorted position, rather than appending to the end, which is also O(log N) on average to find out where to insert the item. The true cost of inserting an item into the middle of an array depends on how the array is actually implemented in the VM, and whether the new element triggers a resize of the array, which requires more memory to be allocated and possibly for the entire array to be moved.

[EmilyBendsSpace]

@VegetationBush

This approach is also nicer as you’re not using different datatypes as table keys, which I believe forces Lua to do some tinkering to make it work in the backend.

But if the OP wants to remove a specific element, it’s still O(N) to find its index in itemTable.

[USADevForum1]

Yes this is another solution that will work, but honestly the next function is the most simplest, and i don’t need to rewrite my item system.

Your solution is good when you want actual random access, but i just want access to a value (doesn’t have to be random), and the next approach is more simpler.

[VegetationBush (FartedWayTooHard)]

@EmilyBendsSpace

But if the OP wants to remove a specific element, it’s still O(N) to find its index in itemTable.

The solution I’ve provided does not do any searching. It’s always O(1) as it only accesses an index.

[EmilyBendsSpace]

@VegetationBush

The solution I’ve provided does not do any searching. It’s always O(1) as it only accesses an index.

Yeah, I didn’t realize the OP wanted access to literally anything in the dictionary, I assumed he was asking how, given an already-populated dictionary, how to get the key for a specific value. I normally just assume that anyone already writing Lua knows how to use next and pairs, so I didn’t realize that was the blocker here.