Могут ли элементы, не равные по equals(), иметь одинаковый hashCode()

Да, могут. По контракту hashCode() в Java:

1. Если obj1.equals(obj2) == true, то obj1.hashCode() == obj2.hashCode()
2. Обратное необязательно – разные объекты могут иметь одинаковый хеш-код (коллизия).

Пример:

String s1 = "Aa";  
String s2 = "BB";  
System.out.println(s1.hashCode()); // 2112  
System.out.println(s2.hashCode()); // 2112  
System.out.println(s1.equals(s2)); // false  

Здесь строки разные (equals() = false), но hashCode() совпадает. Это допустимо, хотя может снижать производительность хеш-коллекций.