A high performance implementation of a hash table with a point class for testing purposes

hashtable.lua

local hashtable = (function()
    local hashtable_mt = {}
    hashtable_mt.__index = hashtable_mt 

    local primes = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741}
    local empty = {}

    function hashtable() 
        local ht = {
            data = {},
            size = 0, -- note this is not necessarily accurate of the hashtable size if elements have been deleted 
            maxsize = 23,
        }

        for i = 1, ht.maxsize do 
            ht.data[i] = empty 
        end 

        return setmetatable(ht, hashtable_mt)
    end 

    function hashtable_mt:resize(_newsize)
        local newsize = _newsize 
        for i = 1, #primes do 
            if primes[i] >= _newsize then 
                newsize = primes[i]
                break 
            end 
        end 
        
        local olddata = self.data 
        local olddatasize = self.maxsize 
        self.maxsize = newsize 
        
        -- prepare the new data table 
        local data = {}
        self.data = data 

        for i = 1, newsize do 
            data[i] = empty
        end 

        -- transfer data 
        for i = 1, olddatasize do 
            if olddata[i] ~= empty then 
                if olddata[i][2] == nil then 
                    -- free a slot, an element was deleted :P 
                    self.size = self.size - 1
                else 
                    self:set(olddata[i][1], olddata[i][2])
                end 
            end 
        end 
    end 

    function hashtable_mt:set(key, value)
        local maxsize = self.maxsize 
        
        -- go through and check for an open slot, one will be found eventually :P
        local s 
        local data = self.data 
        local h = key:hash()
        local i = 0 
        while true do 
            s = (h + i * i) % maxsize + 1 -- slot 
            if data[s] == empty then 
                data[s] = {key, value}
                self.size = self.size + 1 
                break 
            elseif data[s][1] == key then 
                data[s][2] = value 
                break
            end 

            i = i + 1
        end 
        
        -- check if we need to resize
        if self.size >= maxsize * 0.8 then 
            maxsize = self.size * 2
            self:resize(maxsize)
        end 

        return value 
    end 

    function hashtable_mt:get(key, value) 
        local h = key:hash()
        local i = 0 
        local maxsize = self.maxsize 
        local data = self.data

        local s 
        repeat  
            s = (h + i * i) % maxsize + 1
            i = i + 1 
        until data[s] == empty or data[s][1] == key 

        return data[s][2]
    end
    return hashtable 
end)()

function benchmark()

    local point_mt = {}
    local math_floor = math.floor 

    function point_mt:hash()
        return math_floor(self[1] * 7919 + self[2])
    end

    function point_mt:getX()
        return self[1]
    end 

    function point_mt:getY()
        return self[2]
    end

    function point_mt:__eq(other)
        return self[1] == other[1] and self[2] == other[2]
    end 

    point_mt.__index = point_mt 

    function point(x, y)
        return setmetatable({x, y}, point_mt)
    end

    local ht = hashtable()
    local time1 = os.clock()
    for i = 1, 1000 do
        for j = 1, 1000 do 
            ht:set(point(i, j), "why hello there")
        end 
    end 
    local time2 = os.clock()
    print("inserting 1,000,000 records took " .. tostring(time2 - time1) .. " seconds.")

    local time1 = os.clock()
    for i = 1, 1000 do
        for j = 1, 1000 do 
            if ht:get(point(i, j)) == nil then
                error("fatal error")
            end
        end 
    end 
    local time2 = os.clock()
    print("fetching 1,000,000 records took " .. tostring(time2 - time1) .. " seconds.")

    local time1 = os.clock()
    local ht = {}
    for i = 1, 1000 do 
        for j = 1, 1000 do 
            ht[tostring(i) .. '-' .. tostring(j)] = "hello world!"
        end 
    end 
    local time2 = os.clock()
    print("inserting 1,000,000 records w/dumb string keyed table took " .. tostring(time2 - time1) .. " seconds.")


    local time1 = os.clock()
    local ht = {}
    for i = 1, 1000 do 
        for j = 1, 1000 do 
            local t = ht[tostring(i) .. '-' .. tostring(j)]
        end 
    end 
    local time2 = os.clock()
    print("getting 1,000,000 records w/dumb string keyed table took " .. tostring(time2 - time1) .. " seconds.")

end

-- benchmark()