탐색을 위한 해시 (해시가 값 검색을 위해 사용되는 원리)

탐색을 위한 해시

해시 목적 : 탐색을 엄청나게 빨리 하기 위함 ⇒ 해시 값을 키로 이용하면

배열로 원하는 데이터에바로 접근할 수 있음

탐색 할때는 해시 함수 결과를 해시 주소(인덱스)로 해석

 

키 : 값의 개념으로 direct 접근

근데 충돌 무조건 발생함 -> 잘 관리하자

 

충돌관리

• 슬롯 여러개 관리 : 슬롯 만들어서 같은 해시주소에 여러개 저장가능하게!
• 선형 조사법 : 슬롯 오버플로나면 다른 해시 주소(바로 다음)에 저장 ⇒ 선형조사법
  • 근데 이러면 군집화 현상 발생.
  • 군집화 : 특정 지역에 키 값이 몰리는 현상(앞 찼네? 바로 뒤로.. 찼네?? 바로 뒤로..)
• 이차 조사법 : 키가 몰리는거 방지하기위해 다른 위치(4칸 뒤, 8칸 뒤..)로 점프해서 저장토록하면??? ⇒ 이차조사법
  • 근데 이거 규칙 일정하면 또 2차 군집화 가능
• 이중 해싱 : 해시 함수 한번더!!! ⇒ 이중해싱
• 채이닝 : 슬롯을 연결리스트로 관리 (n의 시간복잡도)