On Thu, 2 May 2002, Alexander Frink wrote:
On Tue, 30 Apr 2002, Richard B. Kreckel wrote:
suggesting an improvement of a factor 260 or 270. At the same time, the timings got only very marginally better, indicating that there is nothing to be gained by better hash functions, even perfect collision-free ones (if they would exist), since deep traversals caused by equal objects outweight deep traversals caused by hash collisions of different objects.
Did you also measure the ratio between comparisons which turn out to be equal to those turning out to be different?
Why does this matter? I mean, sure, the comparisons which turn out to be equal are the ones that dominate. They are about three orders of magnitude more frequent than the ones that turn out to be different. This is why enhancements to the hashing are not going to help any more. Cheers -richy. -- Richard B. Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>