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

Groups > comp.programming > #1397

Re: double hashing

Cross-posted to 2 groups.

Show all headers | View raw

On 4/2/12 12:49 PM, Joe keane wrote:
> question
>
> We some have 'docs' that can be 'contracted' or 'expanded'.
>
> They sometimes change from contracted to expanded and vice versa.
>
> They each have a 'key' that's unique [and doesn't change when they
> change state].
>
> struct condocinfo { ... };
> struct expdocinfo { ... };
>
> The info for an expanded doc is a superset of the info for a contracted doc.
> [e.g., pointers to more structures].
>
> Lookup by key.
>
> Scheme 1
>
> We keep a hash table for all docs that contains the info for contracted
> docs.  We keep a hash table for only expanded docs that contains the
> info for expanded docs that's not in the first one.
>
> Scheme 2
>
> We keep a hash table for only contracted docs that contains the info for
> contracted docs.  We keep a hash table for only expanded docs that
> contains the info for expanded docs.
>
> Time?  Space?
>
> [it's for an old project so it's academic]

I'm mostly a Java programmer, so my first instinct is to just make 
expdoc extend condoc, but that doesn't work in C :-).

I would probably go for scheme 3: Keep a single hash table where the 
value is a structure with two pointers, one to the condensed and one to 
the expanded.

My personal preference is:
   Correct first, easy second, fast third.

If it isn't correct, it's not worth doing.
If it isn't easy, it's hard to improve or maintain it.
If it isn't fast, at least its easy, so speeding it up should be easier.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

double hashing jgk@panix.com (Joe keane) - 2012-04-02 19:49 +0000
  Re: double hashing Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-04-02 13:02 -0700
  Re: double hashing Udit Gangwani <uditg22@gmail.com> - 2012-04-06 03:34 -0700

csiph-web