[用JS來寫演算法和了解資料結構] Data Structures - Day5 Hash Table - 集合 Set

Hash Tables

in javascript object could be represented Hash Tables.

Hash Collision -> 是指不同的輸入經過 Hash 函數計算後，得到了相同的輸出值。相同hash編號內的資料，會透過Linked List的方式串接在一起。

• Hash Table 常用在儲存使用者的 Email、使用者資料。

Operations on Hash Tables

1. Insert - O(1)
2. Access Lookup- O(1)
3. Search - O(1)
4. Delete - O(1)

集合 Set

The Set object lets you store unique values of any type, whether primitive values or object references.

• elements in an array do not repeat -> use Set
• elements in an object do not repeat -> use Map

both have size, has(), and keys().

const set1 = new Set([1, 2, 3, 4, 5]);
set1.add(7); // [1, 2, 3, 4, 5, 7]
set1.add(1); // [1, 2, 3, 4, 5, 7] the same value cannot be added into the set

console.log(set1.has(1));// true
console.log(set1.has(6)); // false

const obj: {name: 'Ken'}; // obj type can be added to a set
set1.add(obj);  // [1, 2, 3, 4, 5, 7, {name: 'Ken'}] 

console.log(set1.has({name: 'Ken'})); // false

set1.delete(5);  // true  [1, 2, 3, 4, 7, {name: 'Ken'}] 
set1.delete(6);  // false  [1, 2, 3, 4, 7, {name: 'Ken'}] 

set1.size; // 6 

const text = "India";
const set2 = new Set(text); // Set ['I', 'n', 'd', 'i', 'a']
set2.size; // 5

set2.keys(); //  {'I', 'n', 'd', 'i', 'a'}
set2.values(); //  {'I', 'n', 'd', 'i', 'a'}
set2.entries(); // {'I' => 'I', 'n' => 'n', 'd' => 'd', 'i' => 'i', 'a' => 'a'}

set2.forEach((item) => console.log(item));

set2.clear(); //{size: 0}

Set composition

return Set
A.difference(B) 差集
A.intersection(B) 交集
A.symmetricDifference(B)
A.union(B) 聯集

return Boolean
A.isDisjointFrom(B)
A.isSubsetOf(B)
A.isSupersetOf(B)

圖片來源

• MDN SET

const setA = new Set([1, 2, 3, 4]),
  setB = new Set([2, 3]),
  setC = new Set([3, 4, 5, 6]);

setA.difference(setC); // => Set [1, 2]
setA.union(setC); // => Set [1, 2, 3, 4, 5, 6]
setA.intersection(setC); // => Set [3, 4]

setA.isSuperset(setB); // => true

也可用於 Map

const a = new Set([1, 2, 3]);
const b = new Map([
  [1, "one"],
  [2, "two"],
  [4, "four"],
]);
console.log(a.union(b)); // Set(4) {1, 2, 3, 4}

Array <==> Set

// Set => Array
let SetToArray = [...set]; 
let SetToArray2 = Array.from(set);

// Array => Set
let ArrayToSet = new Set(arr);

Remove duplicate elements from an array

const arr = [1, 1, 3, 5, 5, 7];
let uniqueArray =[...new Set(arr)]; //[1, 3, 5, 7]

Two Sum

// Naive
function hasPairWithSum(arr, sum) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = i + 1; j < len; j++) {
      if (arr[i] + arr[j] === sum)
        return true;
    }
  }

  return false;
}

// Better use Set
function hasPairWithSum2(arr, sum) {
  const mySet = new Set();

  for (let i = 0; i < arr.length; i++) {
    if (mySet.has(arr[i])) {
      return true;
    }
    mySet.add(sum - arr[i]);
  }
  return false;
}

console.log(hasPairWithSum2([6, 4, 3, 2, 1, 7], 9));

//Better use Map

function hasPairWithSum2(arr, sum) {
  const myMap = new Map();

  for (let i = 0; i < arr.length; i++) {
    const newNum =  sum - arr[i];
    console.log(newNum);
    console.log(myMap);
    if (myMap.has(newNum)) {
      return true;
    }
    myMap.set(arr[i], i);
  }
  
  return false;
}

console.log(hasPairWithSum2([6, 4, 3, 2, 1, 7], 9));

學習與參考資料

• 前端工程師用 javaScript 學演算法
• Data Structures and Algorithms (DSA)
• Master the Coding Interview: Data Structures + Algorithms