[2] [gclist] Garbage collection and XML

[eliot@parcplace.com]

-covering message-

+-----------------------------
| Date:	Fri, 02 Mar 2001 10:36:35 -0500 (EST)
| From:	Jerrold Leichter <jerrold.leichter@smarts.com>
| Subject:	Re: [gclist] Garbage collection and XML

| Dynamically adjustable hash tables have been around for 25 years.  They n=
ever
| seem to have made it into the standard textbooks, and most programmers are
| unaware of them.  To this day, textbooks continue to list fixed size as a
| minus for hash tables.  (The contents of textbooks gets frozen in place: =
 The
| textbooks define the course requirements, which in turn define the constr=
aints
| on newer textbooks for the same courses.  Compare a data structures textb=
ook
| published today to one published in 1980 and what you'll find is that the=
 new
| one uses object-oriented concepts and C++ or Java, while the older one us=
es
| Pascal or C - but the actual algorithms presented are pretty much the sam=
e,
| and generally all those algorithms were familiar by the mid-70's.  Tying =
this
| back to GC:  You can see the same phenomenon in compiler texts, or any ot=
her
| texts that might be expected to discuss garbage collection techniques:  T=
hey
| say little - and much of what they *do* say is long obsolete - because th=
ey've
| *always* said little.)

| I've implemented and used with very good results the "linear hashing" alg=
o-
| rithm, described by Witold Litwin in Proc. 6th International Conf. on Very
| Large Databases, 1980.  A more easily accessible reference is Per-\AA ke =
Larson
| in CACM 31 (1988), pg 446--457.  Linear hashing gives you expected consta=
nt
| time access using a table whose size is (expected) bounded as a constant
| multiple of the number of elements in the table.  It grows and shrinks
| dynamically in small increments - the (expected) cost per growth/shrinkage
| again a constant.  All these constants are linearly related to a user-set=
table
| parameter which is basically the target load factor for the table.

You can find an implementation of dynamic hash tables in Smalltalk, which h=
as had them from the mid 70's.  There are a number of free Smalltalk implem=
entations, and they come with all source code.  See e.g. www.squeak.org or =
www.cincom.com/smalltalk/.

---
Eliot Miranda                ,,,^..^,,,               mailto:eliot@parcplac=
e.com
ParcPlace division, Cincom   Smalltalk: scene not herd       Tel +1 408 216=
 4581
3350 Scott Boulevard, Building 36, Santa Clara, CA 95054 USA Fax +1 408 216=
 4500