Вчера нашел в приложении интересный перформанс-баг. Ситуация следующая. Есть некий Hashtable и некий набор объектов. В определенных случаях объекты бывают почти одинаковыми, и их достаточно много (больше 1000 штук). Все они пихаются в этот Hashtable, где ключи - специальные объекты, у которых переопределены Equals и GetHashCode.
После этого обнаруживается, что работа с Hashtable занимает какое-то нереальное время. Даже если пробежать по всем ключам и для каждого просто сказать Assert.IsTrue(Hashtable.Contains(key)) - потратим несколько секунд!
Баг в том, что реализация GetHashCode ключа почти всегда возвращала одинаковые значения. Hashtable, по идее, должен строить бинарное дерево по хэш-кодам своих элементов. Если хэш-коды для каких-то объектов совпадают, то в соответствующий узел дерева кладутся все такие объекты в простом связном списке. А если разных хэш-кодов всего-то, скажем, два, то получаем два списка по 500 значений в каждом, поиск в которых выполняется тупым перебором.
