Open Hashing: rare duplicate key bug

The open hashing exercise creates rarely duplicates which cause confusing situations.

open-hashing-duplicate-1

https://github.com/Aalto-LeTech/jsav-exercise-recorder/assets/3034945/b520c8db-ec84-4e73-8409-b1710d82fc00

Analysis of the video

0:07 There is a hash table with ten slots. The slot with index 6 has a list of three keys: 424 -> 358 -> 853. On the top of the operation stack, there is operation "424 insert".

0:12 The user clicks the hash table slot 6. The duplicate key is added to the end of the list. Result: 424 -> 358 -> 853 -> 424.

0:14 The next item on the operation stack is "358 remove".

0:20 The user clicks the first (topmost) node in the list of table slot 6, having key 424. This list item is highlighted with yellow color.

 The user explains that according to his logic, the empty hash table 
 slot should be clicked as well.

0:24 The user clicks the second node in the list, having key 358. The node is removed from the list.

0:25 The next item on the operation stack is (again) "358 remove". The user clicks list items from the top: 424, 853, 424. Upon each click, each node is added a yellow highlight color. On the last click, the highlight is removed.

0:38 The next item on the operation stack is "424 remove". The user notices: "Now we can remove the 424."

0:43 The user clicks the first item on the list (of slot 6): 424. The yellow highlight does not appear as expected.

0:48 The user clicks the second item (853). The yellow highlight is added.

0:52 The user clicks the third item (424). This item is removed from the list, and the yellow highlight at 853 is also removed.

1:00 The user discusses with another person: both heard that he clicked the first item with key 424 [at time 0:43]

1:01 The next operation is "154 remove". The user clicks the hash table slot 0. The operation is removed from the operation stack.

1:08 The user clicks the hash table slot, the first item (424), and the second item in the list (853).

1:09 The next operation is "358 remove". The user clicks the hash table slot 6, then the first list node having the key 424. The yellow highlight does not appear as expected. The user clicks second list node having the key 853. The yellow highlight at that node appears. Then the highlight disappears, and the operation is removed from the operation stack.

 The user says: "It cannot be clicked. The duplicate cannot be clicked."

1:24 The user continues with other operations which are pointed at other has table slots.

1:28 The next operation at the operation list is "424 search". The user clicks the hash table slot 6, then the first list node having the key 424. The yellow highlight does not appear as expected.

 The user clicks at the second node having the key 853.
 Nothing happens: operation "424 search" is not removed from the
 operation stack as expected.

 The user says: "We cannot search it, because it is a different 424!"

1:46 The user clicks again the node 424. No highlight appears. However, the operation "424 search" is removed from the operation stack.

 The user is confused: "What on earth? Now I clicked it and now it
 succeeded. There is something really weird happening now."

2:00 The use performs a couple of operations not related to the hash table slot 6.

2:05 The last operation in the operation stack is "358 search". The user clicks the hash table slot 6, then the first list node having the key 424. Now, again, the yellow highlight again does appear as expected. The user clicks the second (last) node in the list having key 853. The highlight on this node does not appear. However, the operation queue becomes empty as expected.

2:16 The user clicks the Grade button. The automated grade is 37/100.

Analysis

Sometimes the exercise may create duplicate values.
The exercise adds a duplicate to the end of the list.
Removal of duplicate keys is an ambiguous operation: which one of the duplicates should be removed ?
Duplicate keys also create a confusing situation where the yellow highlight does not appear to some of the duplicates upon clicking them.
Moreover, if a duplicate key appears, it might make another duplicate unsearchable, leading the exercise into a state where it cannot be finished.

The GUI actions on hash table are different depending on whether the hash table slot is empty. At an empty slot, the correct action is to click the slot. At a nonempty slot, the user may click the slot, but that does nothing. It is disputable whether the hash table slot should also be clicked when it is empty.

Sidenote

The third edition of "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein makes the explicit assumption that the keys in a hash table are a set.

Recommendations:

In the current version of hashing exercises, disable the possibility of adding duplicate keys.
Highlight the click operations explicitly in the model answers of the hashing exercises.

Aalto-LeTech / jsav-exercise-recorder