Thread: HashTable help?

Originally Posted by -EquinoX-

so the key is the one that hash unique values??

Ok, perhaps we should clean up the terminology. Say you want a hash-table of names->phone numbers. The name is your key, the phone number your data.
You apply the hashing function to the key and you get your hashkey. The keys are all unique, the hashkeys aren't necessarily. That's why you get collisions. You use the hashkey as an index into your hashtable, where you proceed to store the key and value together. The hashkey is only ever used to access the hashtable.

Hope that clears things up a bit.

QuantumPete

Originally Posted by -EquinoX-

is this function doing according to what it's suppose to do?

As far as I can see, yes. Though you should check the return value from malloc to make sure its not 0 and don't cast the return value either.
I'd also reccomend using strncpy, just because getting used to using it will make your code safer.

QuantumPete

what is strncpy different from strcpy??

it gets the buffer length and does not writes more characters than the buffer can accept. no need in your case - you already know that the buffer is big enough

why can't I case it, it has to return a char*

What do you mean?

I have to cast it unless it's a void pointer..

In C you do not need to cast a void pointer - have you read a FAQ?
Do you compile as C or C++?

do I just do a

yes

Originally Posted by -EquinoX-

what is strncpy different from strcpy?? why can't I case it, it has to return a char* so I have to cast it unless it's a void pointer..

But malloc() returns a void pointer, so it's fine to use that to assign to char *. [Unless you are using a C++ compiler to compile C-code, in which case you need the cast].

and I don't understand this method parameter:

/* Take a string constructed with the above, and give it back to memory */
void StringDestruct (char* s);

do I just do a :

free(s) here??

I would think so.

--
Mats

Originally Posted by -EquinoX-

I am using C here not C++

So no cast will be fine - void * can be automatically converted to char *.

--
Mats

generally and int is defined to be of WORD length. Where WORD is the size of your databus. In this case either 32 or 64 bit. Hence on a 32 bit system int is likely 4 bytes, on a 64 bit system 8 bytes.

QuantumPete

Well, for one thing, an int is normally 32 bit on both 32- and 64-bit machines, so unless you are using a very unusual processor/OS combination, if you are using "int", it probably will not make ANY difference.

If you use the type "long int", then that is more likely to be 64-bit, but far from guaranteed. [Linux for 64-bit processors use long as 64-bit, but Windows leaves even long int as 32-bit].

The place where it almost always matters is pointers. A pointer in a 32-bit machines 32-bit and a pointer in a 64-bit machine is 64-bits.

For most things, it makes no visible difference to you - if you add two 32-bit numbers into a long, you will only see a difference if the 33rd bit gets set by the addition - in a 32-bit machine, you will get a smaller number than you expect, whilst if long is 64-bit you will get a bigger number.

If you use unsigned int for your hash-value, then you should be seeing no difference.

But presumably, you do not use the entire 32 bits, as that would necessitate a table of 4G times the size of the hashtable entry - that would be rather huge [and require a 64-bit machine with plenty of memory to run well - at least if you have a good spread of hashvalues and large number of entries]. The normal method is to divide or mask the number to a suitable size, e.g. if your hashtable is 100 long, use hashvalue % 100 to "limit" the hashvalue index.

--
Mats

what do you guys think of this add function in the HashTable I created?

Code:

boolean HashTableInsert(HashTable *this, const char* key, const char* value)
{
  list_t *new_list;
  list_t *current_list;

  int_u4 hashval = StringHash(key) % this->length;
  /* Attempt to allocate memory for list */
  if ((new_list = malloc(sizeof(list_t))) == NULL)
    outOfMemory(__LINE__, __FILE__, "struct node creation");

  /* Does item already exist? */
  if (HashTableContains(this, key)){
    char* val = HashTableLookUp(this, key);
    StringDestruct(val);
    val = StringConstruct(value);
    return false;
  }
  else{
  /* Insert into list */
    new_list->key = StringConstruct(key);
    new_list->value = StringConstruct(value);
    new_list->next = this->table[hashval];
    this->table[hashval] = new_list;
    return true;
  }
}

it basically just frees the old value and copies the new value in if the key already exists.. this is the part where I was sure to get.. otherwise it just adds in the key value to the hash table
HashTableLookUp funtion here just looks up the given key and return a "reference" to the given value.