[TIL] Data Structure - Set, Dictionary, Hash _200414

이민석·2020년 4월 19일
0

TIL

목록 보기
10/14

Data Structure

Set

set 또한 array나 list처럼 순열 자료구조이다.
하지만 set에는 순서라는 개념이 존재 하지않는다.
set의 기본적인 특징은 다음과 같다.

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

set의 구조

  • array와 달리 set은 요소들을 순차적으로 저장하지 않는다.
  • set에서 요소들이 저장될 때 순서는 다음과 같다.
    1. 저장할 요소의 값의 hash 값을 구한다.
    2. 해쉬값에 해당하는 공간(bucket)에 값을 저장한다.
  • set은 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없다. 따라서 자연스럽게 indexing도 없다.
  • 해쉬값 기반으로 저장하기 때문에 lookup이 굉장히 빠르다.
    • Look up: 특정 값을 포함하고 있는 지를 확인하는 것
    • Set의 총 길이와 상관없이 단순히 해쉬값 계산 후 해당 bucket을 확인하면 되므로 O(1).

Set을 사용하면 좋을 때

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

 

Dictionary

Dictionary (혹은 hashmap이나 hash table이라고도 함)는 Key-Value 형태의 값을 저장할 수 있는 자료구조이다. 실제 데이터 값과 데이터를 설명하는 key의 대응 관계를 표현할 때 유용하다.
Dictionary의 특징은 다음과 같다.

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

Dictionary의 내부 구조

  • Set와 비슷하게 key 값의 해쉬값을 구한 후 해쉬값에 속해있는 bucket에 값을 저장한다.
  • 그럼으로 set와 마찬가지로 순서가 없고 중복된 key값은 허용 되지 않는다.

Dictionary를 사용하면 좋을 때

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

 

Hash

해시란 단방향 암호화이다. 입력 데이터를 변화하여 원본 데이터로 복호화할 수 없도록하는 과정입니다. SHA(보안 해시 알고리즘)을 예로 들 수 있습니다. SHA 함수를 이용하여 문자열 데이터를 입력받아서 해시값을 구할 수 있다. Hash 값은 일정한 길이를 가지고, 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할 때 사용됩니다.

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

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

profile
Still learning

0개의 댓글