Question 412113 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Set.Has() does not work with arrays because they are mutable. What's the alternative?

I have a list of (lots of) coordinates.

coordinateList = [[1,2], [2,1], [3,5]];

These coordinates are unique and since I have a lot of them I want to be able to quickly check if a new coordinate is already in the list without having to search in the list. So a Set is the perfect data type to store my coordinates and hash them.

let coordinateSet = new Set();
for (let coordinate of coordinateList) {
    coordinateSet.add(coordinate);
}

Now coordinateSet is a Set that contains coordinates.

However, those coordinates are saved as an array of two elements, which is mutable. Because of this I cannot check if the set has already a coordinate

coordinateSet.has([1,2])  --> false

I have seen solutions that convert the array to a string to get immutability, but it looks like a hack that although it might work it feels not the correct way of solving that.

How could I store my coordinates (2 numbers) such that they are immutable and can then be used in a set? Is there something like a tuple which is immutable and can be used for this purpose?

Tags:

3

Answers


  1. 0

    Strings would usually fit this solution perfectly, but it may not work well for large sets. If this is your concern, you have to keep it within numeric bounadries. I can think of two other options:

    Nested map (2 levels: 1-level: x, 2-level: y)

    const coordinateList = [[1, 2], [2, 1], [3, 5]];
const coordinateMap = new Map();

for (let [x, y] of coordinateList) {
  let ySet = coordinateMap.get(x);
  if (!ySet) {
    ySet = new Set();
    coordinateMap.set(x, ySet);
  }
  ySet.add(y);
}

function hasCoordinate(x, y) {
  const ySet = coordinateMap.get(x);
  return ySet ? ySet.has(y) : false;
}

console.log(hasCoordinate(1, 2)); // true
console.log(hasCoordinate(2, 3)); // false

    The other is to build a hash function, but… collisions and stuff, may be not worth it.

    Login or Signup to reply.
  2. 0

    Perhaps stringify-ing each array, including in .has(), would work? It does for your example:

    coordinateList = [[1,2], [2,1], [3,5]];
let coordinateSet = new Set();
for (let coordinate of coordinateList) {
    coordinateSet.add(JSON.stringify(coordinate));
}
console.log(coordinateSet.has(JSON.stringify([1,2])))
    Login or Signup to reply.
  3. 0

    Using a Set seems like a good idea but in js when you add arrays to a Set, it checks them by reference, not by value. So even if two arrays have the same numbers, they are considered different if they are different objects.

    That’s why when you do coordinateSet.has([1,2]), it returns false, even though [1,2] is in the set. Because [1,2] is a new array.

    Common way to fix this is to convert the coordinates to strings, like "1,2", and store those in the Set. Then you can check if the Set has "1,2". Feels like a hack, but it’s a common in js.

    js doesn’t have immutable tuples like some other languages. So using arrays or objects won’t solve the problem unless you can ensure you’re using the same instances.

    Another option is to create a unique key for each coordinate. e.g. you combine the x and y values into a single number or string that uniquely represents the coordinate.

    Using strings as keys is simple and works well. It’s also efficient because string comparisons are fast.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search