Print the number of unique pairs Stored in a HashSet

I'm trying to solve this fairly straight forward challenge:


Problem Statement


In computer science, a set is an abstract data type that can store
certain values, without any particular order, and no repeated
values. {1,2,3} is an example of a set, but {1,2,2} is not
a set. Today you will learn how to use sets in java by solving this
problem.


You are given n pairs of strings. Two pairs (a,b) and (c,d) are
identical if a=b and c=d. That also implies (a,b) is not same as
(b,a). After taking each pair as input, you need to print number of
unique pairs you currently have.


Note: Brute force solution will not earn full points.

This works, but I'm getting a timeout on the last test case (10.000 elements to go through).

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        Set pairs = new HashSet<>();
        final int N = s.nextInt();

        for(int i = 0; i < N; i++) {
            String first = s.next();
            String second = s.next();

            pairs.add(new Pair(first, second));
            System.out.println(pairs.size());
        }       
    }

    public static class Pair {
        String first, second;
        Pair(String first, String second) {
            this.first = first;
            this.second = second;
        }

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

        @Override public boolean equals(Object other) {
            if (other == this) {
                return true;
            }
            if (!(other instanceof Pair)) {
                return false;
            }

            Pair otherPair = (Pair) other;
            return (first.equals(otherPair.first) && second.equals(otherPair.second))
                || (first.equals(otherPair.second) && second.equals(otherPair.first));
        }

    }
}

Clearly, janos solution is the simplest, but it'd probably break for the input

a b
a  b

Moreover, it circumvents the learning effect (I guess, it's about learning to write a class with equals and hashCode).

As often, Lombok makes it trivial:

@EqualsAndHashCode
public static class Pair {
    private final String first, second;
}

hashCode

The inefficiency was most probably caused by

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

which is correct, but leads to many collisions due to ignoring second. Something like

return first.hashCode() + 123456789 * second.hashCode();

would solve it (the multiplier should be odd, anything else doesn't matter much).

equals

return (first.equals(otherPair.first) && second.equals(otherPair.second))
            || (first.equals(otherPair.second) && second.equals(otherPair.first));

This contradicts the part


implies (a,b) is not same as (b,a).

If it ever worked, then only because of the asymmetry in hashCode.

Why?

Two equals objects must have the same hashCode, otherwise the HashSet doesn't work properly (as the hash determines the index where the lookup starts). Violating this rule is a serious bug with which you may spend many funny debugging days.

This time, it helped you. After

set.put(new Pair("a", "b"));

the query

set.contains(new Pair("b", "a"));

erroneously returns false, although according to equals, the pair is there. However, it doesn't get found due to the non-equal hashCode. Analogously, after

set.put(new Pair("b", "a"));

you managed to contradict


set is an abstract data type that can store certain values, without any particular order, and no repeated values.

Note that this is not guaranteed to happen as the hashes may coincide and only a part of them gets used.

StackExchange Code Review Q#90932, answer score: 6