Hash Table pointer question

This is a discussion on Hash Table pointer question within the C Programming forums, part of the General Programming Boards category; As part of my C course I'm trying to teach myself pointers in depth. I've looked up some abstract data ...

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    7

    Hash Table pointer question

    As part of my C course I'm trying to teach myself pointers in depth. I've looked up some abstract data types to implement with structures.

    I came across this implementation of a hash table, with seperate chaining as a collision mechanism. I'm confused with the some of the ways data is accessed using pointers. I've also left out the hash function.

    Just to clarify:

    -Is list_t **table a pointer to a pointer to a linked list structure?

    -Looking at the line below, is an array of **table pointers being made, each of which point to a pointer to a linked list?
    Code:
     for(i=0; i<size; i++) new_table->table[i]

    -When a lookup hash is performed in lookup, does the line below pull out a pointer to a linked list contained within the table[] array?

    Code:
    list = hashtable->table[hashval]

    Subsequently, does this line deference the pointer above and access the element within the linked list?

    Code:
    list = list->next

    Many thanks.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,444
    Quote Originally Posted by gibson221 View Post
    -Is list_t **table a pointer to a pointer to a linked list structure?
    Yes. table is a "pointer to a pointer to a list_t". Since list_t is basically a linked list structure, you're right.

    Quote Originally Posted by gibson221 View Post
    -Looking at the line below, is an array of **table pointers being made, each of which point to a pointer to a linked list?
    Code:
     for(i=0; i<size; i++) new_table->table[i]
    Almost right, you have one to many "*" or "pointer to" in there. An array of *tables is being made. He's malloc'ing an "array of pointers to list_t". If you look at the malloc there, he mallocs sizeof(list_t *) * size. That is an array with size elements of type list_t * (pointer to list_t).

    Quote Originally Posted by gibson221 View Post
    -When a lookup hash is performed in lookup, does the line below pull out a pointer to a linked list contained within the table[] array?
    Code:
    list = hashtable->table[hashval]
    Basically, yes. list is being used as an iterator. This sets it to the first element in the linked list for the hash value hashval. The loop moves list through the linked list looking for that exact string, and if found, returns that node of the linked list.

    Quote Originally Posted by gibson221 View Post
    Subsequently, does this line deference the pointer above and access the element within the linked list?

    Code:
    list = list->next
    Sort of, yes. list is a pointer to a struct, so list->next dereferences the pointer and gives the 'next' element. Basically, this is the part where the iterator is being moved to the next element in the linked list.

  3. #3
    Registered User
    Join Date
    Dec 2011
    Posts
    7
    Quote Originally Posted by anduril462 View Post

    Almost right, you have one to many "*" or "pointer to" in there. An array of *tables is being made. He's malloc'ing an "array of pointers to list_t". If you look at the malloc there, he mallocs sizeof(list_t *) * size. That is an array with size elements of type list_t * (pointer to list_t).
    Thanks for clearing that up. Just one question, so by malloc'ing an array of pointers to a list_t to **table, an array of *tables is being made because a *table deferences **table and is a pointer to a linked list?

    Also, when is a explicit return type required with malloc in this case? For instance is the following also valid?
    Code:
    ((new_table->table = (list_t *) malloc(sizeof(list_t) * size))


    Thanks again.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,444
    Quote Originally Posted by gibson221 View Post
    Thanks for clearing that up. Just one question, so by malloc'ing an array of pointers to a list_t to **table, an array of *tables is being made because a *table deferences **table and is a pointer to a linked list?
    Yeah, I think you more or less understand. To (hopefully) clarify:

    by malloc'ing an array of pointers to list_t to **table, an array of *tables is being made, because of the close relationship between arrays and pointers in C. Doing table[i] is the same as doing *(table + i). To take that a little further, adding an integer (like an array index) to a pointer type (such as table, a list_t **) results in the same type, that is (table + i) is the same type as table. Therefore, since table[i] == *(table + i), and the type of (table + i) is the same as the type of table, when you do table[i], you are basically dereferencing a list_t ** and getting a list_t *.

    Quote Originally Posted by gibson221 View Post
    Also, when is a explicit return type required with malloc in this case? For instance is the following also valid?
    Code:
    ((new_table->table = (list_t *) malloc(sizeof(list_t) * size))
    Valid, yes, but often, casting the return value of malloc is not recommended. Read this: FAQ > Casting malloc - Cprogramming.com.

  5. #5
    Registered User
    Join Date
    Dec 2011
    Posts
    7
    OK great, that makes sense now. Thanks.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hash table code question
    By Boxknife in forum C Programming
    Replies: 20
    Last Post: 08-13-2008, 05:55 AM
  2. Hash Table
    By Cpro in forum C++ Programming
    Replies: 3
    Last Post: 03-20-2008, 02:14 PM
  3. Question on free() ing a hash table
    By Overworked_PhD in forum C Programming
    Replies: 3
    Last Post: 10-26-2007, 01:16 PM
  4. hash table?
    By bennyboy in forum C Programming
    Replies: 2
    Last Post: 05-10-2007, 03:06 AM
  5. quick hash table question
    By Brian in forum C Programming
    Replies: 7
    Last Post: 07-30-2005, 07:22 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21