1

我在客户端有一棵树，在 javascript 中：

function Node(uuid, someData, versionNum) {
   this.uuid = uuid;
   this.someData = someData;
   this.versionNum = versionNum;
   this.childNodes = [];
}

和服务器中的同一棵树，在java中：

public class Node {
   UUID uuid;
   String someData;
   int versionNum;
   List<Node> childNodes;
}

客户端将每五秒向服务器发送一个请求，请求树的哈希值。这个想法是树的哈希将像这样递归计算：

public static long hashSubtree(Node node) {
    long hash = node.uuid.getMostSignificantBits() ^ node.uuid.getLeastSignificantBits() ^ node.versionNum;
    for (Node childNode : node.childNodes)
        hash ^= hashSubtree(childNode);
    return hash;
}

在客户端上，一旦它收到来自服务器的响应，使用服务器计算的哈希值，客户端将计算其本地树的自己的哈希值：

function hashSubtree(node) {
    var hash = getMostSignificantBitsAsInt(node.uuid) ^ getLeastSignificantBitsAsInt(node.uuid) ^ node.versionNum;
    for (var i = 0; i < node.childNodes.length; i++)
        hash ^= hashSubtree(node.childNodes[i]);
    return hash;
}

然后客户端将比较两个哈希码。如果两个哈希码不同，则客户端与服务器不同步，将请求整个树。

问题：

由于精度绝对重要，我需要确保 javascript 始终处理整数，并且永远不会将任何内容转换为浮点数。假设如果我继续像这样使用 xor，那么它永远不会变成浮点数是否可以保存？

或者也许有比使用 xor 散列来比较树更好的方法？

4

1 回答 1

2

在 Javascript 中，原始数字不是 32 位整数，变量在任何两种类型之间都不会改变；他们总是Numbers：

Number 类型正好有 18437736874454810627（即 264−253+3）个值，代表二进制浮点算术的 IEEE 标准中指定的双精度 64 位格式 IEEE 754 值，除了 9007199254740990（即, 253−2) IEEE 标准的不同“非数字”值在 ECMAScript 中表示为单个特殊的 NaN 值。

这意味着不同整数的支持范围基本上是 –2 53到 2 53。

这与Java 的 double也符合相同的规范，因此可以最准确地与之进行比较。

我不知道你getMostSignificantBitsAsInt做getLeastSignificantBitsAsInt什么，但如果他们将 Number解释为 32 位整数，你应该没问题——即使它不是。

如果尚未完成和测试，这可能比它的价值更多，但您可以使用 Javascript 的位运算符来完成它，它将操作数视为 32 位整数，这正是您正在寻找的。（具体来说，他们规范要求在应用运算符之前对每个操作数调用ToInt32 。）

我会使用这些操作数编写一些方法来完成此任务，为这些方法编写一些测试用例，您的方法应该可以工作。当然，正如你所说，精度非常重要，所以我会对所有部分进行单元测试。

最后一点，你还没有说你的基本目标是什么，但是你能通过寻找一个“更小的”身份认同感来实现你的目标吗？我不愿意对基础不稳定的算法施加任何形式的压力（关于性能或准确性）。

于 2013-10-01T02:26:58.690 回答