set

set 이란?

set은 array, list 처럼 순열(서로 다른 n개의 원소에서 r ≤ n 개를 뽑아 한 줄로 세우는 경우의 수) 자료구조 이다
그러나 순서라는 개념이 존재하지 않는다 (index가 없음)

set의 특징을 살펴보면

• 데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조 (collection)

  • 순열 : 서로 다른 n개의 원소에서 r ≤ n 개를 뽑아 한 줄로 세우는 경우의 수

• 삽입(insertion) 순서대로 저장되지 않는다. 즉 특정한 순서를 기대할 수 없는 자료구조

• 수정 가능하다(mutable)

• 동일한 값을 여러번 삽입 불가능, 동일한 값이 여러번 삽입 되면 하나의 값만 저장

• Fast Lookup이 필요할때 주로 쓰인다

>>> my_set = {1, 2, 3, 4, 5, 1, 2}
>>> my_set
{1, 2, 3, 4, 5}  // 중복 불가능 , 중복있으면 하나의 값만 저장
>>> for i in my_set:
...     print(i)
...
1
2
3
4
5
>>> my_set.append(7)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'set' object has no attribute 'append'
>>> my_set[0]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'set' object does not support indexing
>>> my_set.add(7)
>>> my_set
{1, 2, 3, 4, 5, 7}
>>>
>>> 5 in my_set # look up
True

---

Set의 구조

• Array와 달리 set은 요소들을 순차적으로 저장하지 않음 (index가 존재하지 않는다)

• Set에서 요소들이 저장될 때 순서는

  • 저장할 요소의 값의 hash 값을 구한다
  • 해쉬값에 해당하는 공간(bucket)에 값을 저장

• 이렇게 set는 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없음, 순서가 없기 때문에 indexing도 없다.

• 그리고 해쉬값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없다 (각각의 메모리 주소가 있기때문)

• 해쉬값을 기반으로 저장하기 때문에 look up 이 굉장히 빠름

  • Look up: 특정 값을 포함하고 있는지를 확인 하는것 ==> 5 in my_set
  • Set의 총 길이와 상관없이 단순히 해쉬값 계산 후 해당 bucket을 확인하면 됨으로 O(1)

hash는 단방향 (one way) 암호화이다
단방향이란 한번 암호화 하면 복호화가 안된다는 뜻이다
복호화는 암호화의 반대말로 부호화(encoding)된 데이터를 부호(code)화 되기 전 형태로 바꾸어, 사람이 읽을 수 있는 형태로 되돌려놓는 것이다.
실제 값의 길이와 상관없이 hash 값은 일정한 길이를 가진다
그럼으로 Hash는 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할때 사용된다

---

언제 set을 사용해야될까?

• 중복된 값을 골라내야 할때
• 빠른 look up 을 해야 할때
• 그러면서 순서는 상관 없을때

---

실습-1

코드

let mySet = new Set(['wecode','wework','wecode']);

mySet.add('wecode');
mySet.add('wework');
mySet.add('weplay');

mySet.forEach((value) => {
	console.log(value);
});

결과

wecode
wework
weplay

• set의 value를 추가할때 add 메서드 사용
• set은 중복을 허용하지 않으므로 중복된 값이 있다면 맨 하나의 값만 저장한다

---

실습-2

js에서 실행시간을 측정하려면 performance 를 사용할 수 있다
아래 코드를 살펴보면

코드

const {
    performance
  } = require('perf_hooks')


for(var j = 610000; j < 1000000 ; j += 40000) {
    var array = [ ]
    for(var i = 0; i < j ; i++){
        array.push(i);
    }

    var myset = new Set()
    for(var i = 0; i < j ; i++){
        myset.add(i);
    }

    array_find_time = 0;
    for(var z = 0; z < 1000; z++){
        num = Math.floor(Math.random() * j);
        var t0 = performance.now()
        array.find(element => element == num);
        var t1 = performance.now()
        array_find_time += (t1-t0);
    }

    set_find_time = 0;
    for(var z = 0; z < 1000; z++){
        num = Math.floor(Math.random() * j);
        var t0 = performance.now()
        myset.has(num);
        var t1 = performance.now()
        set_find_time += (t1-t0);
    }

    console.log("Using Array, Call to find value took " + array_find_time/1000 + " milliseconds.  " + "Using Set, Call to find value took." + set_find_time/1000);
}

결과

---

실습-3

중복을 확인하는 함수를 구현할 수 있다

코드

function isDuplicated(arr) {
    var mySet = new Set(arr);
    return mySet.size < arr.length;
}
console.log(isDuplicated([1,1,2,3]));  // 결과 true
console.log(isDuplicated([1,2,3]));  // 결과 false

function uniqueElements(list1, list2) {
    var mySet = new Set(list1.concat(list2));
    return Array.from(mySet);
}

console.log(uniqueElements([1,2,4,5],[ 2,3,5,6]));
// 결과 [1, 2, 4, 5, 3, 6]

• 참고 : MDN Array.form()
  유사 배열 객체(array-like object)나 반복 가능한 객체(iterable object)를 얕게 복사해새로운Array 객체를 만듬

---

실습-4

• union, intersection, difference 실습

---

Dictionary / HashMap / HashTable

Dictionary 란?

Dictionary (다른 언어에서는 hashmap 이나 hash table이라고 하기도 함)는 Key-value 형태의 값을 저장할 수 있는 자료구조 이다
이름은 "정우성" 등 실제 데이터 값과 데이터를 설명하는 key의 대응 관계를 표현할때 유용하다

Dictionary의 특성은

• Set과 마찬가지로 특정 순서대로 데이터를 리턴하지 않음 (index가 존재하지 않는다)
• Key의 값은 중복될 수 없고 만일 중복된 key 가 있으면 먼저 있던 key와 value를 대체한
• 수정 가능(mutable)

>>> my_dict = {1 : "one", "two" : 2, 3 : 3.0, 1: "one_one"}
>>> my_dict
{1: 'one_one', 'two': 2, 3: 3.0}
>>> for key, value in my_dict.items():
...     print(f"{key} : {value}")
...
1 : one_one
two : 2
3 : 3.0
>>> my_dict[1]
'one_one'
>>> my_dict.get("two")
2
>>> my_dict[5]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 5
>>> my_dict.get(5, 0)
0
>>> my_dict[7] = "Seven"
>>> my_dict
{1: 'one_one', 'two': 2, 3: 3.0, 7: 'Seven'}

---

Dictionary의 내부 구조

• Set와 비슷하게 key 값의 해쉬값을 구한 후 해쉬값에 속해있는 bucket에 값을 저장한다

• set와 마찬가지로 순서가 없고 중복된 key 값은 허용 되지 않는다

---

언제 Dictionary를 쓸 까?

• 데이터베이스 처럼 키와 값을 묶어서 데이터를 표현해야 할때 유용
  실제로 데이터베이스 에서 읽어들인 값을 dictionary로 변환해서 사용 자주 한다

---

실습-1 (dictionary)

딕셔너리 만드는 법

코드

// dictionary create 1
dictionary1 = {"name":["Ryan","Lee"], "job":"sw engineer", "address": {"city":"seoul", "zip_code":"1234"} }

// dictionary create 2
dictionary2 = {}
dictionary2["name"] = ["Ryan", "Lee"]
dictionary2["job"] = "sw engineer"
dictionary2["address"] = {"city":"seoul", "zip_code":"1234"}

// dictionary create 3
let dictionary3 = Object({ "name":["Ryan","Lee"], "job":"sw engineer", "address":{"city":"seoul","zip_code":"1234"} });

결과

위의 예제에서 name키에서 'Ryan' 과 'Lee'를 각각 가져와보고 출력해보고,
address키에서 'seoul'과 zipcode '1234' 를 가져와서 출력

결과

---

실습-2 (hash)

해시란 단방향 (one way) 암호화이다 (입력 데이터를 변환하여 원본 데이터로 복호화할 수 없도록 하는 과정)
SHA(보안 해시 알고리즘)을 예로 들수 있다
SHA 함수를 이용하여 문자열 데이터를 입력받아서 해시값을 구할 수 있다

코드

var crypto = require('crypto')
var shasum = crypto.createHash('sha1')
shasum.update('wecode')
var hash_value = shasum.digest('hex')
console.log(hash_value);
console.log(hash_value.length);

var shasum2 = crypto.createHash('sha1')
shasum2.update('1234')
var hash_value_1234 = shasum2.digest('hex')
console.log(hash_value_1234);
console.log(hash_value_1234.length);

이처럼 hash 값은 일정한 길이를 가지고,
주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할때 사용

해시함수는 같은 문자열에 대해서는 같은 인덱스를 구할 수 있어야 해시함수로 구한 버킷의 인덱스를 저장 후에도 구할 수 있다

해시테이블은 해시함수와 버킷(bucket)의 리스트로 구현할 수 있는데
위의 wecode 의 해시값인 '283463014a3f8ab829fcf9087ff85d50da1d1bb6' 와
'1234'의 해시값인 '7110eda4d09e062aa5e4a390b0a572ac0d2c0220'을 버킷의 주소인 인덱스를 구할 때 사용하기에는 무리가 있어 보인다

버킷의 크기에 따른 인덱스로 변환하는 방법은
입력된 문자열의 각자리의 숫자를 더하는 방식인 Digit folding 과 비트연산을 활용한 방법등 다양한 방법이 있지만 우리는 이미 SHA1 알고리즘으로 해시값을 구하였으므로 간단하게 버킷의 사이즈로 나누는 방법인 나눗셈법을 적용하면 버킷의 인덱스를 초과하지 않는 인덱스를 구할 수 있다