[Data Structure] Set,Dictionary,Hash

1. What You Will Learn

• Date Structure의 개념 필요성, 다양한 종류의 자료구조에 대해 이해
• Set의 개념과 장,단점 그리고 언제 사용하면 좋은지 이해
• Dictionary의 개념과 생성방법 그리고 어떻게 접근하는지 이해

2. Set

Set는 array나 list 처럼 순열 자료구조이다. 하지만 Set는 순서라는 개념이 존재하지 않는다. Set는 다음과 같은 특징을 갖고있다.

• 데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조(collection)
• 삽입 순서대로 저장되지 않는다. 특정한 순서를 기대할 수 없는 자료구조
• 수정 가능
• 동일한 값을 여러번 삽입 불가, 동일한 값이 여러번 삽입 되면 하나의 값만 저장
• Fast Lookup이 필요할 때 주로 사용
• Set에서 요소들이 저장될 때 순서
  1) 저장할 요소의 값의 hash 값을 구한다.
  2) 해쉬값에 해당하는 공간(bucket)에 값을 저장
• Set는 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없다. 순서가 없기 때문에 indexing도 없다.
• 그리고 해쉬값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없다.
• 해쉬값을 기반으로 저장하기 때문에 look up이 굉장히 빠름
  - look up : 특정 값을 포함하고 있는지를 확인 ==> 5 in my_set
  • Set의 총 길이와 상관없이 단순히 해쉬값 계산 후 해당 bucket을 확인하면 됨으로 0(1)

3.Hash

Hash는 단방향 암호화이다. 단방향이란 한 번 암호화 하면 복호화가 안된다는 뜻이다. 실제 값의 길이와 상관없이 hash 값은 일정한 길이를 가진다. 그럼으로 Hash는 주로 임의의 길이를 갖는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할 때 사용

• 중복된 값을 골라내야 할 때
• 빠른 look up이 필요할 때
• 순서는 상관 없을 때

4. Dictionary

Dictionary는 key-value형태의 값을 저장할 수 있는 자료구조, 실제 데이터 값과 데이터를 설명하는 key의 대응 관계를 표현할 때 유용하다. dictionary의 특성은 다음과 같다.

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