cplusplus
.com
TUTORIALS
REFERENCE
ARTICLES
FORUM
C++
Tutorials
Reference
Articles
Forum
Forum
Beginners
Windows Programming
UNIX/Linux Programming
General C++ Programming
Lounge
Jobs
Forum
General C++ Programming
Hash table question
Hash table question
May 26, 2011 at 10:00pm UTC
Bubbletea
(4)
why is full deletion (as opposed to lazy deletion) of a record in a hash table computationally more complex with open addressing than with separate chaining?
May 27, 2011 at 10:33am UTC
kfmfe04
(788)
consider the Wikipedia example:
http://en.wikipedia.org/wiki/Hash_table#Open_addressing
using notation (hash,location)
due to hash-collisions at 152 between John Smith(152,152) and Sandra Dee(152,153), Sandra Dee has been pushed to 153
due to hash-collisions at 153 between Ted Baker(153,154) and Sandra Dee(152,153), Ted Baker is pushed to 154
now, what happens if you delete John Smith? you need to move Sandra Dee to 152 and Ted Baker to 153
this is more expensive than separate chaining where you are just manipulating pointers
Topic archived. No new replies allowed.