earl@wright (Earl Killian) (11/04/88)
In article <623@quintus.UUCP>, ok@quintus (Richard A. O'Keefe) writes: >The one which is really painful is division. When one codes up a hash >table, one knows (having read the literature) that remainder with a >prime is a Good Thing. But one also knows that whizzbang machine X >has no hardware support for division, so to avoid a subroutine call to >a routine not known for its speed one sighs, puts in X & 4095 (instead >of X1 % 4097 or whatever), and wishes... I just wanted to point out that hashing by multiplication is often better than division (Knuth section 6.4), when you're not using chaining. It's probably about the same with chaining hash lookups. Besides, division is slow :-) --