데이터구조 Data Structure - #2 Set, Dictionary, Hash

yojuyoon·2020년 7월 14일
0

TIL👌

목록 보기
16/23

Set이란?

Set은 array나 list처럼 순열 자료구조이다. 하지만 Set은 array나 list와 다르게 순서라는 개념이 존재하지 않는다.

Set의 특징

  • 데이터를 비 순차적으로 저장할 수 있는 순열 자료구조(collection)
  • 삽입 순서대로 저장되지 않는다. 즉 특정한 순서를 기대할 수 없는 자료구조
  • 수정 가능(mutable)
  • 동일한 값을 여러번 삽입 불가능하다. 만약 동일한 값이 삽입될 경우 하나의 값만 저장된다.
  • Fast Lookup이 필요할 때 주로 쓰인다.

Set의 구조

  • Set의 저장 순서는 1. 저장할 요소의 값의 hash 값을 구하고 2. 해쉬값에 해당하는 공간(bucket)에 값을 저장한다.
  • 이렇게 set은 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없고 순서가 없기 때문에 indexing도 없다.
  • 그리고 해쉬값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없는 것이다.
  • 해쉬값 기반으로 저장하기 때문에 look up (특정 값을 포함하고 있는지 확인하는 것) 이 굉장히 빠르다.

When To Use Set

  • 중복된 값을 골라내야 할 때
  • 빠른 look up을 해야할 때
  • 순서는 상관이 없을 때
const set1 = new Set([1, 2, 3, 4, 5]);
console.log(set1.has(1)); // true
console.log(set1.has(6)); // false


//add
const set2 = new Set();
set2.add(10).add(20).add(30) // set{10, 20, 30}

//clear
const set3 = new Set([10, 20, 30])
set3.clear();

console.log(set3) // set{}

Dictionary 란?

Key-value 형태의 값을 저장할 수 있는 자료구조이다. (다른 언어에서는 hashmap이나 hash table이라고 하기도 함)

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


When To Use Dictionary

  • 마치 데이터 베이스처럼 키와 값을 묶어서 데이터를 표현해야 할 때 유용하다. 실제로 데이터베이스에서 읽어들인 값을 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"} });

Hash 란?

해시란 단방향 암호화이다. 입력 데이터를 변환하여 원본 데이터로 복호화할 수 없도록 하는 과정이다.

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

단방향 해시 함수는 원본 메세지를 변환하여 암호화된 메세지인 다이제스트(digest)를 생성한다. 원본 메세지를 알면 암호화된 메세지를 구하기는 쉽지만, 암호화된 메세지로는 원본 메세지를 구할 수 없다. 때문에 단방향성(one-way) 이라고 한다.

예를들어 'test password'를 hash256 해쉬 함수를 사용하면
0b47c69b1033498d5f33f5f7d97bb6a3126134751629f4d0185c115db44c094e 값이 나온다.

만일 'test password2'를 hash256 해쉬 함수를 사용하면
d34b32af5c7bc7f54153e2fdddf251550e7011e846b465e64207e8ccda4c1aeb 값이 나온다.

이 예제를 보면 실제 비밀번호는 비슷하지만 해쉬 함수 값은 완전히 틀린 것을 볼 수 있다. 이러한 효과를 avalance라고 하는데, 비밀번호 해쉬 값 해킹을 어렵게 만드는 하나의 요소이다.

profile
하고싶은게 많은 사람. Front-end Developer

0개의 댓글