script/SDBMHash.lua


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

local byte = string.byte
local max = 0x7fffffff

---@class SDBMHash
local mt = {}
mt.__index = mt

mt.cache = nil

---@param str string
---@return integer
function mt:rawHash(str)
    local id = 0
    for i = 1, #str do
        local b = byte(str, i, i)
        id = id * 65599 + b
    end
    return id & max
end

---@param str string
---@return integer
function mt:hash(str)
    local id = self:rawHash(str)
    local other = self.cache[id]
    if other == nil or str == other then
        self.cache[id] = str
        self.cache[str] = id
        return id
    else
        log.warn(('哈希碰撞：[%s] -> [%s]: [%d]'):format(str, other, id))
        for i = 1, max do
            local newId = (id + i) % max
            if not self.cache[newId] then
                self.cache[newId] = str
                self.cache[str] = newId
                return newId
            end
        end
        error(('哈希碰撞解决失败：[%s] -> [%s]: [%d]'):format(str, other, id))
    end
end

function mt:setCache(t)
    self.cache = t
end

function mt:getCache()
    return self.cache
end

mt.__call = mt.hash

---@return SDBMHash
return function ()
    local self = setmetatable({
        cache = {}
    }, mt)
    return self
end