[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

1120.0. "Rating a Hashing function" by TRACE::GILBERT (Ownership Obligates) Fri Sep 15 1989 14:27

Is there a formula for rating a hashing function?  Hashing a set of values
should give a set of numbers uniformly distributed in the range 0..N-1.
Given the distribution, the number of numbers that fall into each of these
N buckets, how may the uniformity of the distribution be rated?

T.R Title User Personal
Name Date Lines

1120.1 I've seen... VMSDEV::HALLYB The Smart Money was on Goliath Fri Sep 15 1989 14:54 7

T.R	Title	User	Personal Name	Date	Lines
1120.1	I've seen...	VMSDEV::HALLYB	The Smart Money was on Goliath	`Fri Sep 15 1989 14:54`	7
	I suppose you could use a chi-square test, but that ignores the inner workings of the hash function. Typically you would run empirical tests with the table 95% loaded, and compute the mean (and max) number of probes to look up an entry. John
1120.2	Simulate input distribution, then use chi-square	COOKIE::PBERGH	Peter Bergh, DTN 523-3007	`Fri Sep 15 1989 16:49`	33

    I suppose you could use a chi-square test, but that ignores the inner
    workings of the hash function.
    
    Typically you would run empirical tests with the table 95% loaded,
    and compute the mean (and max) number of probes to look up an entry.
    
      John

1120.2 Simulate input distribution, then use chi-square COOKIE::PBERGH Peter Bergh, DTN 523-3007 Fri Sep 15 1989 16:49 33