[알고리즘] 해시(Hash) 이론 이해하기

해시 Hash 알고리즘

1. 개념

• Key : Value 형태를 갖는 자료구조
• 전화번호부를 생각하면 이해하기 쉬움
  • 이름 = Key, 전화번호 = Value
  • 무언가 찾기 위한 검색어 = Key, 검색 결과 = Value

종류	배열	해시
내용	정수로만 접근할 수 있음	String type이나 다른 어떤 데이터형을 기반으로 자료구조 접근, 데이터 관리 가능 = 모든 Data type으로 접근이 가능함
예시	친구 이름을 알아도 전화번호를 검색할 수 없음 → For문을 끝까지 돌려서 내가 찾는 친구가 맞는지 확인해야 함	전화번호부
장점	구현이 쉬움 검색 성능이 좋음(index를 이용한 무작위 접근 가능) 참조를 위한 추가 메모리 할당이 없음	데이터 저장/검색 속도가 빠름 key 중복여부 확인이 쉬움
단점	자료 삽입/삭제 시 비효율적(다음 항목의 모든 요소를 이동시켜야 함) 한번 지정한 크기를 바꿀 수 없음 메모리 재사용이 불가능	일반적으로 저장공간이 비교적 많이 필요함 여리 key의 주소가 동일할 경우, 충돌 해결을 위한 자료구조가 필요함
시간복잡도	일반: O(1) 최악: O(n)	일반: O(1) 최악: O(n)

 

 

2. 예시

• 프로그래머스 - '완주하지 못한 선수' 문제
• [알고리즘] 해시 - Lv.1 완주하지 못한 선수

종류	설명 및 예시
get()	- 딕셔너리에 주어진 key 값을 반환하는 메서드 - 주어진 key가 딕셔너리에 존재하면 key 값 반환 / 없으면 기본값(미지정 시 None) 반환 - dict = {'a': 1, 'b': 2}라는 딕셔너리가 있고, value = dict.get('a')를 한다면 1 출력 - value = dict.get('c', 'N/A')를 한다면 N/A 출력

 

 

3. Hash를 쓰는 조건 

• String을 기반으로 정보를 기록 & 관리해야 할 때는 단순 배열을 쓸 수 없으니 Hash를 활용하자!
• 프로그래머스 - 완주하지 못한 선수
  • '선수 이름'(String) → 완주 여부 판단
• 프로그래머스 - 신고 결과 받기
  • 게시판 사용자 중 신고 당한 사람을 기준으로 신고자 목록 관리
  • 신고 당한 사람의 '이름'(String)
• 프로그래머스 - 위장
  • 옷의 종류에 따라 몇 개의 옵션이 있는지 카운트 해야 함
  • 옷의 종류가 정수가 아니라 '얼굴', '상의', '하의', '겉옷'(String)

4. 정리

• Hash는 전화번호부와 같다
• 대부분 그 Key가 String임

---

 

참고 영상: 개발자로 취직하기 - 해시 Hash 알고리즘 설명 5분만에 이해하기

https://youtu.be/zFL29ydL9D8?si=VFqkQ1EYd5Y43fVn