数字比较比字符串比较更快?

我听说哈希(即将字符串或对象转换为数字)用于字符串,因为它比字符串更容易比较数字。 如果是真的,这是什么原因?

情况不一定如此,但大多数情况下可能就是这种情况。

考虑以下情况:

我想比较字符串“apples”和“oranges”。 如果我只想确定“apples”==“oranges”,我只需要比较每个字符串的第一个字符:’a’!=’o’=>“apples”!=“oranges”。 如果我对字符串进行散列然后进行比较,那么它要慢得多,因为我必须解析两个字符串并在比较结果整数之前将它们提供给散列算法。

但是,如果我需要多次进行这种比较,也许我将“橘子”与“猩猩”进行了很多比较,那么如果我将所有字符串一次性地哈希并多次进行整数比较,那么它就可以解决了快点。 这是哈希映射所基于的原则。

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

比较两个数字的速度比比较两个数字(表示相同的数字)要快。 比较两个数字只需要比较各个比特,并且可以使用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; } 

正如您所看到的,String的比较还有很多。

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

通常,大多数计算机只有一条指令来比较整数,长整数等,并且最多需要几个指令周期。 字符串通常通过效用函数/方法进行比较(此规则可能有奇怪的例外)。

例如,在Java中,String基本上表示为

  /** 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方法同时执行此== anObjectn == anotherString.count ,两者基本上都是整数比较,甚至在它开始比较字符之前。 整数比较需要比单个指令花费更长的时间


C字符串比较比Java等价物更简单/更快 ,但它将包含某种循环和每次循环的多个指令。

这将比Integer Compare需要的一条指令花费更长的时间

是的,但这与散列无关。

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

比较字符串涉及(a)迭代两个字符串,直到找到不同的字符(不同于固定大小的数字)和(b)许多Unicode魔术(不同长度的不同字符串实际上可以相等,不同代码中的不同字符)块比较不同)。


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