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