------------------
Take XTC, Then you wake up in the morning wondering "Wheres My Underwear?"

This message has been edited by StreetRaver on October 13, 2001 at 03:19 PM

------------------
Take XTC, Then you wake up in the morning wondering "Wheres My Underwear?"

Edit: In other words PHP like arrays.

/Thus endeth Anztac's idea for a discussion./
------------------
~Anztac [ I'm just this guy, you know? ]

This message has been edited by DeadAnztac on October 13, 2001 at 10:30 AM

But if you want to use the [] operator, you would either have to decide on some kind of regular expression to use as your index value( i.e. a[#0] or some other kind of reserved character so that you could do a string or integer search within), or else go w/out a true index.

Also, if you made it string-indexable such as a["foo"], your search times (for large, arrays) are going to approach the mythic O unless you force the arrays to be ordered, arent't you?

------------------

quote:

---

Originally posted by Dark-Angel99:
How come {name removed} doesn't like you? I find you really funny :D

---

Never argue with an idiot...he may be doing the same thing

quote:

---

Originally posted by StreetRaver:
To*, Damn I can't spell

---

quote:

---

Originally posted by Beldurin:
Also, if you made it string-indexable such as a["foo"], your search times (for large, arrays) are going to approach the mythic O unless you force the arrays to be ordered, arent't you?

---

Not if you use a hash, which is probably what you want in the first place. They use more memory than arrays but they're a *lot* faster - with a decent implementation, retrieval from an arbitrarily large hash happens in constant time, i.e. retrieving a value from a 1 bazillion element hash happens just as quickly as retrieving a value from a 10 element hash. w00t!

quote:

---

Originally posted by damien_s_lucifer:
hash
*snip*
hash
*snip*
hash
*snip
hash. w00t!

---

Dear God, is that ALL you think about!!??!?

...

I took a C++ class in high school, just to get started off with it, and we got just as far as arrays. I never really learned about pointers. Half the class could barely open up Microsoft Visual C++, so it was a VERY slowly progressing class.

Get your mind off of the drugs damien!

------------------
"Take a cable and simulate a sex act on each end. Press some combonation of play and record buttons." - askheaves

And get this...there were errors...sheeh...you'd think God could spell.

P.S. It's a joke...don't flame me for it

------------------

quote:

---

Originally posted by Dark-Angel99:
How come {name removed} doesn't like you? I find you really funny :D

---

Never argue with an idiot...he may be doing the same thing

quote:

---

Originally posted by miNus:
Dear God, is that ALL you think about!!??!?

---

Yes. And thanks for calling me God

DeadAnztac, implementing a hash is fairly straightforward. Essentially, you create an array of known size whose elements are a simple struct (forgive my C syntax, I'm pretty rusty) :

struct hashrec
{
char key[32];
void* data;
}

Then you define a hashing function :

unsigned int hash_func(char* key)
{
int keylen,genlen,count,return_value;
return_value = 0;
keylen = strlen(key);

// sum up all the characters in our key
for (count=0; count<keylen; count++)
{
return_value += key[count];
}
// return the modulus of our sum and our array size. For efficient hashing,
// HASH_ARRAY_SIZE should be a prime number
return_value = return_value \% HASH_ARRAY_SIZE;
return return_value;
}

Your array should be as large as the *maximum* value your hash function will ever return. For the function above, it will be HASH_ARRAY_SIZE - 1 :

struct hashrec hash_array[HASH_ARRAY_SIZE -1];

I'm just going to pseudo-code retrieval :

int hash_retrieve(char *key, char *data)
{
// figure out what our hash value is
int hash_array_offset = hash_func(key);

// Is our hashed struct null?
if (hash_array[hash_array_offset].key == NULL)
{
// yes, return failure
return 0;
}

// no. see if keys match
if (strcmp(hash_array[hash_array_offset].key,key) == 0)
{
// we found it. Copy out our data and return success.
copy_data(hash_array[hash_array_offset],data); // you'll have to define this
return 1;
}

// No match. Fall back on one of many collision resolution schemes.
}

Insertion is almost the same as retrieval. I'll leave it to you to figure out how to do it.

The only tricky part is collision resolution. With the hash function listed above, the keys 'fuck you' and 'you fuck' will both produce the same hash value, so if you try and insert those two keys into the hash you'll end up with a collision.

There are a lot of ways to resolve this - my favorite is to expand your hash_struct so it can become a linked list. After hashing, you search thru the list until you find a match or run off the end of the list.

Obviously there's more to hash implementation than just the above, but that should give you an idea of how they work at a fundamental level. Have fun!

This message has been edited by damien_s_lucifer on October 14, 2001 at 12:01 AM

- perform the hash lookup and get the index
- use the index to retrieve a pointer from your array
- then dereference the pointer to get the data

If you're storing the data itself in the array, that's a little different... but then you have the problem of having a fixed limit on how much data you can store per key.

Either way, though, inserts are going to slow down drastically as things are added and removed from the array, since you'll pretty much have to start at the beginning of the array and hunt until you find an empty slot, thereby negating a lot of the benefit you'd get from a hash.

Better to just alloc the memory you need during an insert, and store the data pointer in the hash itself. Free the memory on a delete.

As far as autogenerating enumerated data types, you'll have to use strings for that. The compiler's going to balk any time it sees something like

my_hash[foo] = "bar";

if you haven't declared foo somewhere else *and* made your class use the enum. But it won't care about

my_hash["foo"] = "bar";

as long as you've overloaded "foo" properly, i.e. as taking a char*.

A really good hash class should be able to handle

my_hash[char*] = char*
my_hash[int] = char*
my_hash[float] = char*

So that you can use arbitrary keys to store arbitrary data (you can store just about anything in a char* if you're careful )

<advocacy>
All of this crap is why I went to Perl in the first place. Weakly typed data + native lists, hashes, and regular expressions make it a programmer's dream.
</advocacy>