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

Groups > comp.programming > #1396 > unrolled thread

double hashing

Back to article view | Back to comp.programming

Contents

  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

#1396 — double hashing

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]

[toc] | [next] | [standalone]

#1397

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.

[toc] | [prev] | [next] | [standalone]

#1443

On Tuesday, 3 April 2012 01:19:06 UTC+5:30, 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]



On Tuesday, 3 April 2012 01:19:06 UTC+5:30, 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]

Since contracted info is a subset of expanded doc, and if the processing of contracted info from expanded info is order of constant then just maintain a single structure "struct expdocinfo { ... };" and a single Hash Table for it. 

Else
Keep a structure docInfo and keep both condocinfo{} and expdocinfo{} inside it and maintain a single Hash table with the value as a pointer to the docInfo object;

struct docInfo
{
   struct expdocinfo{} expDocInfoObj;
   struct condocinfo{} conDocInfoObj;
};

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web