1 year ago

#325080

test-img

longpeng1899

Compute the hashcodes of multiple different integer arrays, when appending several numbers at the end of each array, the hashcodes are all the same

For example, giving two arrays below:
int[] array1={80,103,142,91,160,250,7,7,7,7};
int[] array2={130,105,209,7,7,7,7};
except {7,7,7,7}, the numbers in the array are some random numbers which between 0 and 255.

Code:

    public static int hashCode(int[] array) {
        int total = 0;
        for (int element : array) {
            total = total * 256;
            total = total + element;
        }
        return total;
    }

    public static void main(String[] args) {
    int[] array1 = {80, 103, 142, 91, 160, 250, 7, 7, 7, 7};
    int[] array2 = {130, 105, 209, 7, 7, 7, 7};
    int hashCode1 = hashCode(array1);
    int hashCode2 = hashCode(array2);
    System.out.println("hashCode1: " + hashCode1);//117901063
    System.out.println("hashCode2: " + hashCode2);//117901063

    }

Adding the number of arrays from 2 to 100, as you append {7,7,7,7} at the end of the arrays, they still have the same hashCode.(Append {1,2,3,4} have the same effect)

Question: Why append several numbers at the end of the arrays, will cause they have the same hashCode?

I try to view the values in the debugger, but I still did not understand. Thanks in advance:)

Originally this question is from CS61B Spring 2018 HW3, it is asking to write a test to prove the provided hashCode function has poor distribution.
One way to complete this task is to append several numbers(e.g. {7,7,7,7}) at the end of the arrays.

What I've tried and what I've observed:

  1. make 100 arrays from {some random numbers,7,7,7,7,7,7,7} to
    {some random numbers,7}

Result: there are some arrays that have different hashCodes, but there are still too many arrays that have the same hashCode

  1. make 100 arrays from {some random numbers,7,7,7,7} to
    {7,7,7,7,some random numbers}

Result: there are some arrays that have different hashCode, but there are still too many arrays that have the same hashCodes

  1. make 100 arrays from {some random numbers,7,7,7,7} to
    {a random number,7, a random number,7, a random number,7}

Result: the distribution is good, there are not too many arrays that have the same hashcode

hashcode

hash-code-uniqueness

0 Answers

Your Answer

Accepted video resources