검색 알고리즘_해시법

~ 목차 ~

• 해시법
• 해시 충돌
  • 체인법
  • 오픈 주소법

---

 

정렬된 배열에서 원소 추가/삭제 시,  추가/삭제 위치 뒤/앞의 원소들 한칸씩 뒤/앞으로 밀어야 한다

= 복잡도 O(n)

 

해시법

 

검색과 데이터 추가/삭제도 효율적으로 수행할 수 있는 방법

• 해시 값(hash value) : 배열의 키(= 원소의 값) %원소의 개수
• 해시 함수(hash function) : 키->해시값 과정
• 해시 테이블(hash table) : 해시값을 인덱스로 하여 원소를 새로 저장한 배열
• 버킷(bucket) : 해시 테이블에서 만들어진 원소

 

해시 충돌

키와 해시값은 일반적으로 n:1 관계

해시 충돌 : 저장할 버킷이 중복되는 현상

 

해시 충돌 대처법

1. 체인법 : 해시값이 같은 원소 연결리스트로 관리
2. 오픈 주소법 : 빈 버킷을 찾을때까지 해시 반복

 

1. 체인법(Chaining)

= 오픈 해시법(Open hashing)

해시값이 같은 데이터를 체인 모양의 연결리스트로 연결하는 방법

 

2. 오픈 주소법(Open addressing)

= 닫힌 해시법(Closed hashing)

충돌 발생 시 재해시를 수행해 빈 버킷을 찾는 방법