lua使用自定义类型作key

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› LUA›LUA教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　前端使用typescript，后端使用C++和lua，在讨论后端下发的int64类型值如何处理时，我建议前端使用long.js，但前端说他需要用这个作key，而js没法用自定义类型作key。我回了一句“js居然没法用自定义类型作key，这么弱”，但是说完这句话，我就愣住了，貌似那里不对。

　　我认为任何一门逻辑完备的语言（基础的数据结构和流程控制等等），都能实现这么一个逻辑，js显然也能实现。说“无法”无非就是实现代价过大，比如需要引入其他库、修改更多的代码，运行效率更低等等原因。但我之所以会愣住，是因为当时脑中想的是“C++和lua都支持，而js这个应该这么广的语言居然不支持“，然而转念一想，lua支持任意数据类型作key，但和用自定义类型作key完全不是一码事。

　　首先，来看下C++中的自定义类型为key

#include <unordered_map>
#include <iostream>

class MyInt64
{
public:
    MyInt64(int hi, int lo)
    {
        this->hi = hi;
        this->lo = lo;
    }

    ~MyInt64()
    {
    }

    int hi;
    int lo;
};

class MyInt64Hash
{
public:
    std::size_t operator()(const MyInt64 &i) const
    {
        int64_t hash = i.hi;
        return (hash << 32) + i.lo;
    }
};


struct MyInt64Equal
{
    bool operator () (const MyInt64 &lhs, const MyInt64 &rhs) const
    {
        return lhs.hi  == rhs.hi && lhs.lo == rhs.lo;
    }
};
int main()
{
    std::unordered_map<MyInt64, int, MyInt64Hash, MyInt64Equal> map;

    MyInt64 i1(1, 1);
    MyInt64 i2(1, 1);

    map.emplace(i1, 999);

    auto found = map.find(i2);
    if (found != map.end())
    {
        std::cout << found->second << std::endl; // 输出 999
    }

    return 0;
}

在上面的代码中i1和i2是不同的两个变量（它们的地址不一样），但是他们的值是一样的，所以对map进行操作时，他们操作的是同一个值。而在lua中，固然可以用任意类型的变量作为key，比如

local i1 = {1, 1}
local i2 = {1, 1}

local map = {}

map[i1] = 999

print(map[i2]) -- 输出nil

显然，这不预期的结果啊。在前后端交互的过程中，可以保证数值是一致的，但哪能保证他们的地址是一致的呢(如果能知道地址，就直接拿到变量了，还要这个map干啥)。我使用lua将近5年了，还是第一次遇到这个问题，我的第一反应是这个在元表中有一个__hash之类的吧，然而元表中有__eq，却没有__hash，那这意味着，官方是没有直接实现这一个功能的。

假如让我实现这个功能，我的第一反应是使用元表的__index和__newindex来劫持这个map的读写，但这样一来，就需要把真正的数据存在另一个table中，然后为了实现遍历，还需要重新实现__pair，那事情就变得复杂多了。这个功能虽然小众，但如果支持的话，还是十分方便的，是什么原因C++支持这个自定义hash，而lua不支持呢，这我倒来了兴趣。

网上查了一下，原来这个事情在10多年前早有定论：http://lua-users.org/lists/lua-l/2009-02/msg00000.html，总结一下，大概有以下几点原因

1. lua使用非基础类型（table、userdata等等）为key时，直接使用内存地址，这相当于没有hash函数，效率高

2. 实现__hash这个函数很容易，但是什么时候调用很难确定。最好的方案是如果存在__hash，则调用__hash，否则按原方案使用内存地址作为hash。但是这个方案会导致table的效率大幅下降。因为即使没有__hash，原来直接取内存地址这一个步骤，变成了判断是否存在元表、是否存在__hash、取内存地址三个步骤，而table是lua唯一的数据结构，包括标准库在内都是使用table，这显然会导致整个语言的效率大幅下降

3. 在第2点的基础上，即使不考虑效率问题，自定义key的mutable（可变）让整个table的维护变成无比复杂。例如

local i1 = {1, 1}

local map = {}

map[i1] = 999
i1[1] = nil -- 这时候map需要做什么变化？？？

当key中的数值被修改时，那__hash得到的值必定会变化，如果重新调整map中的元素hash，显然很低效，也不现实（需要跟踪i1所有值的变化，包括它的子table的子table的子table...），如果不调整，那整个hash就对不上了。C++不存在这个问题是因为C++会把key复制一份变成const，但是在lua中复制这一份table完全不现实，因为这个table可能无比巨大

4. 上面说了那么多__hash缺点，假如我不实现__hash，以现在的代码，我就能更优雅地解决问题，又何必去实现__hash

local i1 = {1, 1}
local i2 = {1, 1}

local map = {}

-- 假设lua不支持int64，而我们需要用int64作key，那使用使用 高位_低位 这个字符串作key
setmetatable(map, {
    __index = function(t, k)
        return rawget(t, k[1] .. "_" .. k[2])
    end,
    __newindex = function(t, k, v)
        return rawset(t, k[1] .. "_" .. k[2], v)
    end
})

map[i1] = 999

print(map[i2]) -- 输出999