If the last entry in a cluster is removed, it doesn’t need to be replaced with a bridge. Outline how this might be implemented and discuss the advantages and disadvantages of making this change to answer the question: Is it worth the effort?

What will be an ideal response?

You would need to check if the next bucket contained either an entry or a bridge. If not, then you could make the bucket empty. An advantage of this would be to break future clusters. Consider the following scenario in which the first letter of a name is the key and the key range is ‘A’ to ‘Z’. After hashing “Bob”, “Betty” and “Billy”, the buckets for ‘B’, ‘C’ and ‘D’ are occupied. A search for “Borat” would have to go all the way to ‘E’ to discover failure. Now, if “Billy” is deleted and is replaced by a Bridge, then “Edgar” gets inserted, a new search for “Borat” would have to go all the way to ‘F’ to discover failure. If, instead, when “Billy” was deleted and the next bucket (‘E’) was discovered empty and ‘D’ was made empty, then after “Edgar” is inserted, a search for “Borat” would fail sooner at ‘D’. Since clusters can hurt performance, this sounds like a worthwhile change to make.