hashing

[starkk]

can any one tell me what is the advantage of using double linked list over single linked list in chain hashing during deletion and searching of the node???

[Narue]

The only possible advantage would be if you use the result of search as the first part of deletion when the search returns a matching node:

void delete_item(hash_table *htable, T data)
{
    node *match = search_list(htable[hash(data)], data);

    if (match != NULL) {
        match->prev->next = match->next;

        if (match->next != NULL)
            match->next->prev = match->prev;
    }
}

This has the advantage of reusing the list search algorithm, but it's not limited to double linked lists. You can do the same thing with a search that returns the previous node in a single linked list:

void delete_item(hash_table *htable, T data)
{
    node *match = search_list(htable[hash(data)], data);

    if (match->next != NULL)
        match->next = match->next->next;
}

Since the list search would be hidden anyway in an ADT hash table, either way works just fine. In fact, I'd say that returning the pointer before the one you want is better for a dummy head setup because it doesn't make the head a special case.

Your book isn't talking about a general rule as much as a specific rule based on the authors' design decisions for their implementation of the hash table. There are many ways to implement separate chaining in a hash table, and in my experience your book (Introduction to Algorithms) sometimes makes some "interesting" design choices and shouldn't be taken as gospel.

p.s. When I say "interesting", I nearly always mean "stupid". :)

[starkk]

can u pls suggest some source for the analysis of close and open hashing

[Narue]

This is a resource with practical leanings. If you want proofs and detailed complexity analysis, a good book on data structures would be your best bet (Robert Sedgewick's Algorithms in C offers good analyses).

[tajendra]

To get brief overview about them one can start with this link[snipped]

One more good book adding to Narue is by Marl Allen Weiss 'data structure and algorithm analysis in C'