Re: hashing(HATs. A more efficient algorithm?)

["Chad R. Meiners" <crmeiners@hotmail.com>]

So what does it have to do with hash tables?  All you have here is an
efficient method of expanding the size of an array.

-CRM

"Wannabe h4x0r" <chris@dont.spam.me> wrote in message
news:YYvt8.11521$Gl6.6265@sccrnsc01...
> On Thu, 11 Apr 2002 19:29:16 -0400, chris.danx wrote:
>
>
> > "Wannabe h4x0r" <chris@dont.spam.me> wrote in message
> > news:mRot8.209679$Yv2.66927@rwcrnsc54...
> >> Lately I've been using Hashed Array Trees(or Tables), which have cut
> >> the execution time by about %40, and has given me a memory savings of
> >> about %20-%30. Note that I'm just progressing from the beginner to the
> >> intermediate stage in my "skillz".
> >>
> >> Basically, you start with an initial array of n number of elements. The
> >> first element is a "pointer"(however one may choose to define that) to
> >> the last element of the array. When the array is filled to n-2
> >> elements, automatically add x additional elements to the array, and
> >> them set the pointer in the first element to point to the end of the
> >> array again(which should be n+x_l).
> >> One can use any number of methods to decide how many elements to add at
> >> any time, it's not fixed. For an additional bit of buffer overflow
> >> protection, one could set the pointer to point to n-2 (or n-1 or
> >> whatever) depending on whatever makes sense at the time.
> >>
> >> This is about the simplest damn algorithm in the world, at least to me
> >> it is. Heh.
> >
> > I don't really get it, but this sounds like chains to me.  Can you
> > explain it a bitty more?
> >
> > bye,
> > Chris
> >
> >
>
> Alright.
>
> Suppose you have some numbers like 1,2,3,4(or could be
> characters, or whatever).
> The actual array would look like (using psuedocode)
>
> array := (pointer(array'range - 1),1,2,3,4,NULL);
> -- The pointer points to the NULL at the end of
> -- The array. Of course I'm using NULL here as
> -- a placeholder for the psuedocode. The NULL
> -- element could hold anything to indicate that
> -- says "This is the end of the array"
>
> Now you want extend that array to hold four more values.
> Look at where the pointer in the first element is
> pointing, jump to that element in the array, add five
> more elements from that point(one to hold the reference
> element), then change the pointer to point at the end
> of the array again. The extended array will look like
> this...
>
> array := (pointer(array'range-1),1,2,3,4, , , , ,NULL --The pointer now
> points here.--);
>
> Then you just fill in the elements.
>
> array := (pointer(array'range-1),1,2,3,4,5,6,7,8,NULL);
>
>
> This beats making a new larger array and copying all the elements over,
> plus the new ones. Plus you can determine with fair degree of certainty
> how much memory you'll need at any one time. Since your only working with
> the specific elements you need, it saves processor time. And because your
> not duplicating data in various moves and copies, it saves
> memory(especially on very large files.)
> It could be said that one does not need a reference pointer, but that
> becomes problematic if you have more than routine modifying data in the
> array.
> To make the array smaller, just do the reverse. Move the reference
> character(or integer, or bit, or whatever) to a point in the array, and
> free all memory above that point.
>
> Amy I making any better sense. Dr. Dobbs had an article on this. I'll see
> if I can find it.
>
> Chris