summaryrefslogtreecommitdiff
path: root/script/SDBMHash.lua
diff options
context:
space:
mode:
Diffstat (limited to 'script/SDBMHash.lua')
-rw-r--r--script/SDBMHash.lua60
1 files changed, 60 insertions, 0 deletions
diff --git a/script/SDBMHash.lua b/script/SDBMHash.lua
new file mode 100644
index 00000000..48728aec
--- /dev/null
+++ b/script/SDBMHash.lua
@@ -0,0 +1,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