20

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

4

5 回答 5

34

不一定是这种情况，但大多数时候可能是这种情况。

考虑以下情况：

我想比较字符串“apples”和“oranges”。如果我只想确定 "apples" == "oranges"，我只需要比较每个字符串的第一个字符：'a' != 'o' => "apples" != "oranges"。如果我对字符串进行哈希处理然后进行比较，它会明显变慢，因为我必须在比较结果整数之前解析两个字符串并将它们输入哈希算法。

但是，如果我需要多次进行这种比较，并且可能我经常将“橙子”与“猩猩”进行比较，那么如果我对所有字符串进行一次哈希处理并多次比较整数，它就会解决快点。这是哈希映射所基于的原理。

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

于 2013-05-12T05:56:27.037 回答
15

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

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

例如，假设我们想比较 9 和 12（假）。对于数字比较，我们假设算法比较单个位。9 = 1001 12 = 1100

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

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

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;
}

正如你所看到的，字符串比较还有很多事情要做。

于 2013-05-12T03:24:16.553 回答
1

比较原始数字肯定比比较字符串快，因为它只是一条计算机指令，而在 Java 中比较字符串是一种方法。但是在 Java 中使用散列是出于不同的原因，Object.hashCode() 用于散列表中以在集合中快速搜索。

于 2013-05-12T02:56:44.653 回答
1

一般来说，大多数计算机都有一条指令来比较整数、长整数等，最多需要几个指令周期。字符串通常由实用函数/方法进行比较（此规则可能存在奇怪的例外）。

例如，在 Java 中，字符串基本上表示为

     /** The value is used for character storage. */
     private final char value[];

     /** The offset is the first index of the storage that is used. */
     private final int offset;

     /** The count is the number of characters in the String. */
     private final int count;

而equals方法是

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;

equals 方法执行this == anObject和n == anotherString.count，两者本质上都是整数比较，甚至在它开始比较字符之前。这将比整数比较所需的单个指令花费更长的时间

C 字符串比较比等效的Java更简单/更快，但它将包含某种循环和每次通过循环的多条指令。

这将比整数比较所需的一条指令花费更长的时间

于 2013-05-12T04:25:04.943 回答
0

是的，但这与散列无关。

比较数字涉及比较位的简单硬件指令。

比较字符串包括 (a) 遍历两个字符串，直到找到不同的字符（与数字不同，它是固定大小的）和 (b) 大量 Unicode 魔法（不同长度的不同字符串实际上可以相等，并且不同代码中的不同字符块比较不同）。

散列通常用于将字符串转换为数组索引。

于 2013-05-12T02:52:28.477 回答