Re: double hashing

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!npeer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
From	Udit Gangwani <uditg22@gmail.com>
Newsgroups	comp.programming
Subject	Re: double hashing
Date	Fri, 6 Apr 2012 03:34:08 -0700 (PDT)
Organization	http://groups.google.com
Lines	80
Message-ID	<15658470.404.1333708448259.JavaMail.geo-discussion-forums@pbbol8> (permalink)
References	<jlcvrh$2bh$1@reader1.panix.com>
NNTP-Posting-Host	121.243.147.6
Mime-Version	1.0
Content-Type	text/plain; charset=ISO-8859-1
X-Trace	posting.google.com 1333708526 29217 127.0.0.1 (6 Apr 2012 10:35:26 GMT)
X-Complaints-To	groups-abuse@google.com
NNTP-Posting-Date	Fri, 6 Apr 2012 10:35:26 +0000 (UTC)
In-Reply-To	<jlcvrh$2bh$1@reader1.panix.com>
Complaints-To	groups-abuse@google.com
Injection-Info	glegroupsg2000goo.googlegroups.com; posting-host=121.243.147.6; posting-account=U0_gigoAAACv7D4JcWRQdSx-ike7j7tv
User-Agent	G2/1.0
X-Received-Bytes	3518
Xref	csiph.com comp.programming:1443

Show key headers only | View raw

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;
};

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