数字比较比字符串比较快吗？

java computer-science c++

2022-09-02 00:30:41

我听说散列（即将字符串或对象转换为数字）用于字符串等，因为比较数字比字符串更容易。如果这是真的，这是什么原因？

答案 1

情况未必如此，但大多数时候可能都是如此。

请考虑以下情况：

我想比较字符串“苹果”与“橙子”。如果我只是想确定“苹果”==“橙子”，我只需要比较每个字符串的第一个字符：'a'！='o'=>“苹果”！=“橙子”。如果我对字符串进行哈希处理，然后进行比较，则速度会明显变慢，因为我必须在比较结果整数之前解析两个字符串并将其馈送到哈希算法中。

但是，如果我需要多次进行这种比较，并且也许我将“橙子”与“猩猩”进行比较很多次，那么如果我对所有字符串进行一次哈希处理并多次进行整数比较，它将更快地工作。这是哈希映射所基于的原则。

但是，请注意，散列字符串对于直接相等比较很有用，它无法确定字符串在词法上是大于还是小于彼此，因此无法通过散列方法对字符串进行排序。（这就是为什么Java中的HashMap是无序的）。

答案 2

比较两个数字比比较两个字符串（表示相同的数字）快得多。比较两个数字只需要比较单个位，并且可以使用任何AND，XOR，2的补码等超快地完成。

比较两个字符串非常缓慢且昂贵。大多数算法需要迭代整个字符串并匹配每个字符。

例如，假设我们要将 9 与 12（假）进行比较。对于数值比较，我们假设算法比较单个位。9 = 1001 12 = 1100

在这里，最坏情况算法将比较4位。

现在，如果我们将“9”和“12”表示为字符串，它们将分别以16位的形式存储在内存中（回想一下：Java使用UTF-16来表示内存中的字符串），并且必须传递给字符串比较算法。实际上，Java的实际字符串比较函数如下：

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = offset;
            int j = anotherString.offset;
            while (n-- != 0) {
                if (v1[i++] != v2[j++])
                    return false;
            }
            return true;
        }
    }
    return false;
}

如您所见，字符串比较还有很多工作要做。