Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.electronics.design > #403266

Re: Exhausted

Show all headers | View raw

On Fri, 18 Mar 2016 02:46:50 +1000, Piotr Wyderski  
<peter.pan@neverland.mil> wrote:

> Clifford Heath wrote:
>
>> Don't laugh - a distant colleague wrote a hash function that
>> inadvertently did that, and it got shipped in a product (long time ago).
>> It wasn't found until we were looking for an N**2 performance problem in
>> a hash table which it keyed - although the base vector was being
>> expanded, all elements were in the overflow chain of the first entry.
>
> If the application is required to produce composite hashes (i.e. merge
> two or more hashes and produce a new one), the bugs are even more
> subtle. I've seen using a simple xor on the input hashes, which is
> theoretically correct (if a and b are random, then a xor b is too),
> but fails badly if the element come in non-unique pairs, which is
> frequent. Then the result of a xor a is not as random as one would  
> expect... Also found using a profiler. :-)
>
> 	Best regards, Piotr
>
>
>
>
>
>

That method was suggested by Shannon. He also predicted the bug you found.  
If the data is correlated than Shannon's method makes it worse.

Back to sci.electronics.design | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Exhausted  "David Eather" <eather@tpg.com.au> - 2016-03-16 15:53 +1000
  Re: Exhausted Klaus Kragelund <klauskvik@hotmail.com> - 2016-03-16 01:07 -0700
  Re: Exhausted George Herold <gherold@teachspin.com> - 2016-03-16 06:04 -0700
    Re: Exhausted "David Eather" <eather@tpg.com.au> - 2016-03-17 00:16 +1000
      Re: Exhausted Allan Herriman <allanherriman@hotmail.com> - 2016-03-16 16:35 +0000
        Re: Exhausted George Herold <gherold@teachspin.com> - 2016-03-16 11:15 -0700
          Re: Exhausted Allan Herriman <allanherriman@hotmail.com> - 2016-03-17 12:11 +0000
      Re: Exhausted mrdarrett@gmail.com - 2016-03-17 10:37 -0700
        Re: Exhausted "David Eather" <eather@tpg.com.au> - 2016-03-18 07:25 +1000
          Re: Exhausted mrdarrett@gmail.com - 2016-03-17 15:05 -0700
    Re: Exhausted Winfield Hill <hill@rowland.harvard.edu> - 2016-03-16 07:32 -0700
      Re: Exhausted George Herold <gherold@teachspin.com> - 2016-03-16 08:04 -0700
        Re: Exhausted Winfield Hill <hill@rowland.harvard.edu> - 2016-03-16 08:16 -0700
        Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-16 10:32 -0700
          Re: Exhausted George Herold <gherold@teachspin.com> - 2016-03-16 11:08 -0700
            Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-16 12:30 -0700
              Re: Exhausted Clifford Heath <no.spam@please.net> - 2016-03-17 06:47 +1100
                Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-16 17:01 -0700
                Re: Exhausted Clifford Heath <no.spam@please.net> - 2016-03-17 07:01 +1100
                Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-16 17:27 -0700
                Re: Exhausted Piotr Wyderski <peter.pan@neverland.mil> - 2016-03-17 17:35 +0100
                Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-17 10:13 -0700
                Re: Exhausted Clifford Heath <no.spam@please.net> - 2016-03-18 11:38 +1100
                Re: Exhausted dplatt@coop.radagast.org (Dave Platt) - 2016-03-16 17:17 -0700
                Re: Exhausted Lasse Langwadt Christensen <langwadt@fonz.dk> - 2016-03-16 17:21 -0700
                Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-16 17:39 -0700
                Re: Exhausted "Tim Williams" <tiwill@seventransistorlabs.com> - 2016-03-16 21:24 -0500
                Re: Exhausted Phil Hobbs <pcdhobbs@gmail.com> - 2016-03-16 20:51 -0700
                Re: Exhausted George Herold <gherold@teachspin.com> - 2016-03-16 20:21 -0700
                Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-16 21:16 -0700
                Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-16 17:34 -0700
                Re: Exhausted "David Eather" <eather@tpg.com.au> - 2016-03-18 07:31 +1000
                Re: Exhausted rickman <gnuarm@gmail.com> - 2016-03-17 00:01 -0400
                Re: Exhausted Clifford Heath <no.spam@please.net> - 2016-03-17 14:09 +1100
                Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-17 09:01 -0700
                Re: Exhausted Piotr Wyderski <peter.pan@neverland.mil> - 2016-03-17 17:46 +0100
                Re: Exhausted "David Eather" <eather@tpg.com.au> - 2016-03-18 07:33 +1000
                Re: Exhausted "David Eather" <eather@tpg.com.au> - 2016-03-18 07:35 +1000
                Re: Exhausted Piotr Wyderski <peter.pan@neverland.mil> - 2016-03-18 11:44 +0100
      low-voltage low-current noise sources Winfield Hill <hill@rowland.harvard.edu> - 2016-03-16 08:10 -0700
  Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-16 08:35 -0700
    Re: Exhausted "David Eather" <eather@tpg.com.au> - 2016-03-18 07:52 +1000
      Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-17 15:35 -0700
        Re: Exhausted "David Eather" <eather@tpg.com.au> - 2016-03-18 09:09 +1000
          Re: Exhausted John Larkin <jjlarkin@highlandtechnology.com> - 2016-03-17 16:54 -0700
          Re: Exhausted George Herold <gherold@teachspin.com> - 2016-03-17 17:40 -0700
            Re: Exhausted mixed nuts <melopsitticus@undulatus.budgie> - 2016-03-17 22:37 -0400
        Re: Exhausted "David Eather" <eather@tpg.com.au> - 2016-03-18 09:09 +1000
        Re: Exhausted George Herold <gherold@teachspin.com> - 2016-03-17 17:29 -0700

csiph-web