알고리즘-자료구조-해시

개요

• 해시(Hash)는 어떤 값을 고정된 크기의 숫자로 변환하는 함수나 결과를 의미한다.
• 이 원리를 이용하여 데이터를 빠르게 저장하고 검색할 수 있도록 한것이 해시 기반 자료구조(hashmap, hashset 등)이다.
• 해시함수 구조 상 다른 값이 변환되어도 동일한 해시값을 가질 수 있다.

기본구성

• 해시 함수: 특정한 값을 해시값으로 변환하는 함수
• 해시 값: 계산되어 고정된 크기를 가지는 숫자값
• 해시 테이블: 해시 값을 기반으로 데이터를 저장하는 배열 구조
• 충돌처리: 서로 다른 키가 중복된 해시값을 가질 때를 대비하는 방법

충돌 및 해결방법

• 체이닝: 같은 인덱스에 여러 값을 연결 리스트 방식으로 저장
• 오픈 어드레싱: 충돌 시 인덱스를 선형/이차/이중 해시로 탐색

해시 기반 자료구조

• HashMap
• HashSet
• LinkedHashMap
• ConcurrentHashMap

장점

• 탐색/삽입/삭제가 평균 O(1)로 매우 빠르다.
• 복잡한 정렬이나 트리탐색 없이도 직접 접근 가능(해시값을 인덱스로 사용)

단점

• 해시 함수의 품질이 낮으면 충돌이 많아져 성능 저하
• 키의 순서 보장이 안된다(순서대로 저장 x).

정리

• 해시는 데이터를 빠르게 찾아가기 위한 주소 생성 원리이며, HashMap, HashSet 은 이 원리를 이용한 자료구조이다.