알고리즘)3장

 

 

 

레드블랙, 리프가 아닌 노드 삭제 [  ]

 

 

---

 

선형 탐색법은 해시 테이블에서 **충돌(Collision)**이 발생했을 때, "그럼 바로 다음 칸에 자리가 있나?" 하고 순차적으로 빈 공간을 찾아가는 아주 단순한 방식입니다.

1. 기본 원리

1. 해시 값 계산: h(key)를 통해 데이터가 들어갈 원래 위치 i를 찾습니다.
2. 확인 작업 (get(key) 기준):
   • Search Hit: 인덱스 i에 내가 찾는 데이터가 딱 있으면? 바로 성공!
   • Search Miss: 인덱스 i가 비어(null) 있으면? "아, 여기 데이터가 없구나" 하고 실패!
   • Collision (충돌): 인덱스 i에 다른 데이터가 들어있으면? "내 자리를 누가 차지했네?" 하고 다음 칸(i+1)으로 이동합니다.

2. "언제까지?" 탐색할까? (슬라이드 마지막 질문의 답)

충돌이 발생해서 다음 칸을 계속 뒤질 때, 멈추는 기준은 3가지입니다.

1. 데이터를 찾았을 때: 다음 칸, 그다음 칸을 확인하다가 내가 찾는 key를 발견하면 멈춥니다. (성공)
2. 빈 공간(null)을 만났을 때: 빈 칸이 나왔다는 건, "이 데이터는 우리 테이블에 저장된 적이 없구나"라는 뜻입니다. (선형 탐색은 빈칸이 생기기 전까지만 데이터를 채우기 때문입니다.) (실패)
3. 한 바퀴 다 돌았을 때: 테이블 끝(M-1)까지 갔는데도 못 찾으면 다시 0번 인덱스로 돌아가서(Modulo 연산 % M) 계속 찾습니다. 그러다 처음 시작했던 i로 돌아오면 "테이블이 꽉 찼고 데이터도 없다"는 뜻입니다. (실패)

 

 

 

 

1. Packing Density와 Collision Ratio(충돌률)의 관계

• 밀도가 낮을 때 (N이 작을 때): 테이블이 텅텅 비어있으니, 해시 함수가 찍어준 자리에 바로 앉을 확률이 높습니다. 충돌이 거의 안 나니 성능이 매우 좋죠.
• 밀도가 높을 때 (N이 M에 가까워질 때): 빈자리가 거의 없습니다. 내가 앉으려는데 이미 누가 있고, 그 옆 칸도, 그다음 칸도 이미 꽉 차 있을 확률이 높습니다.
• 결과: 적재 밀도가 높아질수록 충돌(Collision)이 기하급수적으로 늘어납니다. 선형 탐색법은 특히 빈칸을 찾을 때까지 계속 옆으로 가야 하므로, 한 번 충돌이 나면 연쇄적으로 시간이 엄청나게 걸리게 됩니다(이걸 '군집화'라고 합니다).

2. Packing Density와 Space Utilization(공간 활용도)의 관계

• 밀도가 높으면: 메모리 공간을 아주 알뜰하게 쓰고 있는 겁니다. (공간 활용도 UP)
• 밀도가 낮으면: 빈 공간이 너무 많아서 메모리가 낭비됩니다. (공간 활용도 DOWN)

---

결론: 왜 이게 중요할까?

선형 탐색법(Linear Probing)의 성능은 이 **적재 밀도(αα에 전적으로 의존합니다.

• 보통 적재 밀도가 **0.5(50%)**를 넘어가기 시작하면 성능이 눈에 띄게 떨어지기 시작하고, 0.7~0.8이 넘어가면 검색 속도가 엄청나게 느려집니다.
• 그래서 보통 개발자들은 테이블이 절반 정도 차면 테이블 크기를 2배로 키우는 Rehashing 작업을 해서 적재 밀도를 다시 낮춰줍니다.

 

 

 

 

• 선형 탐색법( B=1 ): 주소 하나당 데이터가 딱 하나만 들어갈 수 있는 구조입니다. (독서실 1인실) 누가 앉아 있으면 무조건 옆방으로 가야 하죠.
• 버킷 방식( B>1 ): 주소 하나가 여러 개의 슬롯(Slot)을 가질 수 있는 구조입니다. (4인용 테이블이 있는 방) 같은 주소가 나와도(충돌이 나도) 빈 의자가 있다면 옆 주소로 갈 필요 없이 그 방에 같이 앉으면 됩니다.

• Bucket 내에서의 검색 방법?
  버킷 안의 슬롯은 보통 개수가 많지 않기 때문에(예: 4개, 8개), 그 안에서는 그냥 **순차 탐색(Linear Search)**으로 데이터를 찾습니다.

 

 

 

 

선형탐색법에서 삭제 

 

방법 3: 데이터 재배치 (슬라이드에서 권장하는 방식)

7번(Morris)을 지웠다면, 그 뒤에 있는 데이터(8번 Smith 등)를 살펴보고 앞으로 당길 수 있는지 확인하는 방식입니다.

 

 

방법 1: Morris만 삭제하고, 나머지는 그대로 두자 (단순 삭제)

• 어떻게 하나요?: 7번 칸(Morris)을 그냥 깨끗하게 비워버립니다(null로 만듦).
• 결과 (치명적인 문제 발생):
  • 이제 Smith를 찾으려고 하면, 해시 주소인 5번부터 탐색을 시작합니다.
  • 5번(Adams), 6번(Jones)을 지나 7번이 비어있는 것(null)을 보고 "어? 빈칸이네? 찾는 데이터가 없구나" 하고 멈춰버립니다.
  • 문제: 실제로는 8번에 Smith가 있는데도 찾지 못하는(Search Miss) 오류가 발생합니다.
• 평가: 이 방법은 뒤에 있는 데이터들을 앞으로 당겨주는 '재배치' 작업이 동반되지 않으면 사용해서는 안 되는 위험한 방식입니다.

---

방법 2: Morris의 자리에 tombstone(묘비)을 두자 (마킹 삭제)

• 어떻게 하나요?: 7번 칸의 데이터를 지우는 대신, **"여기는 원래 데이터가 있었지만 지금은 비었음"**이라는 특별한 기호(슬라이드에서는 ######)를 남깁니다. 이것을 **tombstone(묘비)**이라고 부릅니다.
• 결과 (연결고리 유지):
  • Smith를 찾을 때: 5, 6번을 지나 7번의 '묘비'를 만납니다. 컴퓨터는 "아, 여기 데이터가 지워진 거니까 뒤에 탐색을 더 해봐야겠네!" 하고 8번까지 가서 Smith를 찾아냅니다. (성공!)
  • 새 데이터를 넣을 때: 빈자리를 찾다가 7번의 '묘비'를 발견하면, "어차피 비어있는 칸이니 여기다 새 데이터를 써야지" 하고 덮어씌울 수 있습니다. (효율적!)
• 평가: 구현이 매우 간단하고 검색 오류도 해결할 수 있어 자주 쓰이는 방식입니다.

 

 

 

 

 

 

 

 

 

 

 

 

묘비 방식은 삭제 문제를 간단히 해결해주지만,

1. Searching Delay (검색 지연)

• 상황: 이전 예시에서 **Smith(8번)**가 삭제되어 그 자리에 묘비가 생겼다고 가정해봅시다.
• 문제점: 묘비는 "여기 데이터가 있었으니 뒤를 더 찾아봐"라는 표지판입니다. 만약 Smith 뒤에 다른 데이터가 더 있었다면, 그 데이터를 찾기 위해 이미 지워진 자리(묘비)들을 일일이 다 거쳐서 지나가야 합니다.
• 왜 지연인가?: 진짜 빈칸(null)을 만났다면 바로 탐색을 멈췄을 텐데, 묘비가 많아지면 "실제로 데이터는 없는데 묘비들 때문에 탐색 길이는 여전히 긴" 상태가 유지됩니다. 즉, 테이블에 데이터가 별로 없어도 검색 속도가 빨라지지 않는 현상이 발생합니다.

2. 중복 확인 곤란 (Duplicate Check)

• 상황: 새로운 Smith를 다시 삽입하려고 합니다.
• 문제점: 해시 테이블은 보통 중복된 키를 허용하지 않습니다. 그래서 삽입하기 전에 "이미 Smith가 이 테이블에 있는지" 먼저 확인해야 합니다.
• 왜 곤란한가?:
  1. 탐색 중에 7번에서 묘비를 발견했습니다. "오, 여기 빈자리네? 여기 넣을까?" 하고 바로 넣으면 안 됩니다.
  2. 왜냐하면, 혹시라도 뒷번호(예: 8번)에 이미 Smith가 살고 있을지도 모르기 때문입니다.
  3. 결국 묘비를 발견하더라도 삽입을 확정 짓지 못하고, 진짜 빈칸(null)이 나올 때까지 끝까지 뒤져서 중복이 없는지 확인한 다음에야 다시 돌아와서 묘비 자리에 넣어야 합니다.

 

 

 

 

 

 

문제점: Tombstone 과다 존재 (Searching Delay)

• 상황: 데이터를 넣고 지우는 작업이 수천 번 반복되면, 테이블에 실제 데이터는 2~3개뿐인데 나머지는 전부 '묘비'로 가득 찰 수 있습니다.
• 결과: 데이터를 찾을 때 실제 빈칸(null)이 나올 때까지 묘비들을 하나하나 다 확인하며 지나가야 하므로, 검색 속도가 엄청나게 느려집니다. (데이터가 거의 없는데도 테이블 전체를 다 뒤지는 꼴이 됩니다.)

---

2. 해결 방안 (어떻게 고칠 것인가?)

① Local reorganization at each deletion (삭제할 때마다 부분 정리)

• 방법: 데이터를 지울 때 묘비를 남기지 말고, 그 즉시 뒤에 있는 데이터들을 조사해서 앞으로 당겨주는 방식입니다. (아까 '방법 A'로 설명드린 재배치 방식입니다.)
• 장점: 묘비가 아예 안 생기므로 검색 속도가 항상 최상으로 유지됩니다.
• 단점: 삭제할 때마다 뒷사람들을 챙겨야 하니 삭제 연산 자체가 조금 무거워집니다.

② Complete reorganization after threshold (임계치 넘으면 전체 재구성)

• 방법: 평소에는 편하게 묘비를 쓰다가, 묘비 개수가 일정 수준(예: 전체의 30%)을 넘어가면 테이블을 통째로 새로 만드는 방식입니다.
• 과정: 새 테이블을 만들고, 묘비는 다 버리고 진짜 데이터들만 다시 해싱해서 예쁘게 정렬합니다. (이를 '리해싱, Rehashing'이라고도 부릅니다.)
• 비유: 방이 지저분해질 때마다 치우는 게 아니라, 너무 더러워지면 대청소를 한 번 싹 하는 것과 같습니다.

 

 

 

1. 해시 함수 설계 (Hash Function Design)
   • "Key를 어떻게 숫자로 바꿀까?"를 고민하는 단계입니다. (예: % M 연산, 중간 제곱법 등)
   • 목표: 데이터를 최대한 골고루 퍼뜨려서 충돌 자체를 안 나게 만드는 것.
2. 충돌 해결 알고리즘 설계 (Collision Resolution) ← [지금 여기!]
   • "아무리 함수를 잘 짜도 충돌은 나기 마련인데, 그때 어떻게 할까?"를 고민하는 단계입니다.
   • 여기서 **개방 주소법(Open Addressing)**이라는 큰 분류가 있고, 그중 가장 단순한 방법이 바로 **선형 탐색법(Linear Probing)**입니다.

 

 

 

 

삭제할때 앞으로 당기는부분 

• 어떤 데이터가 삭제되어 **빈 공간(Gap)**이 생기면, 그 뒤에 있는 데이터들을 살펴봅니다.
• 이때, 뒤에 있는 데이터의 원래 집(Home Address) 주소가 현재 빈 공간의 주소보다 작거나 같으면, 그 데이터를 빈 공간으로 당겨올 수 있습니다.

빈 자리를 채울 수 있는 후보들 중에서 가장 뒤에 있는 데이터가 먼저 이동합니다."

 

이동 횟수 최소화: 중간에 있는 Dean을 먼저 옮기면 나중에 Evans를 또 옮겨야 할 수도 있습니다. 하지만 가장 뒤에 있는 애(Evans)를 한 번에 앞의 빈칸으로 점프시키면, 빈칸이 뒤쪽으로 크게 밀려나면서 정리가 한 번에 끝날 확률이 높습니다.

 

 

 

재해싱은 '국소적 재구성'과는 규모가 다른 작업입니다.

• 부하율(Load Factor)이 임계치를 넘었을 때: 테이블이 너무 꽉 차서(보통 70~80% 이상) 충돌이 너무 자주 발생할 때, 더 큰 테이블을 만들고 모든 데이터를 다시 해싱하여 옮깁니다.
• 성능이 급격히 떨어질 때: 삭제가 너무 많이 일어나서 '삭제 마크(Tombstone)'가 많아지거나, 데이터 분포가 불균형해졌을 때 전체적인 최적화를 위해 수행합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

이중 해싱(Double Hashing)**이라고 하는데요, 앞서 본 선형 조사법이나 이차 조사법의 단점을 완전히 해결

점프하는 간격(보폭)조차도 해시 함수로 정하겠다

 

 

 

 

 

 

 

 

f자체가 보폭인거니깐 

 

 

 

 

 

 

 

 

 

1 적재 밀도(Packing Density)는 낮아야 한다

 

2 해결책 (MaxLoop): 무한정 기다릴 수 없으니, "딱 몇 번까지만 쫓아내기 시도를 해보자"라고 정해둔 한계치가 MaxLoop입니다.
Rehash(재배치): 만약 쫓아내기 횟수가 MaxLoop를 넘어가면 "아, 이 테이블은 답이 없다"라고 판단하고, 테이블 크기를 2배로 키운 뒤 모든 데이터를 처음부터 다시 해싱해서 집어넣습니다.

 

장점: 이렇게 빈 공간을 많이 주는 대신, 데이터를 찾을 때는 딱 두 군데만 보면 되니까 찾기 속도는 끝내주게 빠르다.

 

 

 

지금까지 배운 방식들은 모두 **Static Hashing(정적 해싱)**에 속합니다.

이제부터는 데이터의 양에 따라 테이블이 스스로 커졌다 작아졌다 하는 **Dynamic Hashing(동적 해싱)

 

 

*Static Hashing(정적 해싱)

• 특징: 처음에 테이블 크기를 딱 정해놓고 시작합니다.
• 문제점:
  • 데이터가 너무 많아지면? 충돌이 너무 잦아져서 성능이 뚝 떨어집니다.
  • 해결하려면? 테이블 크기를 2배로 키우고 모든 데이터를 다시 계산해서 넣어야 합니다(Rehashing). 이게 엄청난 노가다이고 시간이 오래 걸립니다.
  • 데이터가 너무 적으면? 빈 공간이 너무 많아 메모리 낭비가 심합니다.
• 슬라이드 내용: "현재/예상 테이블 크기 기준 설계", "주기적으로 재계산(Rehash)" 해야 한다는 말이 바로 이 한계를 말합니다.

 

 

 

Dynamic Hashing

 

• Dynamic directory size: 주소록(디렉터리)의 크기가 가변적입니다.
• Controlled overflow/underflow: 데이터가 넘치면(overflow) 방을 쪼개고, 너무 없으면(underflow) 방을 합칩니다.
• 가장 큰 장점: 테이블이 커질 때 모든 데이터를 다시 계산(Rehash)할 필요 없이, 문제가 생긴 방만 쪼개면 됩니다.

 

 

 

 

 익스텐시블 

 

 

 

 

 

 

!=버킷갯수 

• 버킷 크기 (Bucket Capacity): 하나의 보라색 박스(버킷) 안에 **"데이터가 최대 몇 개 들어갈 수 있는가"**입니다. 이건 시스템을 만들 때 처음에 정해놓는 고정된 값입니다.
• 지역 깊이 (Local Depth): 이미지 속 버킷 옆에 적힌 숫자(1, 2, 2)입니다. 이건 크기가 아니라, **"이 버킷이 해시값의 앞 몇 자리 비트를 기준으로 데이터를 모았는가"**를 나타내는 '기준'입니다.

 

 

 

• 버킷 쪼개기: 기존 0번 버킷을 지역 깊이 2인 두 개의 버킷으로 나눕니다.
  • 00 버킷: 앞 두 자리가 00인 데이터 ①(000...)
  • 01 버킷: 앞 두 자리가 01인 데이터 ②(011...), ④(010...)
• 참고: 1번 버킷은 아직 쪼갤 필요가 없으므로 지역 깊이 1을 유지하며, 디렉터리 10과 11이 동시에 이 버킷을 가리킵니다.

 

 

 

• 전역 깊이 ( i ): 2
• 디렉터리 개수: 4개 (00, 01, 10, 11)
• 사용 중인 버킷 수: 3개
  1. 버킷 A (지역 깊이 2): [①] (주소 00에서 가리킴)
  2. 버킷 B (지역 깊이 2): [②, ④] (주소 01에서 가리킴)
  3. 버킷 C (지역 깊이 1): [③, ⑤] (주소 10, 11에서 공통으로 가리킴)

 

 

1. Directory의 크기가 2배로 증가할 때 처리 시간 증가

• 상황: 전역 깊이가 10에서 11로 늘어난다고 가정해 봅시다.
• 문제: 주소록 칸이 1,024개에서 2,048개로 순식간에 2배가 됩니다.
• 이유: 컴퓨터 입장에서는 갑자기 새로운 메모리 공간을 크게 할당받고, 기존에 있던 1,024개의 화살표(포인터)를 새로운 칸들에 일일이 복사해주어야 합니다. 데이터 하나 넣으려다가 갑자기 주소록 전체를 이사시켜야 하니, 그 순간 시스템이 **'버벅(Latency)'**거리게 됩니다.

2. 메모리 부족 및 디스크 I/O 증가

• 상황: 데이터가 정말 많아져서 주소록이 수백만 칸이 되었다고 칩시다.
• 문제: 원래 주소록은 속도를 위해 **메모리(RAM)**에 올려두고 씁니다. 그런데 2배씩 계속 늘어나다 보면 어느 순간 메모리에 다 안 들어가는 크기가 됩니다.
• 결과: 메모리가 부족하면 주소록의 일부를 **디스크(HDD/SSD)**에 저장해야 합니다. 해싱의 장점은 "한 번에 딱 찾기"인데, 주소록을 보려고 느린 디스크를 한 번 더 읽어야 하니 속도가 엄청나게 느려집니다.

3. 특정 bucket에 레코드가 폭주할 경우 (데이터 편중)

• 이게 가장 치명적인 단점입니다.
• 상황: 우연히 모든 데이터의 해시값이 000...으로 시작한다고 해봅시다. (데이터 쏠림 현상)
• 문제: 000... 버킷은 계속 꽉 차서 쪼개지려고 할 겁니다. 그런데 이 버킷 하나를 쪼개기 위해서 전체 주소록을 2배로 늘려야 합니다.
• 비극: 다른 버킷들은 텅텅 비어 있는데, 오직 저 버킷 하나 때문에 주소록만 2, 4, 8, 16... 계속 커집니다. 주소록은 거대한데 실제 데이터 저장소(버킷)는 효율적으로 쓰이지 않는 공간 낭비가 발생합니다.

 

 

 

 

 

 

 

 

 

 

 

• 확장 가능 해싱은 버킷이 **기하급수적(2, 4, 8, 16...)**으로 늘어납니다.
• 선형 해싱은 버킷이 하나씩(2, 3, 4, 5...) 늘어납니다. 그래서 선(Line)처럼 차근차근 늘어난다고 해서 선형 해싱입니다.

 

 

오버플로우는 일단 버티기: 내 방이 꽉 찼어도 내 차례가 아니면 옆에 임시 방(Overflow Chain)을 달아두고 기다립니다. 전체 마을이 붐비면 그때서야 순서대로 방을 넓혀줍니다.

 

 

 

 

 

 

재해싱(이사)은 쪼개진 방에 있는 애들만 하나요?"

• 확장 가능 해싱은 주소록 전체를 건드려야 할 수도 있지만,
• 선형 해싱은 "방금 쪼개진 그 방( p )"에 들어있던 데이터들만 다시 검사해서 "너 그대로 있을래, 아니면 새로 생긴 방(n−1)으로 이사 갈래?"라고 물어봅니다.

 

 

 

 

 

현재 방은 00, 01, 10 뿐인데, **0111**의 끝자리는 **11**이라서 갈 곳이 없어 보이ㅁ

방이 없으면? 내 주소의 가장 앞 비트(현 단계에서 추가된 비트)를 0으로 슥 바꿔서 나오는 방으로 갑니다. 그

 

 

 

비트 수가 증가할 때가 한 라운드의 범위인가ㅇㅇㅇ

한 라운드(Level)가 끝나면p포인터는 다시 0으로 리셋된

 

집 전체가 '레벨 2(비트 2개)'로 업그레이드되려면, 집에 있는 모든 방(0번, 1번)이 다 한 번씩 쪼개져야 해요.

젤처음엔 2개 모두 p가 이동하면 다시 처음으로 그다음은 4개를 모두 p가 이동하면 처음으로 8개..이렇게 되나ㅇㅇㅇ

 

 

 

(0번 쪼개기 완료)    p는 다음 방(1번)으로 이동!
[방 00] : A (0110"00")      ────→  p=1
[방 1 ] : B, C [D] (..1) 
[방 10] : (빈 방) (1111"10")