<알고리즘> 검색 알고리즘(2)

 

1. 해시법

 이번 장은 검색뿐 아니라 데이터의 추가·삭제도 효율적으로 수행할 수 있는 해시법을 알아보자.

 

* 해시법

 - 데이터를 저장할 위치인 인덱스를 새로 구하는 것이다. 이를 통해 원소의 검색과 추가·삭제를 효율적으로 수행한다.

 

  위의 배열을 11로 나눈 나머지를 정리해보자.

 

 

 위에서 나온 해시값을 인덱스로 새로 배열을 해보자.

 

 

 - 위를 해시테이블이라 하며 새로운 원소 37을 추가하더라도 다른원소의 이동이 없는 것을 알 수 있다. 이는 기존의 배열에서 37을 추가하려면 뒤의 원소들을 모두 한칸씩 옮겨야 했던 것보다 효율적임을 알 수 있다.

 - 해시함수 : 위와 같이 키를 해시값으로 변환하는 과정

 - 버킷(bucket) : 해시테이블에서 만들어진 원소

 

* 해시충돌

 - 위의 예시에서 33을 추가하려면 버킷[0]에 들어가야한다. 그러나 이미 11이라는 값이 들어가있음을 볼 수 있다.

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

 

 - 체인법 : 해시값이 같은 원소를 연결 리스트로 관리하는 방법 (오픈해시법)

 - 오픈주소법 : 빈 버킷을 찾을 때 까지 해시를 반복하는 방법 (닫힌해시법)

 

* 체인법

 

 

 

 - 배열의 각 버킷에 저장하는 것은 인덱스를 해시값으로 한 연결리스트의 앞쪽 노드(head node)를 참조한다.

 

* 오픈주소법

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

 

 

 - 원소추가

   : 재해시를 위한 식 (58+1) % 11 로 나머지 4를 얻었으나 이것도 충돌이 일어난다. 그래서 다시 (59+1) % 11 로 재해시를 하자 5를 얻게되어서 인덱스 5에 58을 추가할 수 있다.

 

 - 원소삭제

   : 위의 그림에서 58또한 해시값은 3이다. 따라서 삭제 시 오류를 방지하기위해 다음과 같은 속성을 버킷에 부여한다.

 

    · (숫자) : 데이터 있음 

    · (-) : 비어있음

    · (★) : 삭제완료

 

 

 - 원소 검색

  : 위의 그림에서 28을 검색하려면 해시값이 6인 버킷을 들여다 볼 것이다. 속성이 비어 있으므로 검색실패이다.

 

  : 위의 그림에서 58을 검색해보자. 그럼 해시값이 3인 버킷을 보게되고 이는 삭제완료(★) 이므로 재해시하여 해시값 4를 보게된다. 하지만 여기에는 37이 저장되어 있으므로 재해시하여 58을 찾는다.

 

 

 

 

 

 

---

 

 

참고

 

이 글은 ‘이지스퍼블리싱’의 ‘자료구조와 함께 배우는 알고리즘 입문’을 공부 후 정리하며 쓴 글입니다.

작성된 모든 내용과 코드는 교재 및 관련 사이트를 참고하여 직접 재구성하였습니다.

 

 

Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편

http://www.easyspub.co.kr/20_Menu/BookView/381/PUB

 

이지스퍼블리싱 스터디룸 카페

Do it! 스터디룸 : 네이버 카페

 

교재 공식 깃허브

easysIT/doit_dsalgo_with_python