Node.js聊天应用用functional-red-black-tree查询用户返回undefined如何解决

问题根因 #

你当前的比较器存在两个核心问题：

1. 当两个不同ipv4的Key的rank、score、loginTime完全相等时，比较器没有返回值，默认返回undefined，导致红黑树的节点索引逻辑混乱，所以插入顺序可能碰巧符合预期，但查询、删除时找不到对应节点。
2. 红黑树查询时，只有当比较器返回0才会判定为匹配，你当前的比较器虽然逻辑上优先判断ipv4相等返回0，但如果前面的rank、score、loginTime比较分支先命中，就走不到ipv4相等的判断，自然会返回undefined。

方案1：修复比较器（最推荐，无需改动现有结构） #

直接调整比较器逻辑，优先判断ipv4相等，保证所有分支都有明确返回值即可：

var tree = createTree((userAKey, userBKey) => {
    // 只要ipv4相同就判定为同一个key，优先走这个分支
    if (userAKey.ipv4 === userBKey.ipv4) return 0
    // 按排序规则比较大小
    if (userAKey.rank !== userBKey.rank) {
        return userAKey.rank > userBKey.rank ? -1 : 1
    }
    if (userAKey.score !== userBKey.score) {
        return userAKey.score > userBKey.score ? -1 : 1
    }
    if (userAKey.loginTime !== userBKey.loginTime) {
        return userAKey.loginTime < userBKey.loginTime ? -1 : 1
    }
    // 极端情况：所有非ipv4字段都相同，按ipv4字符串比较保证返回值一致即可
    return String(userAKey.ipv4) > String(userBKey.ipv4) ? 1 : -1
});

调整后查询时只要ipv4填对，其他字段随便填都能正常查到节点：

console.log(tree.get(new Key(10, 0, 0, 0)));

方案2：实现符合要求的哈希函数 #

如果确实要转成单值哈希作为key，可以用BigInt避免数值溢出，按字段优先级拼接即可：

// 先把ipv4转成32位无符号整数
function ipToInt(ip) {
    return ip.split('.').reduce((int, oct) => (int << 8) + parseInt(oct, 10), 0) >>> 0;
}

function hash(ipv4, rank, score, loginTime) {
    // 按优先级从高到低分配bit位，可根据实际字段取值范围调整位移值
    const rankBits = BigInt(rank) << BigInt(105); // rank占最高16位
    const scoreBits = BigInt(score) << BigInt(73); // score占接下来32位
    const loginTimeBits = BigInt(-loginTime) << BigInt(32); // loginTime取负保证时间越小值越大，占接下来41位
    const ipBits = BigInt(ipToInt(ipv4)); // ipv4占最低32位，保证ipv4相同哈希值一定相同
    return rankBits | scoreBits | loginTimeBits | ipBits;
}

额外优化建议 #

如果需要频繁按ipv4查询用户，可以额外维护一个Map<ipv4, OnlineUser>的索引，查询时直接走Map，O(1)性能比红黑树更好，红黑树仅用于维护排序后的用户列表用于展示，两个数据结构同步增删即可，逻辑更清晰，性能也更高。

内容的提问来源于stack exchange，提问作者Hussein Yaqoobi