해시

밑에 영상들 보시면 굳이 이 포스트 글 안 읽어도 될 것 같습니다 ~

그래도 글 한번 읽어주세요..

 

https://youtu.be/xls6jEZNA7Y

https://youtu.be/HraOg7W3VAM\

 

해시

- 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행됨

- 해시 함수에 의해 얻어지는 값

- 해시 값, 해시 코드, 해시 체크섬 이라고도 함

- 해시 관련 개념들

• 해시 함수 (hash function)
• 해싱 (hashing)
• 충돌 (collision)
• 해시 테이블 (hash table)
• key, value, bucket

 

 

1) 해시 함수 (hash function)

- 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

- 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경함

- 저장소를 효율적으로 운영할 수 있도록 도와줌

 

 

2) 해싱 (hashing)

- 해시 함수에서 Key값을 hash로 변환하는 과정

- 해싱을 통해 나온 해시 값이 데이터의 저장 위치가 된다고 생각하면 됨

 

 

3) 충돌 (collision)

- 서로 다른 문자열이 Hash function을 통해 나온 Hash 값이 같은 경우 (중복되는 경우)

- 서로 다른 키(key)가 같은 해시(hash)가 되는 경우

- 충돌 해결방안

• Separating Chaining - Linked List, Tree (Red-Black Tree)
• Open addressing - Linear Probing, Quadratic Probing, Double hashing
• 리사이징(Resizing)

 

4) 해시 테이블 (hash table)

- 연관배열 구조를 이용하는 자료구조 중 하나임

- 단순하게 생각하면 Key - Value 의 구조라고 할 수 있음

- 연관배열 자료구조 (associative array) 는  key  &  value가  1:1 로 이루어진 구조

 

 

5) key, value, bucket

- key

• key - value 형태에서  key 를 의미
• 고유한 값이어야 함
• hash function 의  input 으로 사용됨

 

- value

• key - value 형태에서  value 를 의미
• bucket 에 저장되는 값
• Key 값과 매칭되어 저장, 삭제, 검색 접근이 용이해야함

 

- bucket

• 데이터를 저장하는 테이블, 즉 저장 공간을 의미

 

6) 실습

- python 으로 실습

- 파이썬에서는 Dictionary 라는 자료구조를 통해 해시를 제공

- 문제

 

- 프로그래머스 폰켓몬 문제

 

- 나의 풀이

 

당연히 틀림..

 

- 다른 사람 풀이

 

- 다른 사람들이 set 함수를 사용한다지만 우리는 hash 를 이용해서 풀어야 하기 때문에

- 이 분의 풀이를 가져왔습니다.

 

- 성공 !