How uthash solve the hash collision ?

[林浩]

Hi everyone,

I want to write a trivial hash table implementation in C to make myself familiar with it. 

After a little search I found uthash is an excellent hash table implementation in C. So I start to read the 948 lines source code.

The most important part for me is:

HASH_MAKE_TABLE          // make a  table

HASH_FCN                         // using some hash function to generate hash index

HASH_ADD_TO_BKT           // add an element to hash table, using the hash index generated by HASH_FCN

I can't  find the code, which is used to solve hash collision in the uthash.h, so someone can help me?

~Hao

[Troy D. Hanson]

Hi Hao,

> --

Uthash uses chaining. To elaborate a little bit: When you add an item, it computes the hash function on the key. That is used to choose the bucket. The bucket is a chain of items. It is ok if two items collide. They just land in the same bucket. At lookup time, uthash compares the key (not the hash value) to ensure the right item is returned.

Troy

[林浩]

Thanks, Troy,

Your answer solves my question!

~Hao

2013/12/9 Troy D. Hanson <troyd...@gmail.com>

Troy

--
You received this message because you are subscribed to a topic in the Google Groups "uthash" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/uthash/wZcmWQ1cwNw/unsubscribe.
To unsubscribe from this group and all its topics, send an email to uthash+un...@googlegroups.com.
To post to this group, send email to uth...@googlegroups.com.
Visit this group at http://groups.google.com/group/uthash.
For more options, visit https://groups.google.com/groups/opt_out.

[shubhamsi...@gmail.com]

Hi, Can you please tell what hash function is used to calculate the index value? Also is there any memory constraint to use uthash and what is the complexity for insertion int he hash table and itearting over all the elements of the array?