Searching for a key. The story so far…

Hashing

Hash Functions

Java Integer hashCode Method


    @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }

    public static int hashCode(int value) {
        return value;
    }

https://github.com/openjdk/jdk17/blob/master/src/java.base/share/classes/java/lang/Integer.java

Java String hashCode Method

Javadoc:

“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]\) using int arithmetic, where s[i] is the \(i\)th character of the string, and n is the length of the string. (The hash value of the empty string is zero.)”

    public int hashCode() {
        int h = hash;
        if (h == 0 && !hashIsZero) {
            h = isLatin1() ? StringLatin1.hashCode(value)
                           : StringUTF16.hashCode(value);
            if (h == 0) {
                hashIsZero = true;
            } else {
                hash = h;
            }
        }
        return h;
    }

https://github.com/openjdk/jdk17/blob/master/src/java.base/share/classes/java/lang/String.java

    public static int hashCode(byte[] value) {
        int h = 0;
        int length = value.length >> 1;
        for (int i = 0; i < length; i++) {
            h = 31 * h + getChar(value, i);
        }
        return h;
    }

https://github.com/openjdk/jdk17/blob/master/src/java.base/share/classes/java/lang/StringUTF16.java

Socrative Question

Does the String hashCode method guarantee that no two strings will hash to the same value? If not, is it possible to design a hashCode method that would have this property?

  1. Yes
  2. No, Yes
  3. No, No

Handling Collisions: Open Hashing/Separate Chaining

Hashing In Java

Socrative Quiz

What is the relationship between the equals method and the hashCode method in Java?

  1. Any time the equals method is overriden, hashCode should be as well. Hashing will break if two non-equal objects can have the same hash code.

  2. Any time the equals method is overriden, hashCode should be as well. Hashing will break if two equal objects can have different hash codes.

  3. Any time the equals method is overriden, hashCode should be as well. Hashing will be slow if two non-equal objects can have the same hash code.

  4. Any time the equals method is overriden, hashCode should be as well. Hashing will be slow if two equal objects can have different hash codes.

  5. There is no real relationship between equals and hashCode. It is fine to override one without considering the other.