a linked list with pointer to the head and tail stored containing each request response tuple, and the pointers to the tuple stored in a hashtable described below.
a hash table of size n containing the hash of the request identifier as the hashfunction, and the pointer to the element in the linked list as key. assumption: from the reqest/response, the data which identifis a request to be same is extractable in O(1). so when u add an element u just add it to the tail, calculate its hash insert it to the table and remove the element at the head from the linked list and its entry from the hashtable. the ad has to be done with a lock on both the data structures. collition in the hashtable cud be taken care by some perfect hashing scheme. guys pour in ur comments. On Sat, Jul 3, 2010 at 11:20 PM, sharad kumar <[email protected]>wrote: > @harit > can u plzzzz elaborate how we can do c part of ques by hashing in o(1) > time > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
