Table data structure that "garbage collects" not-recently-used items in O(1) time

gistfile1.md

I use this data structure all the time. Can someone leave a comment and tell me what it's called?

1. insert(k,v): add a new value
2. lookup(k): lookup an existing value
3. age(): delete old entries (that have not been used since previous call to age())

# Initialize 'old' and 'new' to empty tables
local old, new = {}, {}

function insert(k, v)
  new[k] = v
end

function lookup(k)
  if new[k] then
    # Found in new table
    return new[k]
  elseif old[k] then
    # Migrate from old table to new table
    new[k] = old[k]
    return old[k]
  else
    # Not found
    return nil
  end
end

function age()
  # Entries in 'old' are dropped, entries in 'new' become old.
  old = new
  new = {} # empty table
end

I suppose it's good that Lua distinguishes between statements and expressions, because otherwise I wouldn't be able to resist this 4-liner version:

local old, new = {}, {}
function insert(k, v) new[k] = v                         end
function lookup(k)    return new[k] or (new[k] = old[k]) end
function age()        old, new = new, {}                 end

Using Tony Finch's suggestion to make insert() return 'v' and thus refactor into what looks like actually valid Lua code:

local old, new = {}, {}
function insert(k, v) new[k] = v; return v                end
function lookup(k)    return new[k] or insert(k, old[k])  end
function age()        old, new = new, {}                  end

.. and yeah makes sense because in Lisp it's SETF returning the value that makes it combine nicely with AND/OR/etc.

Common Lisp version being discussed on Twitter:

(defvar *new* (make-hash-table))
(defvar *old* (make-hash-table))

(defun insert (k v)
  (when v (setf (gethash *new* k) v)))

(defun lookup (k v)
  (or (gethash *new* k) (insert k (gethash *old* k))))

(defun age ()
  (rotatef old new)
  (clrhash new))

Nice -- I'll remember that. Here's a similar-but-different thing I do sometimes:

table = {}

def insert(k, v):
    if k not in table and 10000 <= len(table):
        table.clear()
    table[k] = v

Seems like a degenerate version of a MRU cache?

Also, the lisp version of "lookup" shouldn't have a "v" argument, right?

It looks like an LRU cache that has no hard limit on the number of elements.

Also, I ported this data structure to Python recently.