알고리즘) 동적해싱

 
 
 
 

---

 

 
 
 

 

 
 
 
익스텐시블은 앞의 비트 보고, 
리니얼은 뒤의 비트 보던가 ㅇㅇ
 
 
굳이 i,n,r얼마인지 계속 추적할 필요는 없을듯
답에서 요구한다면 마지막에 하던가 
 
 
근데 익스텐시블에서는 한번에 두배로 크기가 늘어나는 대신에, 버킷 터진 얘들만 다시 배치해줬을는데, 
리니얼에서는 다시 다 배치해주나, 
아니면, 오버플로우로 연결리스트로 된 녀석만 재배치 해주나, 
 
 
그니깐 버킷이 하나씩 늘어난다는건 알겟는데 
아 지금은 G가 들어갈 방이 없어서 이동을 못한것 뿐인건가, 
(버킷이 한칸씩 늘어나니깐, 재배치해야할 녀석이 한종류뿐인건가
 
 
 

---

 
버킷의 용량(Capacity)은 2라고 가정하고 진행합니다
(exten linear 하던가 둘다 용량이 정해져있네 
 

용량이 2라면, 
젤 앞엣게 10이어도 분리되지않음 
 
 
 
이 버킷에 들어있는 모든 데이터들은 앞에서부터 [숫자]개의 비트가 모두 똑같다
 
 
 
 
미노타우르스 : 3개를 봐야함
(10만 보면 안되고) 
 
 
 
 

1. 디렉터리 110, 111: 한 버킷을 가리킴 [Perryridge, Clearview] (로컬 뎁스 2)

 
 

 

 

 
 
 

1. 동적 해싱(Dynamic Hashing)의 도입

강의는 해싱의 마지막 시간으로 동적 해싱을 주제로 시작합니다. 기존에 배웠던 **정적 해싱(Static Hashing)**의 한계를 먼저 정리합니다.

• 기본 원리: 키를 해시 함수에 넣어 테이블의 주소를 계산하고 데이터를 저장합니다. 충돌이 발생하면 체이닝이나 선형 탐색 등으로 해결합니다.
• 문제점: 해싱의 성능은 **적재 밀도(데이터 개수를 테이블 크기로 나눈 값)**에 좌우됩니다. 테이블 크기는 고정인데 데이터가 계속 늘어나면 성능이 떨어집니다. 이를 해결하려면 전체 테이블 크기를 키우고 모든 키를 새로 배치하는 **리해시(Rehash)**를 해야 하는데, 이는 시간이 매우 오래 걸리는 작업입니다.
• 해결책: 리해시를 전체적으로 하지 않고 더 쉽게 수행할 수 있는 구조가 동적 해싱입니다. 여기에는 익스텐서블 해싱과 리니어 해싱 두 종류가 있습니다.

---

2. 동적 해싱의 공통 개념

두 방식 모두 해시 함수를 고정해 놓고, 계산된 주소값 전체를 다 주소로 쓰지 않습니다.

• 비트 수 조절: 데이터 양에 따라 주소로 사용할 비트 수를 조절합니다.
• 확장 방식: 예를 들어 처음에는 앞의 일부 비트만 보고 주소를 결정하다가, 데이터가 많아지면 비트 수를 하나씩 늘려가며 주소 범위를 확장하는 개념입니다.

---

3. 익스텐서블 해싱 (Extensible Hashing)

익스텐서블 해싱은 **'디렉터리'**라는 개념을 사용합니다.

• 구조: **디렉터리(버킷 주소 테이블)**가 실제 데이터가 담긴 버킷의 주소를 가리킵니다.
• 비트 표시: 전역 변수는 디렉터리가 현재 몇 비트를 사용하는지 나타내고, 각 버킷에 적힌 숫자는 해당 버킷의 데이터들이 앞의 몇 비트까지 일치하는지를 나타냅니다.
• 삽입과 분할:
  1. 초기 상태: 모든 데이터를 하나의 버킷에 넣습니다.
  2. 버킷 포화: 버킷이 꽉 찬 상태에서 새 데이터가 들어오면 분할이 일어납니다.
  3. 디렉터리 확장: 특정 영역에 데이터가 몰려 버킷이 계속 부족해지면, 비트 수를 늘려 디렉터리 크기를 2배(2개, 4개, 8개 등)로 확장합니다.
• 특징: 비트 수가 늘어날 때마다 디렉터리 사이즈가 2배씩 커지므로, 특정 구간에 데이터가 몰리면 디렉터리만 과도하게 커지는 부담이 있습니다.

---

4. 리니어 해싱 (Linear Hashing) -앞에는 linear probing

리니어 해싱은 디렉터리가 없으며, 버킷을 하나씩 순차적으로 추가합니다.

• 확장 기준: **적재 밀도(레코드 수를 버킷 수로 나눈 값)**를 계산하여, 미리 정한 **임계값(예: 1.7)**을 넘으면 버킷을 하나 늘립니다.
• 주소 계산: 해시 함수의 마지막 일정 비트를 주소로 씁니다. 만약 계산된 주소의 버킷이 아직 생성되지 않았다면, 앞 비트를 조정한 기존 버킷에 임시 저장합니다.
• 오버플로우 처리: 버킷이 꽉 차도 즉시 분할하지 않고, **오버플로우 버킷(연결 리스트)**을 추가로 달아줍니다. 그러다 전체 적재 밀도가 임계값을 넘기면 그때 버킷을 순서대로 추가하며 데이터를 재배치합니다.

 
 
 
 

---

6. 검색 구조의 비교

강의 중반에는 트리 기반 검색과 해시 기반 검색을 비교합니다.

• 해싱: 구현이 쉽고 성능이 매우 빠릅니다(상수 시간). 하지만 정렬 상태를 유지하지 못해 최솟값, 최댓값 찾기나 구간 검색이 불가능합니다. 단순 저장과 조회에 최적화되어 있습니다.
• 트리: 구간 검색이 가능하다는 큰 장점이 있습니다. 자바의 트리맵, 트리셋이 이 방식을 사용합니다.

---

7. 자바 컬렉션 프레임워크 (JCF)

자바에서 제공하는 효율적인 데이터 구조 라이브러리입니다.

• 핵심 인터페이스:
  • 리스트(List): 순서가 있고 중복을 허용합니다. (어레이리스트, 링크드리스트)
  • 셋(Set): 순서가 없고 중복을 허용하지 않습니다. (해시셋, 트리셋)
  • 큐(Queue): 먼저 들어온 데이터가 먼저 나가는 구조입니다.
  • 맵(Map): 키와 값의 쌍으로 저장합니다. (해시맵, 트리맵)
• 주요 클래스 특징:
  • 어레이리스트: 배열 기반으로 조회가 빠르지만, 중간 삽입과 삭제는 데이터를 밀어야 해서 느립니다.
  • 링크드리스트: 연결 구조로 삽입과 삭제는 빠르지만, 특정 데이터를 찾으려면 처음부터 찾아야 해서 조회가 느립니다.
• 큐의 메서드: 실패 시 예외를 던지는 방식(add, remove)과 특정 값을 반환하는 방식(offer, poll)으로 나뉩니다.
• 데크(Deque): 양쪽 끝에서 삽입과 삭제가 가능하며 스택으로도 활용할 수 있습니다.