get_pointer()方法中可能存在的性能问题

[DanKE123abc]

原代码中的function db:get_pointer(key)当发生冲突时，会一直尝试下一个位置

while true do
        -- 寻址
        local pointer = (level * block_size) + hash_code -- 计算指针位置
        local a, b = self:get_addr(pointer, key)         -- 获取地址
        if a then
            -- 存在即返回，否则下降深度
            return pointer, a, b, key, nil, level
        end
        level = level + 1 -- 下降深度
    end

这种方法是否会在冲突较多时导致性能下降？

未写出测试用例能够证明。

我找到一种解决方案 开放寻址法

引用CSDN的一篇文章 [开放寻址法](https://blog.csdn.net/jiangshaoxin1987/article/details/101162006)

下面是我给出的解决方案（本人lua代码能力不佳，勿喷）

function db:get_pointer(key)

  -- 定义当前簇深度和簇大小
  local level, block_size = 0, self.block_size
  local addr_size = self.addr_size
  local hash_code = (hash(key) % block_size) + 1 -- 获取hash值
  local probe_count = 0 -- 开放寻址法迭代变量 ———————— 变更1
  key = tostring(key)               -- key转字符串
  -- 判断数据库可遍历，即留出next属性的空间
  if self.can_each then
​    block_size = block_size * 2
​    hash_code = hash_code * 2
  end
  -- 计算实际占用空间
  block_size = block_size * addr_size
  -- 计算指针实际位置
  hash_code = hash_code * addr_size

  while true do
​    -- 寻址
​    local pointer = (level * block_size) + hash_code -- 计算指针位置
​    local a, b = self:get_addr(pointer, key)     -- 获取地址
​    if a then
​      -- 存在即返回，否则下降深度
​      return pointer, a, b, key, nil, level
​    end
​    -- 开始二次探测 ———————— 变更2
​    probe_count = probe_count + 1
​    hash_code = (hash_code + probe_count * probe_count) % block_size 
​    if probe_count > block_size then
​      level = level + 1 -- 下降深度
​      probe_count = 0
​    end
  end
end

[limao996]

感谢大佬，我会尝试优化的！下个版本打算重构项目，准备试着用一下哈希桶