HashCollisionLinearProbing will be unable to retrieve values after initial collision element is removed

[macnube]

In Chapter 7 it seems like there is a serious issue with the way that LinearProbing has been implemented but it could be my lack of knowledge as I'm learning about these things for the first time with your book! In the example code from the book we get:

19 - Gandalf
29 - John
16 - Tyrion
16 - Aaron
13 - Donnie
13 - Ana
5 - Jonathan
5 - Jamie
5 - Sue
32 - Mindy
32 - Paul
10 - Nathan
**** Printing Hash ****
5 -> [Jonathan - jonathan@email.com]
6 -> [Jamie - jamie@email.com]
7 -> [Sue - sue@email.com]
10 -> [Nathan - nathan@email.com]
13 -> [Donnie - donnie@email.com]
14 -> [Ana - ana@email.com]
16 -> [Tyrion - tyrion@email.com]
17 -> [Aaron - aaron@email.com]
19 -> [Gandalf - gandalf@email.com]
29 -> [John - johnsnow@email.com]
32 -> [Mindy - mindy@email.com]
33 -> [Paul - paul@email.com]

If at this point we do the following:

hash.remove('Jonathan')
Now index 5 is assigned to undefined

console.log(hash.get('Jamie'))

we will get undefined because of line 44 which doesn't continue searching because the original table[position] returns undefined.

So it seems like any later entries that we created from a collision cannot be retrieved after the original key is removed.

[fy951002432]

I also found this problem. Is there a better solution

[loiane]

I'll review the code and get back to you! Sorry for the delay!

[loiane]

Hi,

With the current approach of the algorithm, it is needed to add an else to search for possible deleted values. This is not the most optimized approach, and I'll review with more time and also provide a more optimized approach for this algorithm.
Thanks for opening this issue. I'll also submit an errata to Packt.

this.get = function(key) {
        var position = hashCode(key);

        if (table[position] !== undefined){
            if (table[position].key === key) {
                return table[position].value;
            } else {
                var index = ++position;
                while (table[index] !== undefined && (table[index] && table[index].key !== key)){
                    index++;
                }
                if (table[index] && table[index].key === key) {
                    return table[index].value;
                }
            }
        } else { //search for possible deleted value
            var index = ++position;
            while (table[index] == undefined || index == table.length ||
                (table[index] !== undefined && table[index] && table[index].key !== key)){
                index++;
            }
            if (table[index] && table[index].key === key) {
                return table[index].value;
            }
        }
        return undefined;
    };

[loiane]

Hi,
Added 2 versions of this algorithm with some fixes:

• Version 1: Update hash after each deletion: https://github.com/loiane/javascript-datastructures-algorithms/blob/third-edition/src/js/data-structures/hash-table-linear-probing.js
• Version 2: Soft delete: https://github.com/loiane/javascript-datastructures-algorithms/blob/third-edition/src/js/data-structures/hash-table-linear-probing-lazy.js

Also added some tests with Mocha to make sure different scenarios were covered:

• Version 1: https://github.com/loiane/javascript-datastructures-algorithms/blob/third-edition/test/js/data-structures/hash-table-linear-probing.spec.js
• Version 2: https://github.com/loiane/javascript-datastructures-algorithms/blob/third-edition/test/js/data-structures/hash-table-linear-probing-lazy.spec.js