double hashing

[Joe keane]

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]

 

[Daniel Pitts]

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.

 

[Tim Rentsch]

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 would devise an approach that uses a single hash table
rather than two. There are various ways of doing this,
depending on whether the differentiating information can
be put in the structs themselves or needs to be extrinsic.