Stupid Bugs: Implementing Comparators

about | archive

[ 2005-July-27 13:45 ]

Many libraries require users to implement comparator functions/methods in order to impose a custom order on a collection. For example, Java's PriorityQueue requires a Comparator, as does Python's list.sort method. These functions follow the form required by the venerable qsort function from the C Standard Library. They return a negative integer if the first parameter is less than the second, a positive integer if it is greater than the second, or zero if they are equal. This seems simple, but there is one very important requirement: the comparison must be consistent between runs, otherwise you can get some strange behaviour. I ran into this issue because I used Java's Object.hashCode() as the "last resort" comparison to enforce Object equality on my custom object. However, I forgot that an instance's hashCode can vary between runs since it is based on its memory address. Thus, I was getting slightly different orderings of objects when I reran my program. I didn't care what order was chosen, but I needed a predictable order. This led to a very subtle and difficult bug. The lesson here is do not use memory addresses, or other unpredictable values, to sort objects.