Hash tables.

[Thalius]

Great Work and Thanks!

Ill check it out under Linux.

Thalius

[srod]

Great Work and Thanks!

Ill check it out under Linux.

Thalius

Thanks.

If it doesn't work under Linux then I'm afraid that I'm unable to do anything about it as I do not have a Linux box - and not likely to in the near future! Still there's no api involved so I see no reason why it should not work.

Hang on, what am I doing producing code without any api? That's sick! I'd better add some quickly!

[Thalius]

Great Work and Thanks!

Ill check it out under Linux.

Thalius

Thanks.

If it doesn't work under Linux then I'm afraid that I'm unable to do anything about it as I do not have a Linux box - and not likely to in the near future! Still there's no api involved so I see no reason why it should not work.

Hang on, what am I doing producing code without any api? That's sick! I'd better add some quickly!

- well if not i can take a look at it - as i am under Linux now almost 90% of the Time i am behind a puter and i gotta LOVE it

And hey now! Without API Code is soo much more interesting ( besides the fact it should run anywhere where PureBasic runs
Fred: When is that upgrade of PureBasic for PeaceMakerOS 1.0 planned ?

Cheers,
Thalius

[kinglestat]

yes, this is what I assumed is happening....so from assumption to certainty is a great step. Still my original answer remains a mystery...essentially my view how PB deals with pointers.
If I understand you, a linkedlist in pb is a "cast" in c for a generic pointer?

eg
(linkedlist *) ptr;

in which case any long can be a pointer...so that you can exchange the address of ll element to hash while keeping ll intact

Something like this?
I hope nobody minds....I like to learn as much as I can

[srod]

yes, this is what I assumed is happening....so from assumption to certainty is a great step. Still my original answer remains a mystery...essentially my view how PB deals with pointers.
If I understand you, a linkedlist in pb is a "cast" in c for a generic pointer?

eg
(linkedlist *) ptr;

Not exactly, although there are similarities I guess. A linked list in PB is strictly typed in that each element contains data of the same type. The fact that you can access each element of a linked list directly from it's address is a consequence of the way structures are handled by PB, nothing more.

I usually avoid using linked lists where possible and even in cases where I have to use a list, I generally access the elements directly through pointers (as with the hash tables to some extent, although this code is quite old and does need updating - something I will do pretty soon.)

Using pointers to access elements in a list is not really the same as having a list of generic pointers.

Don't confuse what is going on in the hash table library with the way linked lists operate in general. I'll repeat; a hash table is not a linked list, it is a single-dimensional array of pointers into a linked list.

[kinglestat]

cheers

[milan1612]

I totally overlooked this, great work srod!
...already have an idea on how to use it

[srod]

You're welcome Milan.

[Mistrel]

srod, you just saved me a whole lot of grief. Thank you for this!

If I try to look up an entry with an invalid key is the search time still about O(1) or is it O(n)?

[srod]

srod, you just saved me a whole lot of grief. Thank you for this!

If I try to look up an entry with an invalid key is the search time still about O(1) or is it O(n)?

It depends on how many 'collisions' there are. That is it depends on how many other entries in the table have hashes which match the one dervied from the key you gave. At best, 1 hash followed by 1 lookup. At worst, 1 hash followed by n lookups, where n is the number of entries from the SAME hash table sharing the same hash .

It is quite likely, therefore, that it will be very quick, depending on the 'likelihood' of collisions. This in turn depends on the size of the table, the number of keys and the hashing algorithm - all of which can be changed etc.

[kinglestat]

good explanation, as always srod
But there is another use which people often miss with hash tables; you can use a single hash table for all your (or most of your data)...no need to make a seperate hash

[srod]

good explanation, as always srod
But there is another use which people often miss with hash tables; you can use a single hash table for all your (or most of your data)...no need to make a seperate hash

Well, if an individual hash table starts to fill up then the average number of lookups required to find an entry will of course rise. The obvious solution is to then increase the size of the hash table, but this is equivalent to using a second table instead!

Personally, I will only use a hash table for specialist data using string indexes. I perfer more direct structures for other kinds of data.

[kinglestat]

well, I prefer to make a very large hash..say a million records, use a bitflag inside the hash structure to know which one it is; with the amount of RAM PCs have better 6MB of RAM in a single contiguas block. I have also experimented with using linked lists (similar to your code) for storing data, but I noticed that RAM usage goes very high versus using my own garbage collector. On 600,000 records I save about 38% of ram which more than makes up for the waste in the large hash table (160MB vs 118MB)

NOTE:

how Windows works, even if you allocate a large amount of RAM, only on the first selector request will windows "count" memory as used, so even if hash has lots of wasted space in it, most of the space will not be wasted as the selector will be pointing to disk. By default any allocation is 25% RAM, 75% swap.Conversely, small allocations will require different selectors, requiring more physical RAM; which is why I assume linked lists will finish consuming lots of RAM

[srod]

6 million records!

Cor blimey guv'ner, that's some good hash!

[Foz]

6 million? He said 6 hundred thousand...