[prev in list] [next in list] [prev in thread] [next in thread] 

List:       linux-vlan
Subject:    [VLAN] Re: The device name hash at 0.0.13
From:       Matti Aarnio <matti.aarnio () zmailer ! org>
Date:       2000-10-27 12:07:03
[Download RAW message or body]

On Thu, Oct 26, 2000 at 11:13:30PM -0700, Ben Greear wrote:
> Matti Aarnio wrote:
> > Ben,
... 
> What, you don't think this is a thing of beauty?? **GRIN**
> 
> Lets work towards your crc version..  Were you going to try to generalize
> the crc stuff anyway?  Perhaps the name hash & crc code could be part of
> the same patch...

	One quite nice looking hash produced nasty surprise when fed
	lowercase alphanumeric strings of up to 8 chars, then hashed
	modulo (26*26) -- 3/4 of entire result space was not used at
	all, and usage distribution was non-uniform.

	I am always suspicuous about varying hash functions if not
	shown how it will work.  Usually I am rather happy with crc32(),
	but lets see...

	crc32() for "vlan0000" thru "vlan4095" modulo 256 produces 4
	(FOUR!) different buckets!  Very bad result for this input.

	Your function produces 256 buckets with varying population
	counts:

		14: 27%
		15: 26%
		16: 18%
		17:  3%
		18:  5%
		19: 10%
		20:  7%
		21:  1%

	Ok, optimal uniform distribution would result from 16 elts
	in each bucket.  As things go, that is not bad.

	However if we take just VLANs 0..255 and add them 16 virtual
	interfaces each (vlan0002:0 .. vlan0002:15), then we get very
	bad distributions for your function, but similarly bad also
	for the crc32() :-/



	Knuth has written a lot about hashing, as have others too.
	I will revisit the issue latter.

> Ben Greear (greearb@candelatech.com)  http://www.candelatech.com
> http://scry.wanfear.com               http://scry.wanfear.com/~greear

/Matti Aarnio

_______________________________________________
VLAN mailing list  -  VLAN@Scry.WANfear.com
http://www.WANfear.com/mailman/listinfo/vlan
VLAN Page:  http://scry.wanfear.com/~greear/vlan.html

[prev in list] [next in list] [prev in thread] [next in thread]