알고리즘) 적재밀도,클러스팅,뻐꾸기,삭제

 삭제

기타 충돌 해결방법

뻐꾸기 문제 
 
 
 

---

 

---

 

 

 

 

 

 

return vals[i]; // 인덱스 같나 왜지

ㅇㅇ

 

 

 

 

 

나눠줘야함 

 

 

 

 

 

public V get(K key) {
}

 

get :value를 가져오는거구나 (node가 아니네 ) 

(2,3장 차이 )

 

1. 해싱의 기본 구조와 리니어 프로빙(Linear Probing)의 기초

강의는 해싱의 기본 구성 요소에 대한 복습으로 시작합니다. 해싱은 크게 해시 함수와, 이 함수로 만들어진 주소에서 충돌(Collision)이 발생했을 때 이를 해결하는 방법 두 가지로 구성됩니다.
충돌 해결 알고리즘에는 크게 두 가지가 언급됩니다:

1. 세퍼레이트 체이닝(Separate Chaining): 각 주소마다 연결 리스트(Linked List)를 할당하여 데이터를 매달아 관리하는 방식입니다.
2. 리니어 프로빙(Linear Probing): 데이터를 담는 심볼 테이블의 크기(M)를 데이터 개수(N)보다 조금 더 크게 잡고 빈 공간을 찾아 들어가는 방식입니다.

리니어 프로빙의 동작 예시:
어떤 값 h가 들어왔을 때 들어왔을 때 해시 주소값이 4가 나왔다고 가정해 봅시다. 4번 위치에 이미 다른 데이터가 있다면, 그다음 칸인 5번을 확인합니다. 5번도 사용 중이라면 그다음인 6번을 봅니다. 이렇게 하나씩 옆으로 밀려나다가 빈 칸을 발견하면 그곳에 데이터를 저장합니다. 데이터를 찾을 때(get)도 마찬가지로, 해시 값 4로 가서 없으면 5번, 6번 순으로 하나씩 찾아보는 과정이 필요합니다.

---

2. 리니어 프로빙의 Java 클래스 구조 (슬라이드 25~26)

강의에서는 리니어 프로빙을 구현한 클래스의 변수와 함수를 하나씩 짚어줍니다.

• 변수: m은 심볼 테이블의 크기, n은 현재 들어있는 원소의 개수입니다. 리니어 프로빙에서는 항상 m > n이어야 빈 자리가 존재합니다. 키(keys[])와 값(vals[]) 쌍을 담는 배열이 각각 m개만큼 생성됩니다.
• 생성자: 디폴트 생성자는 테이블 크기를 31로 설정합니다.
• 해시 함수 (hash): hashCode()를 이용해 정수 값을 얻고, 이를 0x7fffffff와 비트 연산하여 양수로 바꾼 뒤 테이블 크기 m으로 나눈 나머지를 주소로 사용합니다.

private int hash(K key) {
    return (key.hashCode() & 0x7fffffff) % m;
}

• Get 함수: 키를 찾기 위해 해당 해시 주소로 먼저 갑니다. 그 주소에 찾는 키가 있으면 리턴하고, 없다면 null이 아닌 동안 다음 주소로 계속 이동하며 비교를 반복합니다. 끝까지 가도 없거나 null을 만나면 해당 키가 없는 것이므로 null을 리턴합니다.
• Put 함수: 데이터를 추가하기 전, 적재율()을 검사합니다. 만약 50% 이상 차 있다면 심볼 테이블 크기를 2배로 늘립니다(resize). 그 후, 주소로 가서 키가 이미 있다면 값을 업데이트하고, 없다면 빈 공간을 찾을 때까지 다음 칸으로 이동한 뒤 키와 값을 추가하고 n을 증가시킵니다.
• put은 찾았을땐, 업데이트, 못찾으면 그 i값에 넣기 

---

3. 적재 밀도(Packing Density)와 클러스터링 문제 (슬라이드 27~29)

적재 밀도(alpha = n/m) 테이블에 데이터가 얼마나 찼는지를 의미합니다. 이 밀도가 높아질수록(예: 50% → 90%) 충돌이 더 많이 발생하는 것은 당연한 결과입니다.
클러스터링(Clustering) 현상:
리니어 프로빙의 가장 큰 문제는 데이터들이 뭉치는 '클러스터링'입니다.

• 확률의 불균형: 예를 들어 주소 4번부터 8번까지 데이터가 꽉 차 있다고 가정해 봅시다. 새로운 데이터가 들어올 때, 해시 값이 4, 5, 6, 7, 8 중 어느 것이 나오더라도 결국 모두 밀려서 9번 자리에 들어갈 확률이 매우 높아집니다.
• 반면, 빈 공간인 다른 주소에 들어갈 확률은 해시 값이 정확히 그 번호일 때뿐입니다.
• 결국 데이터들이 골고루 퍼지지 않고 패거리를 지어 덩어리가 생기며, 이 덩어리는 점점 더 빨리 커집니다. 이를 막기 위해 보통 적재 밀도를 25~30% 정도로 유지하여 심볼 테이블을 데이터 대비 3배 정도 크게 잡는 것이 일반적입니다.

---

4. 탐색 길이(Search Length)와 성능 측정 (슬라이드 30~32)

성능을 체크하기 위해 **서치 랭스(Search Length)**를 계산합니다. 이는 특정 키를 찾기 위해 몇 번 비교(조사)를 했는지를 나타냅니다.
평균 서치 랭스(Average Search Length) 계산 예시:
슬라이드 31의 데이터를 보면:

1. Adams: 해시 20, 실제 20번 저장 → 1번 만에 찾음.
2. Bates: 해시 21, 실제 21번 저장 → 1번 만에 찾음.
3. Cole: 해시 21인데 밀려서 22번 저장 → 2번 조사.
4. Dean: 해시 22인데 밀려서 23번 저장 → 2번 조사.
5. Evans: 해시 20인데 밀려서 24번 저장 → 20, 21, 22, 23, 24 총 5번 조사.

• 전체 합: 1+1+2+2+5 = 11
  평균: 11 / 5 = 2.2

이처럼 적재 밀도가 60%를 넘어가면 서치 랭스가 급격히 늘어납니다. 보통 25~30% 수준으로 관리하면 평균 서치 랭스가 1.2 내외로 유지되어 좋은 성능을 보입니다.

---

5. 리사이즈(Resize)와 리해싱(Rehashing) (슬라이드 33)

데이터가 계속 들어와서 n/m이 50%를 넘으면  테이블을 2배로 키웁니다. 반대로 데이터가 지워져서 12.5%(1/8) 이하로 줄어들면 테이블을 반으로 줄입니다.
리사이즈 과정:
새로운 크기의 심볼 테이블을 하나 새로 만들고, 기존 테이블에 있던 모든 원소를 다시 put 함수를 돌려 하나씩 집어넣어야 합니다. 이를 '리해싱'이라고 부르며 시간이 꽤 걸리는 작업입니다. (강의에서 2M+1로  크기를 잡는 이유가 소수(Prime number)로 잡아야 충돌이 적기 때문이라고 설명합니다.)

---

6. 버킷(Bucket)의 개념 (슬라이드 34~36)

• 버킷은 하나의 주소 공간에 여러 개의 데이터를 담을 수 있는 용기입니다.버킷 크기를 키우면(예: B=5), 적재 밀도가 높아져도 실제 자기 주소에 못 들어가는 데이터가 줄어듭니다. 하지만 버킷 안에서는 다시 순차 검색을 해야 하므로 무작정 키울 수는 없습니다. 보통 4~5 정도가 합리적이라고 봅니다.
• 방안 1: 100개 공간에 각각 1개씩 저장 (M=100, B=1).
  방안 2: 50개 공간에 각각 2개씩 저장 (M=50, B=2).

---

7. 삭제 연산(Deletion)과 해결 방법 (슬라이드 37~42)

리니어 프로빙에서 중간 데이터를 그냥 지워버리면 '해시 체인'이 끊깁니다. (예: 5번이 지워졌는데, 원래 5번에서 밀려나 8번에 저장된 스미스를 찾으려 할 때 5번이 비어 있으면 "데이터 없음"으로 판단하게 됨)
방법 1: 묘비 (Tombstone) (슬라이드 38~39)
지워진 자리에 "여기 데이터가 있었음"이라는 표시를 남깁니다.

• 문제점: 삭제가 반복되면 테이블 전체가 묘비로 가득 찹니다. 2)_데이터를 찾을 때 빈 공간(null)을 만나야 멈추는데, 묘비만 계속 나오면 테이블 한 바퀴를 다 돌아야 하는 서치 딜레이가 발생합니다.

방법 2: 재구성 (Reorganization) (슬라이드 40~42)
데이터를 삭제할 때마다 뒤에 있는 데이터를 앞으로 당겨주는 방식입니다.

• 강의 설명: 삭제된 위치 이후부터 null을 만날 때까지의 모든 데이터를 지웠다가 다시 put 해주는 알고리즘을 소개합니다. 다소 비효율적일 수 있으나 가장 확실하게 체인을 유지합니다. 뒤에서부터 앞으로 당기는 방식이 재구성을 빨리 끝낼 확률이 높다는 팁도 덧붙입니다.

---

8. 기타 충돌 해결 방법 (슬라이드 43~45)

1. Two-probe Hashing: 해시 함수 2개를 써서 두 주소 중 연결 리스트(체인)가 더 짧은 쪽에 저장합니다.Double Hashing (이중 해싱): 해시 함수 h(x)와 보폭을 결정하는 f(x) 두 개를 사용합니다.해시 값이 같더라도 보폭(f(x))이 다르면 다른 곳으로 흩어지게 되어 클러스터링 방지에 매우 효과적입니다.
2. 공식: (h(x) + i * f(x)) (mod m)
3. Quadratic Probing: 충돌 시 +1, +4, +9... (i의 제곱 단위)로 건너뛰어 클러스터를 빨리 탈출합니다. 하지만 해시 값이 같으면 여전히 똑같은 궤적을 밟는 문제가 있습니다.

근데 이거 할때 다음단계는 이전 단계를 포함하나, 즉, 9번 인덱스에서 시작하면, 9>10(9+1)>그다음은 9+4니깐, 10+3인가

 

 "처음 계산된 해시 주소(Home Address)"를 기준으로 제곱수를 더합니다.

 

 

 

---

9. 뻐꾸기 해싱 (Cuckoo Hashing) (슬라이드 46~49)

뻐꾸기가 다른 새의 둥지 알을 밀어내듯 동작합니다.
구조: 테이블 2개(T1, T2)와 해시 함수 2개(h1, h2)를 사용합니다.
동작: 일단 T1에 넣고, 자리가 있으면 끝. 자리가 없으면 기존 놈을 쫓아내고 내가 차지합니다. 쫓겨난 데이터는 다른 해시 함수를 써서 T2로 가서 또 누군가를 쫓아냅니다.
장점: 조회(get)할 때 h1이나 h2 주소 두 곳만 딱 보면 되므로 최악의 경우에도 탐색 시간은 O(1)입니다.
단점: 삽입 시 쫓고 쫓기는 과정이 무한 루프에 빠질 수 있습니다. 일정 횟수(MaxLoop)를 넘기면 테이블을 키우고 전체 재배치를 해야 합니다.