[[Data Structure] Set & HashMap]

Set

array 나 list 와 같은 순열 자료구조(collection)이나 순서라는 개념이 없다는 점에서 구별된다.

• 데이터를 비순차적(unordered)으로 저장
• 삽입 순서대로 저장되지 않는다.
• 수정이 가능하다(mutablew)
• Fast Lookup 이 필요할 때 주로 사용된다.
• 동일한 값을 여러번 삽입할 수 없고 동일 한 값이 여러번 삽입되면 하나의 값만 저장된다.

Set의 구조

• Array와 달리 요소들을 순차적으로 저장하지 않고 다음과 같은 절차를 따른다.
  1. 저장할 요소의 hash 값을 구한다.
  2. hash값에 해당하는 공간(bucket)에 값을 저장한다.
• 이렇듯 저장하고자 하는 값의 해쉬값에 해당하는 bucket 에 값을 저장하기 때문에 순서가 없고 indexing 도 없다.
• 해쉬값 기반의 bucket 에 저장하기 때문에 중복된 값을 저장할 수 없는 것이다.
• 해쉬값을 기반으로 하기 때문에 look up 이 빠르다.
  - look up : 특정값을 포함하고 있는지 확인 하는 것 ex) 5 in my_set
  • Set 의 총 길이와 상관없이 단순히 해쉬값 계산 후 해당 bucket 을 확인하면 됨 0(1)

Set 을 사용하는 경우

• 중복된 값을 골라내야 할때

• 빠른 look up 을 해야 할때

• 그러면서 순서는 상관 없을때

  hash 란?

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

  해시 함수는 임이의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수입니다. 암호 알고리즘에는 키가 사용되지만, 해시 함수는 키를 사용하지 않으므로 같은 입력에 대해서는 항상 같은 출력이 나오게 됩니다. 이러한 해시함수를 사용하는 목적은 메시지의 오류나 변조를 탐지할 수 있는 무결성을 제공하기 위해 사용됩니다.

참고
해쉬란?

Dictionary/HashMap/HashTable

• key-value 형태의 값을 저장할 수 있는 자료구조로서 이름:정우성 같이 실제 데이터 값과 데이터를 설명하는 key 의 대응관계를 표현할 때 유용하다.

• Set 과 마찬가지로 특정 순서대로 데이터를 리턴하지 않음

• key의 값이 중복될 수 없고 만일 중복된 key가 있을 경우 먼저 있던 key 와 value를 대체한다.

• 수정 가능

  Dictionary 의 내부구조

  

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

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

Dictionary를 사용하는 경우

• 데이터베이스처럼 키와 값을 묶어서 데이터를 표현해야 할 때 유용하다.

Dictionary 실습

• 첫번째 방법 : 데이터가 주어지거나 딕셔너리의 내용이 고정되어 있는 경우 사용
• 두번째 방법 : dictionary2 변수를 선언해놓고 데이터베이스를 조회해서 필요한 정보를 동적으로 채워야 할 때 편리
• 세번째 방법 : (숫자로 딕셔너리의 키를 사용할 수 있지만) 문자열만 키로 사용되는 경우 사용할 수 있는 방법