알고리즘 )3장 문풀

 

7,,9

 

#11~

 

 

 

 

---

Progressive overflow==선형 조사법(Linear Probing)

 

평균 검색 거리는 어케 구핟라, 그곳으로 갔을떄, 있더라도 1이던가 있으면 0이 아니라ㅇㅇㅇ

입력넣을때 바로바로 구하는게 빠르나, ㅇㅇㅇ

"중간에 데이터를 삭제(Delete)하는 과정이 없을 때"

 

 

확장 해싱 데이터가 계속 늘어날 수 있는 환경에서 주로 사용하는 동적 해싱

Progressive overflow(선형 조사법)는 '크기가 고정된' 해시 테이블을 사용했습니다

 

 

 

 

해시 함수가 하필 K % 8인 이유가 있습니다.
어떤 수를 8로 나눈 나머지는 0부터 7입니다. 이것을 **이진수(Binary)**로 바꾸면 어떻게 될까요?

• 0 -> 000
• 1 -> 001
• ...
• 7 -> 111

즉, K % 8은 해시값을 딱 3비트(bit)짜리 이진수로 만들어주는 역할을 합니다.

 

 

 

• 디렉토리가 있는 버전: 확장 해싱 (Extensible Hashing)
• 디렉토리가 없는 버전: 선형 해싱 (Linear Hashing)

 

 

• 리니어(Linear): 버킷 하나가 넘쳤다고 바로 쪼개는 게 아니라, 임계치를 보고 결정한다. 
• 익스텐시블(Extensible): 버킷 크기가 곧 법이다. 넘치는 순간 바로 그 자리를 쪼갠다. 

 

 

근데 d=0이어도 2**0==1인데 그래서 처음엔 0한개인가 그러면 버킷 크기 10이면 1로 시작하는거 4개있어도 모두 0번 커킷에 들어가나ㅇㅇㅇ

 

그러면, 000 001 010 011 모두 깊이 2인가 000은 한명인데도 깊이 2인가, 쪼개졋으면 ? 근데 001은 깊이 2인ㄱ가

 

 

 

 

 

선형 해싱은 보통 **뒷자리(Suffix)**를 사용하므로, 새로운 비트는 **기존 비트의 왼쪽(앞)**에 추가됩니다

 

 

키(2, 3, 5...)를 그대로 이진수로 바꾸면 안 됩니다/ 해시 함수 결과값을 이진수로 바꾼다

 

 

시작은 0(또는 1)부터 하는 것이 맞음 

 

 

 Extensible hashing은 linear hashing보다 bucket array의 크기가 많다. (잘못됨)

• 해설: **Linear Hashing(선형 해싱)**은 오버플로우가 발생할 때마다 순차적으로 버킷을 추가(분할)하므로, 실제로 가득 차지 않은 버킷들도 분할되는 경우가 생겨 전체적인 **버킷 수(bucket array의 크기)**가 **Extensible Hashing(확장 해싱)**보다 더 많아지는 경향이 있습니다. (반면 확장 해싱은 디렉터리 크기가 2배씩 증가하는 단점이 있지만, 버킷 자체는 오버플로우가 발생한 것만 분할하므로 더 효율적으로 관리됩니다.)