TIL wecode 20. Data Structure - Set, Dictionary, Hash

Data Structure

1. Set

• array나 list와 같은 순열 자료구조이지만 순서 개념이 없다.
• 동일한 값을 삽입할 수 없고 만약 동일한 값이 들어온다면 하나의 값만 저장된다.
• 수정 가능하다.

1-1. Set의 구조

• Set에서 요소들을 저장하고 싶을 때,

1. 저장할 요소의 값의 hash값을 구한다. 이 때 실제 값의 길이와 상관없이 hash값은 일정한 길이를 가진다.
2. hash값에 해당하는 공간(bucket)에 값을 저장한다.

• 이렇게 Set에서는 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하게 되는데 이러한 이유로 순서가 없고 중복된 값을 저장할 수 없다.
• 해쉬값을 기반으로 저장하므로 look up이 빠르다.
  예를 들어 특정 값을 포함하고 있는지 확인할 때는 5 in my_set, 단순히 해쉬값 계산 후 해당 bucket을 확인할 때는 0(1)

1-2. Set은 언제 쓰일까

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

2. Dictionary

• key-value 형태의 값을 저장할 수 있는 자료구조
• set과 마찬가지로 순서의 개념이 없다.
• key의 값은 중복될 수 없으며 만일 중복된 key가 있으면 먼저 존재하던 key와 value를 대체한다.
• 수정 가능하다.
• 자바스크립트의 오브젝트와 유사하다.

2-1. Dictionary의 구조

• Dictionary에서 요소들을 저장하고 싶을 때,

1. key의 hash값을 구한다.
2. hash값에 해당하는 공간(bucket)에 값을 저장한다.

2-2. Dictionary는 언제 쓰일까

• 키와 값을 묶어서 데이터를 표현할 때 (실제로 데이터베이스에서 읽은 값을 dictionary로 자주 변환해 사용함)

3. Hash

• 단방향 암호화 기법을 말하며 해쉬함수(해쉬 알고리즘)을 이용하여 고정된 길이의 암호화된 문자열로 바꾼다.
• 입력값의 길이가 달라도 출력값은 언제나 고정된 길이로 반환하여 동일한 값이 입력되면 언제나 동일한 출력값을 보장한다.
• 해쉬함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해쉬값(hash value), 매핑하는 과정을 해싱(hashing)이라고 한다.
• 해쉬함수는 암호화가 아닌 검색을 위해 만들어졌기 때문에 10만번을 반복해도 1초도 안 걸리는 속도를 지녔다는 것이 큰 장점이다.

3-1. Hash 예시

이조은 - C498E4A2C96C1B8854B279FC1A1CEBEC8DE2FD7D732205EDA4D1F279229D362A
이쪼은 - EB99EF6EFDFCC5585CEBD4AA66B3CC0FCC047F81204C06F89601612C650816F1