배열
배열 A에서 새로운 값인 36을 추가하게 되며 삽입할 위치가 a[5]와 a[6] 사이의 이진 검색법으로 조사하고 B의 이미지처럼 a[6]이후의 모든 요소를 하나씩 뒤로 이동하게 됩니다.
요소가 이동할 때 필요한 복잡도는 O(n)이므로 비용은 작다고 할 수 없습니다. 삭제 같은 경우도 똑같은 비용이 들어갑니다.
해시법
해시법은 데이터를 효율적으로 저장하고 검색하기 위한 기법으로, 간단한 연산을 통해 데이터의 저장 위치를 결정하는 방식입니다. 일반적으로는 해시 함수를 사용하여 데이터의 키를 해시값으로 변환 후 이 해시값을 이용하여 데이터를 저장하거나 검색합니다.
위와 같이 해시값을 index로 하여 key값과 data를 저장하는 자료구조를 해시 테이블이라고 합니다. 이 해시 테이블은 해시값을 인덱스로 사용하여 데이터를 저장하는 자료구조이며 각각의 저장 공간을 버킷이라고 합니다. 해시 테이블을 사용하게 되며 데이터를 빠르게 검색할 수 있어 시간 복잡도가 O(1)이 됩니다. 하지만 해시 함수에 의해 동일한 해시값이 나올 경우, 즉 해시 충돌이 발생할 수 있습니다.
위의 표를 예시로 들면 해시 함수가 13% 일 때 key값으로 20을 준다고 가정하면 해시값이 7이 나옵니다. 하지만 33이라는 키값이 있으면 해시값이 7이 나와 동일한 해시값으로 매핑되어 해시 테이블의 같은 버킷에 저장됩니다. 이렇게 되면 같은 인덱스에 여러 데이터가 쌓이게 되어 검색 기능을 저하시킬 수 있습니다. 이 해시 충돌을 해결하기 위해서 체인법과 오픈 주소법을 이용합니다.
해시 함수 특징
일관성
동일한 입력에 대해 항상 동일한 출력을 반환합니다.
고유성
서로 다른 입력에 대해서는 가능한 한 서로 다른 출력을 반환합니다.
빠른 연산
해시 함수는 빠르게 연산되어야 합니다.
체인법
체인법은 해시 충돌이 발생했을 때 각 인덱스마다 연결 리스트를 사용하여 충돌된 데이터를 저장하는 방식입니다. 각 인덱스는 연결 리스트의 맨 처음 노드를 가리키는 포인터 역할을 합니다.
- 해시 함수를 통해 key 값의 해시 값을 계산합니다. 예를 들어 key % 13일 때, key 값이 20과 33인 경우에는 각각 해시값이 7이 됩니다.
- 이때 인덱스는 7인 위치에는 연결 리스트가 없으므로 null을 가리키게 됩니다.
- 그다음으로는 key 값이 20인 데이터를 추가하면 이 데이터는 인덱스 7에 연결 리스트의 맨 앞에 추가됩니다. 이때 인덱스 7은 첫 번째 노드를 가리키면 연결 리스트의 헤드가 됩니다.
- 그 이후에 key 값이 33인 데이터를 추가하면 동일한 해시값을 가지므로 인덱스 7에 연결 리스트의 뒤에 추가됩니다. 따라서 연결 리스는 첫 번째 데이터를 가리키는 헤드를 유지하면서 다음 데이터를 연결하여 저장하게 됩니다.
- 탐색을 할 때는 해시 함수를 사용하여 해당 key 값의 해시 값을 구한 후, 그 해시값에 해당하는 인덱스를 찾습니다. 인덱스를 찾은 후에는 해당 인덱스가 가리키는 연결 리스트를 순회하며 실제로 원하는 key 값을 가진 데이터를 찾아내면 됩니다. 이런 방식으로 체인법은 해시 충돌된 데이터를 효율적으로 저장하고 탐색할 수 있습니다.
import java.util.*;
class ListNode {
int key;
int data;
ListNode next;
public ListNode(int key, int data) {
this.key = key;
this.data = data;
this.next = null;
}
}
class HashMapJoo {
private ListNode[] buckets;
private int capacity;
public HashMapJoo(int capacity) {
this.capacity = capacity;
this.buckets = new ListNode[capacity];
}
private int hashFunction(int key) {
return key % capacity;
}
public void put(int key, int data) {
int index = hashFunction(key);
ListNode newNode = new ListNode(key, data);
if (buckets[index] == null) {
buckets[index] = newNode; // 인덱스가 가리키는 위치에 연결 리스트가 없으면 새로운 노드를 추가합니다.
} else {
ListNode current = buckets[index];
while (current.next != null) {
current = current.next;
}
current.next = newNode; // 이미 연결 리스트가 있는 경우, 마지막 노드 뒤에 새로운 노드를 추가합니다.
}
}
public int get(int key) {
int index = hashFunction(key);
ListNode current = buckets[index];
while (current != null) {
if (current.key == key) {
return current.data; // 해당 key값을 가진 데이터를 찾으면 반환합니다.
}
current = current.next;
}
return -1; // 데이터를 찾지 못한 경우 -1을 반환합니다.
}
}
public class Main {
public static void main(String[] args) {
HashMapJoo hashMap = new HashMapJoo(13);
// 데이터 추가
hashMap.put(20, 200);
hashMap.put(33, 330);
// 데이터 탐색
System.out.println("20의 데이터: " + hashMap.get(20)); // 200 출력
System.out.println("33의 데이터: " + hashMap.get(33)); // 330 출력
}
}
오픈 주소법
해시 충돌이 발생했을 때 재해싱을 통해 재해싱을 통해 다른 버킷을 사용하여 충돌을 해결하는 방법입니다. 이는 해시 테이블의 각 슬롯에 하나의 항목만 저장하도록 설계되어 있습니다. 따라서 해시 충돌이 발생하면 충돌된 항목을 해시 함수를 통해 새로운 위치에 저장합니다.
선형 탐사
충돌이 발생한 버킷의 다음 버킷을 검사하는 방식입니다. 즉 현재 위치에서 일정한 간격만큼 이동하여 비어 있는 버킷을 찾습니다. 선형적으로 이동하기 때문에 클러스터링 현상이 발생할 수 있습니다.
제곱탐사
충돌이 발생한 버킷에서 일정한 제곱수만큼 떨어진 위치에 있는 버킷을 검사하는 방식입니다. 충돌이 발생한 위치에서 제곱수를 더한 위치로 이동하여 비어 있는 버킷을 찾습니다. 이 방식은 선형 탐사와 달리 일정 패턴을 따라 이동하기 때문에 클러스터링 현상을 완화할 수 있습니다.
오픈 주소법은 체인법과 비교하면 추가적인 메모리를 사용하지 않아 공간복잡도를 줄일 수 있으며 충돌이 발생하면 추가적인 검색이 필요해 검색속도가 체인법에 비해 느릴 수 있습니다.