double hashing

From	jgk@panix.com (Joe keane)
Newsgroups	comp.programming, comp.lang.c
Subject	double hashing
Date	2012-04-02 19:49 +0000
Organization	Public Access Networks Corp.
Message-ID	<jlcvrh$2bh$1@reader1.panix.com> (permalink)

Cross-posted to 2 groups.

Show all headers | View raw

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]

Back to comp.programming | Previous | Next — 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