1113 Suggest how to implement a directaddress table in which

11.1-3 Suggest how to implement a direct-address table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictionary operations (INSERT, DELETE, and SEARCH) should run in O.1/ time. (Don’t forget that DELETE takes as an argument a pointer to an object to be deleted, not a key.)

this question is from introduction to algorithm third edition by thomas cormen

Solution

If the key need not be unique then we can implement a direct address table using Hashing with Chaining to run in O(1) time.
Against each duplicate key, there can be a linked list node containing satellite data. This can be a doubly linked list.
Insert operation will be O(1) as new node is added to head of linked list.
Delete operation will be O(1) as the address to node is given.
Search operation will be O(1) because
Load Factor ()=(size/capacity)= (No.of elements per slot/No.of slots in table)
Load Factor will be constant so search in case of duplicate keys will still be O(1).