在 Java 中，对于字符串 x，s.length() 的运行时成本是多少？是 O(1) 还是 O(n)？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/254726/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
In Java, for a string x, what is the runtime cost of s.length()? Is it O(1) or O(n)?
提问by someguy
I've been told that code such as:
有人告诉我，代码如：
for (int i = 0; i < x.length(); i++) {
// blah
}
is actually O(n^2) because of the repeated calls to x.length(). Instead I should use:
实际上是 O(n^2) 因为重复调用x.length(). 相反，我应该使用：
int l = x.length();
for (int i = 0; i < l; i++) {
// blah
}
Is this true? Is string length stored as a private integer attribute of the String class? Or does String.length()really walk the whole string just to determine its length?
这是真的？字符串长度是否存储为 String 类的私有整数属性？或者String.length()真的只是为了确定它的长度而遍历整个字符串？
回答by sblundy
No, the length of a java string is O(1) because java's string class stores the length as a field.
不，java 字符串的长度是 O(1)，因为 java 的字符串类将长度存储为字段。
The advice you've received is true of C, amongst other languages, but not java. C's strlen walks the char array looking for the end-of-string character. Joel's talked about it on the podcast, but in the context of C.
您收到的建议适用于 C，以及其他语言，但不适用于 Java。C 的 strlen 遍历 char 数组以查找字符串结尾字符。乔尔在播客上谈到了它，但在 C.
回答by Alexander
Contrary to what has been said so far, there is no guarantee that String.length()is a constant time operation in the number of characters contained in the string. Neither the javadocs for the Stringclass nor the Java Language Specification require String.lengthto be a constant time operation.
与目前所说的相反，不能保证String.length()字符串中包含的字符数是一个常数时间操作。String类的 javadoc和 Java 语言规范都不需要String.length是恒定时间操作。
However, in Sun's implementation String.length()is a constant time operation. Ultimately, it's hard to imagine why any implementation would have a non-constant time implementation for this method.
但是，在 Sun 的实现中String.length()是一个常数时间操作。最终，很难想象为什么任何实现都会为这种方法提供非常量时间实现。
回答by Satish
String stores the length in a separate variable. Since string is immutable, the length will never change. It will need to calculate the length only once when it is created, which happens when memory is allocated for it. Hence its O(1)
字符串将长度存储在一个单独的变量中。由于字符串是不可变的，因此长度永远不会改变。它只需要在创建时计算一次长度，当为它分配内存时就会发生这种情况。因此它的 O(1)
回答by Allain Lalonde
In the event you didn't know you could write it this way:
如果你不知道你可以这样写：
for (int i = 0, l = x.length(); i < l; i++) {
// Blah
}
It's just slightly cleaner since l's scope is smaller.
由于l的范围更小，因此它稍微干净一点。
回答by Marcus Downing
You should be aware that the length()method returns the number of UTF-16 code points, which is not necessarily the same as the number of characters in all cases.
您应该知道该length()方法返回的是 UTF-16 代码点的数量，它不一定与所有情况下的字符数相同。
OK, the chances of that actually affecting you are pretty slim, but there's no harm in knowing it.
好吧，这实际上影响你的可能性很小，但知道它没有坏处。
回答by Daniel Spiewak
I don't know how well the link will translate, but see the source of String#length. In short, #length()has O(1) complexity because it's just returning a field. This is one of the many advantages of immutable strings.
我不知道该链接将如何翻译，但看到的来源String#length。简而言之，#length()具有 O(1) 复杂度，因为它只是返回一个字段。这是不可变字符串的众多优点之一。
