verifyRemoveSideEffect possible simplification

[ivanduka]

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:

 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)?

Thank you again for sharing your wisdom :)

[loiane]

Hi @ivanduka. Yes, you can simplify the code. The original idea was also to show how to handle the same algorithm in other languages as well - as in JavaScript we don't have to set the length of the array prior its creation, then we're good!

[ivanduka]

Thank you @loiane !