CODEWITHSUNDEEP
java
Ramesh Singh
Ramesh Singh

Reputation: 137

What is the time complexity of Java hashCode method for the String class?

Is Java's hashCode method for String class computed in constant time or linear time? What is the algorithm used?

Upvotes: 7

Views: 5912

Answers (3)

Aramazd
Aramazd

Reputation: 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.

Upvotes: 0

Atri
Atri

Reputation: 5831

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).

Upvotes: 3

Louis Wasserman
Louis Wasserman

Reputation: 198093

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.

Upvotes: 10

Related Questions