Is Java's hashCode method for String class computed in constant time or linear time? What is the algorithm used?
1
-
4How about reading the javadoc?assylias– assylias2016-01-21 05:44:48 +00:00Commented Jan 21, 2016 at 5:44
Add a comment
|
3 Answers
The documentation tells you the function:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
It's computed once using a linear-time pass, and then cached so it's only O(1) to retrieve it in the future.
1 Comment
assylias
Unless the result is 0 ;-)
According to the docs
public int hashCode()
Returns a hash code for this string. The hash code for a String object is computed as
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
As you can see, the time complexity is the O(n) where n is the number of characters in the string. After one pass, it is cached so the time complexity is effectively O(1).
1 Comment
cubuspl42
This answer is incomplete/misleading, because it doesn't take caching into consideration. The caching makes the complexity effectively amortized O(1).
Time Complexity of Object::hashCode method is O(1), because it has no any interaction with the data of your object. It is a native method and written with C language. The integer value which is returned, is probably heap memory address with some modifications (bitwise operations) since every address in memory representing unique value.
For example 4GB memory addresses will be represented in hexadecimal format from 0x00000000 to 0xffffffff range and each of this value is unique. Thus, Java does not require extra computation to ensure uniqueness of these values. Therefore hashCode gives constant time complexity.
