强制表格重新哈希在先前的重新哈希后无效

2016-4-21 14:30:33
收藏：0
阅读：68
评论：1

我创建了一个函数，可以调整数组的大小并将新条目设置为 0，但也可以以2种不同的方式缩小数组的大小： 1. 简单地将 n 属性设置为新大小（由于此原因，无法使用长度运算符）。 2. 将新大小之后的所有值设置为 nil，以强制重新哈希到2 * 大小。

local function resize(array, elements, free)
    local size = array.n

    if elements < size then     -- 减小尺寸
        array.n = elements
        if free then
            size = math.max(size, #array)   -- 如果有多个调整尺寸，则进行二次调整
            local base = elements + 1
            for idx = base, 2*size do       -- 强制重新哈希，释放额外不需要的内存
                array[idx] = nil
            end
        end
    elseif elements > size then -- 增加尺寸
        array.n = elements
        for idx = size + 1, elements do
            array[idx] = 0
        end
    end
end

如何测试它：

local mem = {n=0};
resize(mem, 50000)
print(mem.n, #mem)              -- 50000 50000
print(collectgarbage("count"))  -- 相对较大的数字

resize(mem, 10000, true)
print(mem.n, #mem)              -- 10000 10000
print(collectgarbage("count"))  -- 较小的数字

resize(mem, 20, true)
print(mem.n, #mem)              -- 20 20
print(collectgarbage("count"))  -- 与上述相同的数字，但它应该是更小的数字

但是，当我在第二次调整大小的调用中没有将 true 作为第三个参数传递（因此它不会在第二次调用中强制重新哈希），第三次调用最终确实重新哈希了。

我错过了什么吗？我期望第三个调用在第二个调用后也重新哈希。

点赞
用户3677376
用户3677376

这是表格通常在调整大小前后的更清晰图：

table: 0x15bd3d0    n:  0       #:  0       narr:   0       nrec:   1
table: 0x15bd3d0    n:  50000   #:  50000   narr:   65536   nrec:   1
table: 0x15bd3d0    n:  10000   #:  10000   narr:   16384   nrec:   2
table: 0x15bd3d0    n:  20      #:  20      narr:   16384   nrec:   2

然后发生的情况如下：

  • 调整大小为 50000 元素时，表格被重新哈希多次，最后恰好包含了一个用于n字段的哈希槽和足够的整数键值数组部分槽。
  • 在收缩到 10000 元素时，首先将整数键 10001 到 65536 分配为nil，再将 65537 到 100000 分配为nil。第一组分配永远不会导致重新哈希，因为您分配给现有字段。这与next函数的保证有关。第二组分配将导致重新哈希，但由于你分配的是nil，Lua 会在某个时候意识到表格的数组部分为空超过半数（参见 ltable.c 开始的说明）。Lua 将缩小数组部分的大小，并使用第二个哈希槽用于新键。但由于您正在分配nil，因此该第二个哈希槽永远不会被占用，Lua 可以随意重用它_所有_剩余的分配（它通常而不总是这样做）。此时你无法注意到重新哈希，因为你总是最终拥有16384个数组槽和 2 个哈希槽（一个用于n，一个用于新元素的分配）。
  • 收缩到 20 元素时，继续这样，但例外是第二个哈希槽已经可用。因此，您可能_永远_不会得到重新哈希（数组大小保持大于必要的大小），但如果您_确实_（由于某种原因 Lua 不喜欢那个空闲的哈希槽），你将看到数组槽数量降至一个合理水平。

这是在第二个收缩期间获得重新哈希时的情况：

table: 0x11c43d0    n:  0       #:  0       narr:   0       nrec:   1
table: 0x11c43d0    n:  50000   #:  50000   narr:   65536   nrec:   1
table: 0x11c43d0    n:  10000   #:  10000   narr:   16384   nrec:   2
table: 0x11c43d0    n:  20      #:  20      narr:   32      nrec:   2

如果要重复本人的实验，则lua-getsize的 git HEAD 版本（原始版本在 这里）现在也会返回表格的数组/哈希部分的槽数量。

2016-04-21 19:17:11

作者:

用户3989259

用户3989259
推荐文章