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

[Wannabe h4x0r <chris@dont.spam.me>]

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