0

For example, if I am hashing integers and my hashing function is simply (n % 10) then the number 17 and the number 27 will produce the same result. This does not mean that those numbers are the same.

Now, assuming the n%10 is my hashing function, my question is: If I input the following numbers by the following order, how will the numbers be outputed since they are sorted by their hashcode ?

Numbers: 10, 27, 17, 38, 58, 28, 43

Arthur
  • 171
  • 6
  • 5
    Why don't you give it a try? – sleepToken Jan 29 '20 at 18:35
  • 3
    Why are you sorting integers by their hashcodes? – nylanderDev Jan 29 '20 at 18:35
  • 3
    `10, 43, [27, 17], [38, 58, 28]` where numbers in square brackets can interchange position, depending on the implementation details of the sorting algorithm, and the original position in the list – Michael Jan 29 '20 at 18:37
  • The whole purpose of hash code is, that 2 objects will be considered the same as soon as their hash code is the same. – C.B. Jan 29 '20 at 18:39
  • the output order depends on the "stability" of the sorting algorithm (see https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important) ...with e.g. quicksort, you "cannot make any predictions"... but you could sort not only by the hashcode, but also by an additional property/value/function (e.g. the int value) ... ;) – xerx593 Jan 29 '20 at 18:40
  • By the way, `n % 10` is a bad hash function for integers. You are reducing the available number of hash codes by about a factor of 1 billion. This makes hash collisions a near certainty. For reference, `Integer.hashCode` just returns the integer value. – Michael Jan 29 '20 at 18:42
  • @xerx593 It is not really accurate to say "*you cannot make any predictions*". Any sane implementation is not going to be random. It will be deterministic; you will get the same output for the same input. With enough scrutiny of the algorithm, it is certainly *possible* to predict, and with absolute certainty. However, those are implementation details that the contract makes no guarantees about. – Michael Jan 29 '20 at 18:46
  • 3
    @C.B. Not quite. Objects that are equal must return the same hash code, but different objects can also return the same hash code. No matter how good your hashing algorithm, hash collisions are a thing. – azurefrog Jan 29 '20 at 18:46
  • 1
    I'm confused. Are you asking how java sorts objects? And what happens when two of them have identical hashcodes? – Scratte Jan 29 '20 at 18:46
  • you are right, @Michael, it was not accurate... :) better would be "difficult to predict" ...or "as complex/simple as running it". ..but I hope you/all get my point about "stability" – xerx593 Jan 29 '20 at 18:52
  • Does this answer your question? [Stable sort - do we really need it?](https://stackoverflow.com/questions/32711035/stable-sort-do-we-really-need-it) – Progman Jan 29 '20 at 20:35
  • @azurefrog Yes, there is hash collisions, that's why I wrote "will be considered the same" rather than "are guaranteed to be the same" – C.B. Jan 29 '20 at 23:31

1 Answers1

1

I think you may be confused as to what hashCode() is used for in Java.

Sorting does not generally rely on equals() and hashCode(). They're used to identify equality. For example HashSet will use these two methods to identify equality only. TreeSet also uses both methods to identify equality, but they're not used to sort the elements.

Sorting needs a way to compare objects, and for that (only considering Java SE) it's either required that the class implements Comparable and therefore has a compareTo(Object o) method, or that a Comparator is provided for the sorting algorithm.

So assuming you're sorting the integers using a method in Java SE, like Arrays.sort(), then the hashCode will not be considered and your integers will come out according to the compareTo() of the class or a provided Comparator.

Scratte
  • 3,056
  • 6
  • 19
  • 26