10 - 해시법 (자바편)

🌏 주제 : 10 - 해시법 (자바편)

---

 

 

 

 

 

 

 

 

 

 

🌏 해시법

---

• 해시법은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하여 검색,추가,삭제를 효율적으로 수행

 

 

 

 

 

 

 

 

🌏 충돌(Collision)

---

• 만약 333이라는 값이 인덱스 14에 저장되어있는데 이후에 130이라는 값(나머지 14)을 저장한다고 가정
  -> 이렇게 저장할 버킷이 중복되는 현상을 충돌이라고 한다.
  -> 해시 함수는 가능하면 해시값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다.

 

 

• 충돌 대처법 2가지
  1. 체인법 : 해시값이 같은 요소를 연결 리스트로 관리
  2. 오픈 주소법 : 빈 버킷을 찾을때 까지 해시 반복

 

 

 

 

 

 

 

🌏 오픈 주소법

---

 

• 충돌이 발생했을 때 재해시를 수행하여 비어있는 버킷을 찾는 방법
  -> 닫힌 해시법이라고도 함

 

• 18 삽입 하고자 할때 18 % 13 = 5 충돌
  -> (18+1) % 13 = 6 충돌
  -> (19+1) % 13 = 7 삽입