참고
Hash Table
NOTE
해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 key-value 데이터를 저장하는 자료구조!
% 연산을 사용한 해시함수로 Hash Table 구성
•
검색 / 삽입 / 삭제 작업에서 평균 O(1)의 시간복잡도를 가진다.
•
Key는 고유해야 하며, 중복된 Key가 있다면, value값을 대체한다.
•
저장 순서를 보장하지 않는다.
Hashing
NOTE
임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업!
dog라는 문자가 해시함수를 통해 일정길이의 값으로 변한다.
•
Hash Table에서 해시 함수는 Key값을 입력받아 Hash Table 상의 주소 값을 반환한다.
•
입력 키를 해시 테이블 전체에 분산시켜 저장할 수 있는 함수가 좋은 해시 함수이다. (균든성)
•
일반적으로 Hash Table의 크기는 2의 멱수에 가깝지 않은 소수를 선택하면 균든성이 높아진다.
Hash Table 사용사례
NOTE
•
데이터에 빠른 검색/삽입/삭제 작업 수행이 필요한 경우
•
키-값 쌍의 데이터를 관리해야 되는 경우
•
중복 데이터 검사 : 키의 유일성을 보장하기 때문에 중복검사가 가능하다.
•
캐싱(Caching) : 캐싱용 서버(Redis)에 key-value 쌍을 저장 할 떄, 내부적으로 해시 테이블 사용
Hash Table 장단점
NOTE
장점
•
빠른 데이터 접근 속도
◦
O(1)로 조회/삽입/삭제를 수행한다.
•
키-값 쌍 저장
◦
키를 기반으로 데이터를 저장하고 검색하는 구조
◦
데이터의 연관 관계를 보다 명확하고 쉽게 관리할 수 있다.
•
중복 방지
◦
키의 유일성을 통해 데이터의 중복을 막는다.
단점
•
2개 이상의 키가 동일한 해시 값을 가질 경우 충돌이 발생한다.
•
충돌을 관리하는 많은 방법이 있지만, 빈번하게 발생하는 경우 성능 저하가 발생한다.
Hash Table 충돌처리 (Hash Collision)
NOTE
해시 테이블 내에 변환된 색인에 이미 값이 있는경우에 삽입을 시도하는 경우를 말한다!
서장훈은 0 index를 가지는데 이미 값이 있다.
해결 방법 - Separate Chaning
NOTE
충돌이 일어나는 Entry를 연결 리스트로 연결해서 저장하는 기법!
각 idx에 연결리스트가 할당된다.
•
Chaning을 통해 구현하는 경우, 추가는 O(1)이지만, 탐색/삭제의 경우 O(n)이 걸린다.
해결 방법 - Open Addressing
NOTE
충돌이 일어나는 Entry를 다른 주소에 저장하는 기법!
John Smith와 Sandra Dee는 동일한 152 idx를 가지고 있고, Sandra Dee가 1칸뒤에 저장되었다.
•
삽입
◦
계산한 해시 값에 대한 인덱스가 이미 차 있는 경우, 다음 인덱스로 이동하면서 비어있는곳에 저장한다.
◦
이렇게 비어 있는 자리를 탐색하는 것을 탐사(Probing)라고 한다.
•
탐색
◦
계산한 해시 값에 대한 인덱스부터 검사하며 탐사를 해나간다.
◦
이 때 “삭제” 표시가 있는 부분은 지나간다.
•
삭제
◦
탐색을 통해 해당 값을 찾고 삭제한 뒤 “삭제” 표시를 한다.
•
이러한 Open Addressiong의 충돌 처리방식은 3가지가 존재한다!
◦
선형탐사
◦
제곱탐사
◦
이중해싱
선형탐사(Linear Probing)
NOTE
충돌이 발생한 메모리 다음 위치에 데이터를 저장/검색 한다!
0 idx에 해싱충돌이 발생하면 1,2,3.. 다음 비어있는 주소로 저장한다.
•
데이터가 밀집되는 클러스터링 문제가 발생하며, 이로인해 탐색과 삭제가 느려진다.
제곱탐사(Quadratic Probing)
NOTE
말 그대로 1^2, 2^2, 3^2 .. 으로 탐사를 하는 방식으로 선형탐사에 비해 폭 넓게 탐사하기 때문에 효율적일 수 있다!
순차적으로 비어있는 값을 찾는게 아닌, 기존 위치의 제곱번째 위치에 데이터를 저장! (클러스터링을 줄이기 위함)
이중 해싱 (Double Hashing)
NOTE
클러스터링을 2개의 해시 함수를 사용해서 해결하는 방법!
1 idx에 데이터가 겹친다 ⇒ 추가 해시 함수를 사용해서 idx를 분리한다.
•
기존 해시 함수: h(key)
•
추가 해시 함수: J(key)
•
해시 충돌 발생시 함수: h(key) + i*J(key) (i = 1, 2, 3...N)
Load Factor
NOTE
Load Factor ⇒ 해시 테이블의 “가득 찬 정도”를 나타낸다!
Load Factor 0.5 ⇒ 50%가 채워져있다.
•
Load Factor는 각 구현방식에 따라 끼치는 영향이 다르다.
1.
Separate Chainging
•
LoadFactor가 증가한다 ⇒ 각 버킷에 저장된 연결 리스트의 평균 길이가 증가한다!
•
검색 성능이 Load Factor에 비례해서 저하될 수 있다.
◦
따라서 임게값에 도달하면 테이블의 크기를 늘리는게 일반적이다.
•
충돌 시 처리하는데 필요한 시간이 증가할 수 있다.
2.
Open Addressing
•
Load Factor가 증가한다 ⇒ 테이블 내의 사용 가능한 빈 슬롯이 줄어든다! (충돌이 늘어남)
◦
이로 인해 성능 저하가 발생한다.
◦
검색 성능은 Load Factor가 1에 가까워질수록 급속도로 감소한다.
•
Open Addressing에서는 Load Factor가 높다 = 성능이 저하된다.
◦
일반적으로 임계값을 Separate chaining 보다 낮게 설정한다.
◦
보통 0.5정도로 설정한다.
동적 리사이징
NOTE
동적 리사이징 ⇒ 해시 테이블의 크기를 동적으로 조정하는 과정!
// 50% 초과시 크기 2배로 늘린다.
if (size >= capacity * LOAD_FACTOR) resize();
// 크기가 50%까지 도달하면, 2배로 늘린다.
private void resize() {
capacity *= 2;
Entry<K, V>[] oldTable = table;
table = new Entry[capacity];
size = 0;
for (Entry<K, V> entry : oldTable) {
if (entry != null) put(entry.key, entry.value);
}
}
Java
복사
•
초기에 할당된 배열의 크기가 고정되어 있으므로, 데이터의 양이 증가하면서 배열의 크기를 초과할 수 있다.
•
이럴 때, 해시 테이블의 크기를 증가시켜 (보통 2배) 새로은 배열에 재 해싱하여 저장하는 과정
◦
보통 Load Factor 0.75에서 진행된다.
Hash Table - Linear Probing 구현
NOTE
Linear Probing ⇒ 해쉬 테이블 충돌 해결 방식으로, 충돌이 발생한 메모리 주소 다음위치의 bucket을 저장/검색 하는 방법이다!
hash 함수로 인해 0번 지점으로 강호동-서장훈이 겹치는 경우 다음주소로 옮김
전체 구현코드
데이터 삽입
NOTE
// 데이터 삽입
public void put(K key, V value) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
// 50% 초과시 크기 2배로 늘린다.
if (size >= capacity * LOAD_FACTOR) resize();
// 핵심! (해싱 충돌시 다음 주소로 저장)
int index = getIndex(key);
while (table[index] != null && !table[index].key.equals(key)) {
index = (index + 1) % capacity;
}
// 비어있거나, key값을 찾는다면 삽입
table[index] = new Entry<>(key, value);
}
Java
복사
가장 중요한건, 해싱 충돌이 일어날때 다음 주소로 간다는 것
@Test
public void testPutAndGet() {
hashTable.put("one", 1);
hashTable.put("two", 2);
hashTable.put("three", 3);
assertEquals(1, hashTable.get("one"));
assertEquals(2, hashTable.get("two"));
assertEquals(3, hashTable.get("three"));
assertNull(hashTable.get("four"));
}
Java
복사
테스트 코드
데이터 제거
NOTE
// key값을 제거한다.
public V remove(K key) {
if (key == null) return null;
// index에 값이 있고, key가 동일하다면 값을 지운다.
int index = getIndex(key);
while (table[index] != null) {
if (table[index].key.equals(key)) {
V oldValue = table[index].value;
table[index] = null;
size--;
rehash();
return oldValue;
}
index = (index + 1) % capacity;
}
return null;
}
Java
복사
삭제하고 나서 index를 재배치하는 rehash작업이 꼭 필요하다! (Linear 해싱충돌 방식의 핵심)
@Test
public void testRemove() {
hashTable.put("one", 1);
hashTable.put("two", 2);
assertEquals(1, hashTable.remove("one"));
assertNull(hashTable.get("one"));
assertEquals(2, hashTable.get("two"));
}
Java
복사
테스트 코드
rehash()
NOTE
// 배열의 특정부분이 삭제되면, 이동시키는 함수
// 해당 함수로 인해, index가 밀린 경우 중간이 삭제되더라도 제대로 검색이됨
private void rehash() {
Entry<K, V>[] oldTable = table;
table = new Entry[capacity];
size = 0;
for (Entry<K, V> entry : oldTable) {
if (entry != null) {
put(entry.key, entry.value);
}
}
}
Java
복사
데이터 삭제이후 전체 데이터를 다시 put한다.
@Test
public void testRehashWithHashCollisions() {
int fixedHashCode = 12345;
// 동일한 해시코드를 가진 키들을 사용하여 Linear Probing을 강제로 발생시킴
for (int i = 0; i < 8; i++) {
hashTableCollision.put(new CustomKey(i, fixedHashCode), i);
}
// 중간 항목 삭제
hashTableCollision.remove(new CustomKey(4, fixedHashCode));
// 모든 항목이 여전히 올바른 위치에 있는지 확인
for (int i = 0; i < 8; i++) {
if (i == 4) {
assertNull(hashTableCollision.get(new CustomKey(i, fixedHashCode)));
} else {
assertEquals(i, hashTableCollision.get(new CustomKey(i, fixedHashCode)));
}
}
}
Java
복사
CustomKey는 hashcode가 동일하게 나오기 위한 객체이다.
특정 값을 삭제했을때, 동일한 hash가 여러개 저장되어 주소탐색이 제대로 이루어지는가를 위한 코드