Dynamic Hash Tables (Desperate Help needed)

Dynamic Hash Tables (Desperate Help needed)

Post by Gustavo Ri » Fri, 14 Mar 2003 08:19:27



Hi folks!

I am in need for this article (Dynamic Hash Tables), authored by
Per-Ake Larson!
I would like to known if anyone here get in hands a ps/pdf version of
it and would not bother sending me a copy of it.

Thanks a lot for your time and cooperation.
best regards.

 
 
 

Dynamic Hash Tables (Desperate Help needed)

Post by Marc Rochkin » Fri, 14 Mar 2003 08:52:21


Well, assuming you are DESPERATE, in 5 min. I found the article on the ACM
web site for $10. I used Google to find a reference to the article (CACM v.
31 #4) and then to the ACM Digital Library.

--Marc


Quote:> Hi folks!

> I am in need for this article (Dynamic Hash Tables), authored by
> Per-Ake Larson!
> I would like to known if anyone here get in hands a ps/pdf version of
> it and would not bother sending me a copy of it.

> Thanks a lot for your time and cooperation.
> best regards.


 
 
 

Dynamic Hash Tables (Desperate Help needed)

Post by Gustavo Ri » Sat, 15 Mar 2003 04:45:51



> Well, assuming you are DESPERATE, in 5 min. I found the article on the ACM
> web site for $10. I used Google to find a reference to the article (CACM v.
> 31 #4) and then to the ACM Digital Library.

> --Marc



> > Hi folks!

> > I am in need for this article (Dynamic Hash Tables), authored by
> > Per-Ake Larson!
> > I would like to known if anyone here get in hands a ps/pdf version of
> > it and would not bother sending me a copy of it.

> > Thanks a lot for your time and cooperation.
> > best regards.

That's the point: I am not considering paying $10 for this paper!

The question still remains!

 
 
 

Dynamic Hash Tables (Desperate Help needed)

Post by Fao, Sea » Sun, 16 Mar 2003 11:22:52


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Quote:> Hi folks!

> I am in need for this article (Dynamic Hash Tables), authored by
> Per-Ake Larson!
> I would like to known if anyone here get in hands a ps/pdf version
> of it and would not bother sending me a copy of it.

Is this what you're looking for?

http://portal.acm.org/citation.cfm?id=42410&dl=ACM&coll=portal&CFID=11
111111&CFTOKEN=2222222

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>

iQA/AwUBPnKOeV1PNzyp+Ow+EQLHIQCgx4a7UiBHy/pXPJlRecQQ52gNKxEAoLlu
o5FdOfA5LQQILlYLZbn75NFR
=qHPt
-----END PGP SIGNATURE-----

 
 
 

Dynamic Hash Tables (Desperate Help needed)

Post by David Schwart » Sun, 16 Mar 2003 11:29:41



> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1



> > Hi folks!

> > I am in need for this article (Dynamic Hash Tables), authored by
> > Per-Ake Larson!
> > I would like to known if anyone here get in hands a ps/pdf version
> > of it and would not bother sending me a copy of it.

        There are three things to watch out for if you use Per-Ake Larson's
dynamic hash tables:

        1) It can be more expensive that you might expect if you have a
situation where a hash table changes in size dramatically over and over.
For example, a hash table that goes from 3 entries to 3,000 then back to
3 repeatedly.

        2) It's difficult to traverse the hash table while deleting elements
because the re-arrangements cause you to lose your place in the table.
You may wish to implement a 'LockSize' function and an 'UnlockSize'
function that right-sizes the table. This way you LockSize the table,
then traverse/delete, then UnlockSize it.

        3) You must use a hash function that can distribute evenly into powers
of two. It's much easier to create a hash function that distributes
evenly into prime numbers of buckets, but Per-Ake Lawson's tables
effectively use powers of two, so your hash function must distribute the
entropy evenly over the available bits.

        If you can* these three problems, you should find Larson's
algorithm to be extremely efficient for cases where you have no idea how
many elements will be in the hash table in advance.

        DS

 
 
 

1. about Apache C API, need way to build hash table

This is assuming apache 1.3, I've done no work on 2.0 other than
compiling it once to see if it compiled.

I do not think you can do what you want with a pool.  Your message is
unclear, but it looks like you want a table that you will update with
all the clients that connect with your server.  Remember on UNIX, these
are all different processes and they do not share memory.  You could
write some code to use shared memory, but you can not have pools use
this shared memory.

As far as what pool, the pool passed to your init function lives for the
lifetime of your server.  It is destroyed and recreated on any restrat,
graceful or not.  This can only be used for things you read from a
file.  This memory is not shared between clients.  If one client adds to
the table, none of the others will see it.

Apache does have a table API, but it is not a hash table.  Tables in
general are key/value lists.  The table API in apache is an ordered name
value list.  Getting a value for a particular key may mean you search
the entire list.  A hash table has quicker lookup.  If you intend to
have a table with a lot of values in it, you should have a real hash
table.

So you need to answer two questions:
1) do I need to update the table as I run or can I read the table one
time at server config time?  If you update as you run, you can not use
server pools.

2) Will I have a lot of data?  If so, you will want a true hash-table,
not the table API that apache provides.

Also look into the EAPI, which I think modssl uses, and it provides
shared memory.  I know *nothing* about EAPI outside of this.
Programming with it would be hard.  There is essentially no
documentation.

2. COPS implementation on freeBSD

3. Star Office 6.0

4. shared hash table between apache children

5. xmms and artsd

6. Common hash table implementation

7. INFO on PCI ADAPTEC SCSI and ETHERNET

8. hash table

9. is there any C library for hash table?

10. Fix mount hash table

11. KERN_INFO 2.4.19-pre2 IP/TCP hash table size printks

12. C-shell hash table