Hash table

[pbrennick]

Sorry, could not ressist,
We eat hash potatoes with our breakfast, or is that just something we do in New England?  I also like Corned Beef Hash with Poached Eggs on top.

Paul

[Tedd]

We eat hash potatoes with our breakfast, or is that just something we do in New England?

Yeah it is - you're freaks :bg

[pbrennick]

Tedd,
Yep, we certainly are a strange bunch, even the rest of the US thinks we are wierd!  I don't care, they are just jealous!  :lol

Paul

[AeroASM]

We do that in "Old" england too.

[pbrennick]

Aero,
Believe it or not, we still miss the Monarchy and I guess we still pattern our lives accordingly.

Paul

[AeroASM]

Really? I hate the monarchy and both the two biggest parties.

[pbrennick]

Aero,
Nobody really appreciates what they have until it is gone.  Be happy.  You live in a wonderful country with an incredibly rich history.

Paul

[gabor]

Hi!

I was wondering when will we turn back to the original topic: hashing.
Does anyone have an implemented algo, that works according to the theory?

I created a raw code, not optimized and surely not bug free, and I could stick it here if anyone interessted.
I'm a bit shy and pessimistic, because till now it didn't have any significant advantages since no one responded... :'(

But I still believe in asm and in you people.  :U Please tell me it is worth to share everyone's own efforts!

Greets, gábor

[hutch--]

Gabor,

The one I posted is reasonably straight forward, its just that it does its own scan of the equaes file and does the replacements in the source file as well.

[gabor]

Hi Hutch and folks!

Thanks for your code. I would say I mainly see the point of the algo. You applied bucket hashing for strings, and I'd say the hash key provider proc is a special one.
I have some questions:
- Did I understand it right: you sum the char codes multiplied by primes to generate a key?
- The string length is not limited? What if overflow occures?
- Can it happen that more strings get the same key?
I have suggestions about this questions, but to be sure I would like to have the "official" answers.

BTW, I thought of a hash lib with all the neccessary stuff of a skeleton: variables, structures and procedures. I post mine right away, after I added some comments. Later I'll try to utilize it with your key gen function and your application if you don't mind...

Greets, gábor

[hutch--]

Its basic design is pretty straight forward, it is different with the array of primes as I was looking for a technique that would give a wider range of numbers that was fast enough. You determine the maximum string length by what you allocate in the main array making sure you have enough room for both source and replacement words and in production code you would place a limit on the string length based on that array member size.

It has a collision handling method that skip up to the next bucket based on the word length so it does avoid clustering this way to a reasonable extent.

Feel free to design whatever you think will work well. The inportant things with this style of hash table is to make the array count a prime number so you cannot get an infinite loop after it wraps around. You should probably set a count limit for the number of items you can put in it and this would be best determined empirically to see when its starting to fill up where it starts to slow down.

[gabor]

Thanks a lot Hutch!

I've already encounterd with the infinitive loop anomaly, and did not take the time to dig deeper searching for reasons and solutions. Honestly I just canceled creating a complex key generator, instead I used a random generator and a linear method. In a few hours I'll post my code, you will easily understand what I wanted to say.
I did not mentined, that I need something like open addressing, that version of hashing with bucket size of exactly one record. So when the array is full, then that's all, no more storing. I need all this stuff to finally complete my LZW encoder/decoder. (But it will come handy later on.)


Greets, gábor

[gabor]

Hi!

Here is what I promised. Please check it out and add your comments. And also feel free to ask, suggest and modify!

Greets, gábor


[attachment deleted by admin]