알고리즘) 3장 퀴즈준비

 

 

(용어들)

Linear hashing에서는 오버플로우 버킷이 생성될 수 있다[  ]

 

더블해싱 계산법 

 

 

삭제시, 해시테이블이 매번 재구성 된다 : 입력순서 똑같이 다시 넣어야하나 [  ]ㅇㅇ

 

 

 

#16번 

 

---

Progressive Overflow는**선형 탐색(Linear Probing)**과 같은 개념입니다

 

 

 

 

 

 

 

( 테이블 그리기전에, 다음 문제들 보고, search Length구하는 문제 있으면 미리 계산하면서 하는게 ) 

 

 

 

 

 

 

 

 

 

Chaining에서 탐색시간[   ]

 

 

 

 

똑같은 말임 

 

(이때 나머지를 탐색시간에 적지않도록 주의 ) 

 

 

 

 

Chaining with a separate overflow area , 방식으로 충돌을 해결할 경우 해쉬 테이블과 오버플로우 영역을 그려라

(걍 연결리스트방식이네 ) 

(둘다 overflow는 들어가네 ) 

 

 

 

 

리니얼 프루빙에서 임계값

 

 

(wjrwo..)

 

 

 

15%3

15%7

이거 암산하지말고 적어서 해야겟는데 실수함 

 

 

 

 

 

 

 

 

 

 

해쉬 테이블의 적재율(packing density)은 해쉬 테이블의 크기에 대한 적재 레코드 수의 비율이다

a에 대한 b의 비율 식 어케 세우지 

 

 

 

 

 

 

 

 

User PM 5:26

 

 

'현재 해쉬 테이블 안에 실제로 들어있는 데이터(키)의 개수

 

 

 

 

갯수(사람 몇명인지 실수 ) 

 

 

익스텐시블(한번에 두배씩 디렉토리 늘어나던거_): 

 

그 버킷뒤에 숫자 적어주는거, 리니어에서는 없었던가 ㅇㅇ

 

 

 

익스텐시블, 리니어, 젤처음에 어케 해야하지

(버킷 갯수만큼 채워두면 되나 그냥 )

 

 

존의 포인터들은 일단 그대로 복사됩니다. (예: 00을 가리키던 것들은 000, 001이 되어 같은 곳을 가리킴)

• 나머지 버킷들(00, 01, 10 계열)은 쪼개지지 않았으므로, 디렉토리 2개당 버킷 1개씩 연결된 상태를 유지합니다. (Local Depth는 그대로 2)

 

 

 

 

 

두 번째 해쉬 함수의 적용시 충돌이 발생하면progressive overflow . 로 해결한다

 

 

처음부터 

크기많이 늘리게 되는거나 

익스텐시블일때 

0000 0001 0010 이렇게 드러오면 ㅇㅇ

 

 

hi(x) = (h(x) + i * f(x)) % 7

두번째 해시값으로 나온값을, 최종값으로 안쓰도록 주의 

 

 

 

 

더블해싱으로 평균탐색길이 구할때는 i가 늘어날때마다 

search length도 1씩 늘려줘야하나 ㅇㅇ

 

근데 i=0인것만 searchlength1이고, i=1이어도 searchlength2인가, 

이미 거기에 자리 차지해있다는거 확인햇으니깐, ?