A function that checks for duplicate elements in an array

Question

Is there a simpler way to implement this function?

function has_duplicates(arr) {
  var myObject = {};

  for (var key in arr) {
    if (myObject[arr[key]])
      return true;
    else
      myObject[arr[key]] = true;
  }
  return false;
}

console.log(has_duplicates(["foo", "bar", "baz", "quux", "foo"]));

Answer 1

function has_duplicates(arr) {

In JS, function names are usually in camelCase. So this should be hasDuplicates.

for (var key in arr) {

Don't use for-in with arrays. for-in loops will run through properties, including prototype properties. Use a regular for loop with counters. A forEach would also work, but you can't bail out in the middle of the array.

So far, iirc, a loop and hash is favorable in this scenario since it's just O(n) and you can bail out in the middle of the operation.

---

Another way to do it is the following. The concept is that when a value appears twice, indexOf and lastIndexOf will not be the same, thus adding the entry to the array created by filter.

function hasDuplicates(arr){
  return !!arr.filter(fuction(value){
    return arr.indexOf(value) !== arr.lastIndexOf(value);
  }).length;
}

Another way to do it is by using ES6's Set. The concept is that sets only hold unique values. When you try to add a duplicate, it won't be added to the set. If there is a mismatch in the array length and set size, you jumped over a duplicate somewhere, thus revealing the existence of the duplicate.

function hasDuplicates(arr){
  var set = new Set();
  arr.forEach(function(value){ set.add(value); });
  return set.size !== arr.length;
}

Going with @PeterCordes's suggestion, you can use Set and check on each iteration the size mismatch. We can assume false until a mismatch happens.

function hasDuplicates(arr){
  var set = new Set();
  for(var i = 0; i < arr.length; i++){
    set.add(arr[i]);
    if(set.size !== i + 1) return true;
  }
  return false;
}

Answer 2

Don't use for..in to iterate an array, because for..in is for enumerating objects and will enumerate over properties, including prototype properties. To iterate, use a normal for loop with a counter.

ES5

ES5 introduced some array iteration methods. Array.some() is the logical choice for this case, since it terminates the loop as soon as you've found an element that matches your condition.

function hasDuplicates(arr) {
  var valueHash = {};
  return arr.some(function(item) {
    var exists = valueHash[item];
    valueHash[item] = true;
    return exists;
  });
}

document.write(hasDuplicates(["foo", "bar", "baz", "quux", "foo"]));

ES6

If you can use ES6, you have the new Set object available, which is optimized for this kind of work. The constructor takes an iterable (such as an array) as an argument. So, you can just create a Set, and compare it's size to the array's length:

function hasDuplicates(arr) {
  return new Set(arr).size < arr.length;
}

document.write(hasDuplicates(["foo", "bar", "baz", "quux", "foo"]));

Now, I don't know, but it's conceivable that this could be slow on a large array. If your array is large, and there could be many duplicates, it might be faster to loop through and add items to the Set one at a time. Use the JS5 function from above, but use a Set instead of an Object:

function hasDuplicates(arr){
  var set = new Set();
  return arr.some(function(item) {
    var exists = set.has(item);
    set.add(item);
    return exists;
  });
}

document.write(hasDuplicates(["foo", "bar", "baz", "quux", "foo"]));

It has been suggested that checking Set.has() followed by Set.add() could require the hash being computed twice, and thus be slower. If that's the case, it may perform better by checking Set.size instead of using Set.has().

function hasDuplicates(arr){
  var set = new Set();
  return arr.some(function(item, i) {
    return set.add(item).size == i; // while the array is distinct, set.size is i + 1
  });
}

document.write(hasDuplicates(["foo", "bar", "baz", "quux", "foo"]));