Can we simplify the function verifyRemoveSideEffect?
It's original version in the file is:
verifyRemoveSideEffect(key, removedPosition) {
const hash = this.hashCode(key);
let index = removedPosition + 1;
while (this.table[index] != null) {
const posHash = this.hashCode(this.table[index].key);
if (posHash <= hash || posHash <= removedPosition) { // QUESTION IS ABOUT THIS LINE
this.table[removedPosition] = this.table[index];
delete this.table[index];
removedPosition = index;
}
index++;
}
}
However, since hash is always less than removedPosition, can we just check for posHash <= removedPosition instead of posHash <= hash || posHash <= removedPosition?
This way the function would look like:
verifyRemoveSideEffect(key, removedPosition) {
const hash = this.hashCode(key);
let index = removedPosition + 1;
while (this.table[index] != null) {
const posHash = this.hashCode(this.table[index].key);
if (posHash <= removedPosition) { // THIS LINE IS CHANGED
this.table[removedPosition] = this.table[index];
delete this.table[index];
removedPosition = index;
}
index++;
}
}
I tried this change and it passes all your tests.
Also, this way we do not need const hash = this.hashCode(key); and subsequently key param of the function:
verifyRemoveSideEffect(removedPosition) { // THIS LINE IS CHANGED
// const hash = this.hashCode(key); - THIS LINE IS REMOVED
let index = removedPosition + 1;
while (this.table[index] != null) {
const posHash = this.hashCode(this.table[index].key);
if (posHash <= removedPosition) { // THIS LINE IS CHANGED
this.table[removedPosition] = this.table[index];
delete this.table[index];
removedPosition = index;
}
index++;
}
}
(of course we would need to change the remove function as well, so it calls this.verifyRemoveSideEffect(position); instead of this.verifyRemoveSideEffect(key, position);
With those changes it also passes all tests.
Does it make sense or there are some edge cases that I do not see and they need this check for both possibilities (posHash <= hash || posHash <= removedPosition)?
Hi Loiane!
Thank you for this excellent book! I enjoy reading it a lot!
The question is regarding hash-table-linear-probing.js:
Can we simplify the function verifyRemoveSideEffect?
It's original version in the file is:
However, since
hash
is always less thanremovedPosition
, can we just check forposHash <= removedPosition
instead ofposHash <= hash || posHash <= removedPosition
?This way the function would look like:
I tried this change and it passes all your tests.
Also, this way we do not need
const hash = this.hashCode(key);
and subsequentlykey
param of the function:(of course we would need to change the
remove
function as well, so it callsthis.verifyRemoveSideEffect(position);
instead ofthis.verifyRemoveSideEffect(key, position);
With those changes it also passes all tests.
Does it make sense or there are some edge cases that I do not see and they need this check for both possibilities (
posHash <= hash || posHash <= removedPosition
)?Thank you again for sharing your wisdom :)