HashTable 이란?
해시테이블은 데이터를 저장할 때 키(key)에 대한 해시함수를 적용하여 데이터가 저장될 인덱스를 계산하고, 이 인덱스를 활용하여 데이터에 접근하는 자료구조.
HashTable의 특징
-
빠른 검색 및 삽입 : HashTable 은 평균적으로 O(1) 의 시간 복잡도를 가지며, 매우 빠른 검색과 삽입을 제공. 이는 해시 함수를 통해 계산된 인덱스로 바로 데이터에 접근할 수 있기 때문
-
해시 함수 : key를 해시 함수에 입력하여 해당 key에 대한 해시 값을 계산. 이 해시값은 배열의 인덱스로 사용됨. 이 때 해시 함수는 key의 분포를 고려하여 골고루 분배되도록 설계 되어야 함
-
충돌 해결 : 서로 다른 key들이 같은 해시값(인덱스)을 가질 수 있는데, 이를 충돌(Collision) 이라고 함.
충돌을 해결하기 위한 방법으로는 개방 주소법(Open Addressing) 과 폐쇄 주소법(Closed Addressing) 이 있음
-개방 주소법 : 충돌 발생 시 다른 빈 버킷(공간) 을 찾아 데이터를 삽입. 선형 탐사(Linear Pribing), 이차 탐사(Quadratic Probing), 랜덤 탐사(Random Probing) 등이 있음
-폐쇄 주소법 : 충돌이 발생해도 그 자리에 연결 리스트 등을 이용해 모든 데이터를 저장. 대표적으로 체이닝(Chaining) 기법이 있음 -
효율성 : 충분한 크기의 배열을 사용하면 충돌을 최소화하고 O(1)의 시간 복잡도를 유지할 수 있음. 하지만 배열의 크기가 너무 작으면 충돌이 자주 발생하여 성능 저하가 일어날 수 있음
-
동적 크기 조정 : 필요에 따라 해시 테이블의 크기를 동적으로 조정하는 기능이 필요할 수 있음. 일반적으로 2배 크기로 확장하고 데이터를 재배치하는 방식이 사용됨
HashTable 과 HashMap의 차이점
HashTable 사용
Hashtable<Integer, Integer> ht = new Hashtable<>();
ht.put(0, 10);
System.out.println(ht.get(0));-Hashtable 을 생성하고 put 메서드를 사용해 키-값 쌍을 저장
-get 메서드를 사용해 값을 출력
HashMap 사용
HashMap<Integer, Integer> hm = new HashMap<>();
hm.put(0, 10);
System.out.println(hm.get(0));-HashMap 을 생성하고 put 메서드를 사용해 키-값 쌍을 저장
-get 메서드를 사용해 값을 출력
Map 인터페이스를 통한 Hashtable 과 HashMap 사용
Map<Integer, Integer> map1 = ht;
Map<Integer, Integer> map2 = hm;
System.out.println(map1.get(0));
System.out.println(map2.get(0));-Hashtable과 HashMap을 Map 인터페이스를 통해 사용
-동일한 메서드 get을 통해 값을 출력
null키 사용
ht.put(null, -999);
System.out.println(ht.get(null));
hm.put(null, -999);
System.out.println(hm.get(null));-Hashtable은 null 키를 허용하지 않고 에러 발생
-HashMap은 null 키를 허용하며, 이를 사용해 값을 저장하고 출력
종합
-
null키와 값의 허용 여부
-Hashtable : null 키와 값을 허용하지 않음
-HashMap : 하나의 null 키와 다수의 null 값을 허용 -
스레드 안전성(Thread-safety)
-Hashtable : 기본적으로 동기화되어 있어 스레드가 안전함. 멀티스레드 환경에서 안전하게 사용 가능
-HashMap : 동기화되지 않아서 스레드가 안전하지 않음. 싱글 스레드 환경에서 사용하는 것이 적합
멀티스레드 환경에서 사용하려면 Collections.synchronizedMap 이나 ConcurrentHashMap 을 사용해야 함 -
성능
-Hashtable : 동기화로 인해 단일 스레드 환경에서 성능이 저하될 수 있음
-HashMap : 동기화가 없어서 단일 스레드 환경에서 더 빠름 -
사용된 메서드와 생성자의 차이
-Hashtalbe : 오래된 클래스로 대부분의 메서드가 동기화 되어 있음
-HashMap : 비동기화된 메서드로 구성되어 있어 더 유연하게 사용 가능
import java.util.Hashtable;
import java.util.Map;
public class Main {
// 해시 함수
public static int getHash(int key) {
return key % 5;
}
public static void main(String[] args) {
// 기본 해시 테이블 사용 방법
Hashtable<String, Integer> ht = new Hashtable<>();
ht.put("key1", 10);
ht.put("key2", 20);
ht.put("key3", 30);
ht.put("key3", 50);
for (Map.Entry<String, Integer> item : ht.entrySet()) {
System.out.println(item.getKey() + " - " + item.getValue());
}
// 해시 충돌 케이스 (해시 함수 사용)
Hashtable<Integer, Integer> ht2 = new Hashtable<>();
ht2.put(getHash(1), 10);
ht2.put(getHash(2), 20);
ht2.put(getHash(3), 30);
ht2.put(getHash(4), 40);
ht2.put(getHash(5), 50);
System.out.println("== 충돌전 ==");
for (Map.Entry<Integer, Integer> item : ht2.entrySet()) {
System.out.println(item.getKey() + " - " + item.getValue());
}
System.out.println("== 충돌후 ==");
ht2.put(getHash(6), 60);
for (Map.Entry<Integer, Integer> item : ht2.entrySet()) {
System.out.println(item.getKey() + " - " + item.getValue());
}
}
}- 해시함수
public static int getHash(int key) {
return key % 5;
}-주어진 키에 대해 간단한 모듈로 연산을 수행하여 해시 값을 계산. 이 예에서는 키를 5로 나눈 나머지 반환
- 기본 해시 테이블 사용법
Hashtable<String, Integer> ht = new Hashtable<>();
ht.put("key1", 10);
ht.put("key2", 20);
ht.put("key3", 30);
ht.put("key3", 50);
for (Map.Entry<String, Integer> item : ht.entrySet()) {
System.out.println(item.getKey() + " - " + item.getValue());
}-Hashtable을 생성하고 키-값 쌍을 추가
-동일한 키("key 3") 에 대해 값을 갱신할 수 있음. 마지막에 추가된 값 50이 저장
-entrySet() 메서드를 사용하여 모든 키-값 쌍을 출력
- 해시 충돌 케이스
Hashtable<Integer, Integer> ht2 = new Hashtable<>();
ht2.put(getHash(1), 10);
ht2.put(getHash(2), 20);
ht2.put(getHash(3), 30);
ht2.put(getHash(4), 40);
ht2.put(getHash(5), 50);
System.out.println("== 충돌전 ==");
for (Map.Entry<Integer, Integer> item : ht2.entrySet()) {
System.out.println(item.getKey() + " - " + item.getValue());
}
System.out.println("== 충돌후 ==");
ht2.put(getHash(6), 60);
for (Map.Entry<Integer, Integer> item : ht2.entrySet()) {
System.out.println(item.getKey() + " - " + item.getValue());
}-getHash 함수를 사용하여 키의 해시값을 계산하고 해시 테이블에 추가
-키 1부터 5까지 해시 값을 계산하고 해시 테이블에 값을 추가한 후, 결과를 출력
-키 6을 추가하여 충돌을 유발하고 결과를 출력
Practice1 해시 테이블 배열로 직접 구현
class MyHashTable {
Integer[] table;
int elemCnt;
MyHashTable() {}
MyHashTable(int size) {
this.table = new Integer[size];
this.elemCnt = 0;
}
public int getHash(int key) {
return key % this.table.length;
}
public void setValue(int key, int data) {
int idx = this.getHash(key);
this.table[idx] = data;
this.elemCnt++;
}
public int getValue(int key) {
int idx = this.getHash(key);
return this.table[idx];
}
public void removeValue(int key) {
int idx = this.getHash(key);
this.table[idx] = null;
this.elemCnt--;
}
public void printHashTable() {
System.out.println("== Hash Table ==");
for (int i = 0; i < this.table.length; i++) {
System.out.println(i + ": " + this.table[i]);
}
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
MyHashTable ht = new MyHashTable(7);
ht.setValue(1, 1);
ht.setValue(2, 2);
ht.setValue(3, 3);
ht.setValue(4, 4);
ht.setValue(5, 5);
ht.printHashTable();
ht.setValue(8, 6);
ht.printHashTable();
}
}- 클래스 정의
class MyHashTable {
Integer[] table;
int elemCnt;
MyHashTable() {}
MyHashTable(int size) {
this.table = new Integer[size];
this.elemCnt = 0;
}-MyHashTable 클래스는 Integer 배열 table과 요소 개수를 추적하는 elemCnt를 멤버 변수로 가짐
-기본 생성자와 크기를 인수로 받는 생성자를 제공
- 해시 함수
public int getHash(int key) {
return key % this.table.length;
}-해시 함수는 키를 테이블의 크기로 나눈 나머지를 반환. 이를 통해 키를 테이블의 인덱스로 매핑
- 값 설정
public void setValue(int key, int data) {
int idx = this.getHash(key);
this.table[idx] = data;
this.elemCnt++;
}-주어진 키와 데이터를 사용하여 해시 테이블에 값을 설정
-키의 해시 값을 계산하여 해당 인덱스에 데이터를 저장
- 값 검색
public int getValue(int key) {
int idx = this.getHash(key);
return this.table[idx];
}-주어진 키의 해시 값을 계산하여 해당 인덱스에 저장된 값을 반환
- 값 제거
public void removeValue(int key) {
int idx = this.getHash(key);
this.table[idx] = null;
this.elemCnt--;
}-주어진 키의 해시 값을 계산하여 해당 인덱스에 저장된 값을 삭제
- 해시 테이블 출력
public void printHashTable() {
System.out.println("== Hash Table ==");
for (int i = 0; i < this.table.length; i++) {
System.out.println(i + ": " + this.table[i]);
}
}-해시 테이블의 현재 상태를 출력
Practice2 개방 주소법 (선형 탐사법)
class MyHashTable2 extends MyHashTable {
MyHashTable2(int size) {
super(size);
}
public void setValue(int key, int data) {
int idx = this.getHash(key);
if (this.elemCnt == this.table.length) {
System.out.println("Hash table is full!");
return;
} else if (this.table[idx] == null) {
this.table[idx] = data;
} else {
int newIdx = idx;
while (true) {
newIdx = (newIdx + 1) % this.table.length;
if (this.table[newIdx] == null) {
break;
}
}
this.table[newIdx] = data;
}
elemCnt++;
}
}
public class Practice2 {
public static void main(String[] args) {
// Test code
MyHashTable2 ht = new MyHashTable2(5);
ht.setValue(1, 1);
ht.setValue(3, 3);
ht.printHashTable();
ht.setValue(1, 10);
ht.printHashTable();
ht.setValue(1, 20);
ht.setValue(1, 30);
ht.setValue(1, 40);
ht.printHashTable();
}
}-MyHashTable 클래스를 상속받아 생성
-MyHashTable2 생성자는 상위 클래스의 생성자를 호출하여 해시 테이블 초기화
-seyValue 메서드를 override 하여 충돌 해결을 위해 선형 탐사를 사용 : 충돌이 발생한 경우 인덱스를 증가시키며 빈 슬롯을 찾음
-해시 테이블이 가득 찬 경우 메세지를 출력
Practice3 개방 주소법 (제곱(이차) 탐사법)
class MyHashTable3 extends MyHashTable {
MyHashTable3(int size) {
super(size);
}
public void setValue(int key, int data) {
int idx = this.getHash(key);
if (this.elemCnt == this.table.length) {
System.out.println("Hash table is full!");
return;
} else if (this.table[idx] == null) {
this.table[idx] = data;
} else {
int newIdx = idx;
int cnt = 0;
while (true) {
newIdx =(newIdx + (int)Math.pow(2, cnt)) % this.table.length;
if (this.table[newIdx] == null) {
break;
}
cnt++;
}
this.table[newIdx] = data;
}
this.elemCnt++;
}
}
public class Practice3 {
public static void main(String[] args) {
// Test code
MyHashTable3 ht = new MyHashTable3(11);
ht.setValue(1, 10);
ht.setValue(2, 20);
ht.setValue(4, 40);
ht.printHashTable();
ht.setValue(1, 100);
ht.printHashTable();
ht.setValue(1, 200);
ht.setValue(1, 300);
ht.setValue(1, 400);
ht.printHashTable();
}
}-MyHashTable 클래스를 상속받아 이차 탐사를 사용한 충돌 해결 구현
-MyHashTable3 생성자는 상위 클래스의 생성자를 호출하여 해시 테이블을 초기화
-setValue 메서드는 이차 탐사 방식을 사용하여 충돌을 해결. 충돌 발생시 인덱스를 i제곱 만큼 증가시키며 빈 슬롯을 찾음
Practice4 이차 탐사 & 이차 해싱(Quadratic Hashing) 을 사용해 충돌을 해결하는 해시테이블 구현
class MyHashTable4 extends MyHashTable {
int c;
MyHashTable4(int size) {
super(size);
this.c = this.getHashC(size);
}
public int getHashC(int size) {
int c = 0;
if (size <= 2) {
return size;
}
for (int i = size - 1; i > 2; i--) {
boolean isPrime = true;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
c = i;
break;
}
}
return c;
}
public int getHash2(int key) {
int hash = 1 + key % this.c;
return hash;
}
public void setValue(int key, int data) {
int idx = this.getHash(key);
if (this.elemCnt == this.table.length) {
System.out.println("Hast table is full!");
return;
} else if (this.table[idx] == null) {
this.table[idx] = data;
} else {
int newIdx = idx;
int cnt = 1;
while (true) {
newIdx = (newIdx + this.getHash2(newIdx) * cnt) % this.table.length;
if (this.table[newIdx] == null) {
break;
}
cnt++;
}
this.table[newIdx] = data;
}
this.elemCnt++;
}
}
public class Practice4 {
public static void main(String[] args) {
// Test code
MyHashTable4 ht = new MyHashTable4(11);
ht.setValue(1, 10);
ht.setValue(2, 20);
ht.setValue(3, 30);
ht.printHashTable();
ht.setValue(1, 100);
ht.setValue(1, 200);
ht.setValue(1, 300);
ht.printHashTable();
}
}-c 변수 : 해시 테이블에서 사용할 소수 c 값을 저장. getHashC 메서드를 통해 구함.
getHashC 메서드는 주어진 사이즈에서 가장 큰 소수 c값을 찾아 반환
-getHash2 메서드 : 이차 해시 함수를 정의. 1 + ket % c 의 값을 반환. 이는 충돌 해결에 사용됨
-setValue 메서드 : 키와 값을 받아 해시 테이블에 저장. 충돌이 발생하면 이차 해시 함수를 통해 새로운 위치를 계산하여 값을 저장
Practice5 연결 리스트를 이용한 Chaining 기법
class Node {
int key;
int data;
Node next;
Node() {}
Node(int key, int data, Node next) {
this.key = key;
this.data = data;
this.next = next;
}
}
class LinkedList {
Node head;
LinkedList() {}
LinkedList(Node node) {
this.head = node;
}
public boolean isEmpty() {
return this.head == null;
}
public void addData(int key, int data) {
if (this.head == null) {
this.head = new Node(key, data, null);
} else {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(key, data, null);
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node pre = cur;
while (cur != null) {
if (cur.key == data) {
if (cur == this.head) {
this.head = cur.next;
} else {
pre.next = cur.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public Integer findData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return null;
}
Node cur = this.head;
while (cur != null) {
if (cur.key == data) {
System.out.println("Data exist!");
return cur.data;
}
cur = cur.next;
}
System.out.println("Data not found!");
return null;
}
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty!");
return;
}
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}
class MyHashTable5 {
LinkedList[] table;
MyHashTable5(int size) {
this.table = new LinkedList[size];
for (int i = 0; i < this.table.length; i++) {
this.table[i] = new LinkedList(null);
}
}
public int getHash(int key) {
return key % this.table.length;
}
public void setValue(int key, int data) {
int idx = this.getHash(key);
this.table[idx].addData(key, data);
}
public int getValue(int key) {
int idx = this.getHash(key);
int data = this.table[idx].findData(key);
return data;
}
public void removeValue(int key) {
int idx = this.getHash(key);
this.table[idx].removeData(key);
}
public void printHashTable() {
System.out.println("== Hash Table ==");
for (int i = 0; i < this.table.length; i++) {
System.out.print(i + ": ");
this.table[i].showData();
}
}
}
public class Practice5 {
public static void main(String[] args) {
// Test code
MyHashTable5 ht = new MyHashTable5(11);
ht.setValue(1, 10);
ht.setValue(2, 20);
ht.setValue(3, 30);
ht.printHashTable();
ht.setValue(12, 11);
ht.setValue(23, 12);
ht.setValue(34, 13);
ht.setValue(13, 21);
ht.setValue(24, 22);
ht.setValue(35, 23);
ht.setValue(5, 1);
ht.setValue(16, 2);
ht.setValue(27, 3);
ht.printHashTable();
System.out.println("== key 값으로 해당 데이터 가져오기 ==");
System.out.println(ht.getValue(1));
System.out.println(ht.getValue(12));
System.out.println("== 데이터 삭제 ==");
ht.removeValue(1);
ht.removeValue(5);
ht.removeValue(16);
ht.printHashTable();
}
}- Node 클래스
class Node {
int key;
int data;
Node next;
Node() {}
Node(int key, int data, Node next) {
this.key = key;
this.data = data;
this.next = next;
}
}-Node 클래스는 키(key), 데이터(data), 다음노드를 가리키는 포인터(next) 로 구성됨
- LinkedList 클래스
class LinkedList {
Node head;
LinkedList() {}
LinkedList(Node node) {
this.head = node;
}
public boolean isEmpty() {
return this.head == null;
}
public void addData(int key, int data) {
if (this.head == null) {
this.head = new Node(key, data, null);
} else {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(key, data, null);
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node pre = cur;
while (cur != null) {
if (cur.key == data) {
if (cur == this.head) {
this.head = cur.next;
} else {
pre.next = cur.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public Integer findData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return null;
}
Node cur = this.head;
while (cur != null) {
if (cur.key == data) {
System.out.println("Data exist!");
return cur.data;
}
cur = cur.next;
}
System.out.println("Data not found!");
return null;
}
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty!");
return;
}
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}-LinkedList 클래스는 연결리스트를 구현
-addData(int key, int data) : 주어진 키와 데이터를 가진 새로운 노드를 리스트에 추가
-removeData(int key) : 주어진 키를 가진 노드를 리스트에서 삭제
-findData(int key) : 주어진 키를 가진 노드의 데이터를 반환
-showData() : 리스트의 데이터를 출력
- MyHashTable5 클래스
class MyHashTable5 {
LinkedList[] table;
MyHashTable5(int size) {
this.table = new LinkedList[size];
for (int i = 0; i < this.table.length; i++) {
this.table[i] = new LinkedList(null);
}
}
public int getHash(int key) {
return key % this.table.length;
}
public void setValue(int key, int data) {
int idx = this.getHash(key);
this.table[idx].addData(key, data);
}
public int getValue(int key) {
int idx = this.getHash(key);
int data = this.table[idx].findData(key);
return data;
}
public void removeValue(int key) {
int idx = this.getHash(key);
this.table[idx].removeData(key);
}
public void printHashTable() {
System.out.println("== Hash Table ==");
for (int i = 0; i < this.table.length; i++) {
System.out.print(i + ": ");
this.table[i].showData();
}
}
}-MyHashTable5 클래스는 해시 테이블을 구현
-table 배열은 LinkedList객체를 요소로 가지며, 각 인덱스에는 연결 리스트가 저장됨
-getHash(int key) : 주어진 키를 해시 함수를 통해 해시 테이블의 인덱스로 변환
-setValue(int key, int data) : 주어진 키와 데이터를 해시 테이블에 저장. 충돌이 발생하면 연결 리스트를 이용하여 처리
-getValue(int key) : 주어진 키에 해당하는 데이터를 반환. findData 메서드를 호출하여 데이터를 찾음
-removeValue(int key) : 주어진 키를 가진 데이터를 해시 테이블에서 삭제
-printHashTable() : 해시 테이블의 현재 상태를 출력
