Hash table question

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?

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.