해쉬 테이블 (Hash Table) - 2
해쉬 테이블의 장단점
1. 장점
- 데이터의 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
- 해쉬는 키에 대한 데이터가 있는지 중복에 대한 확인이 쉽다.
2. 단점
- 일반적으로 hash function이 생성할 수 있는 주소에 대한 공간을 미리 할당하여야하므로, 저장 공간이 비교적 많이 필요하다.
- 여러 키에 해당하는 주소가 동일할 경우, 충돌을 해결하기 위한 별도의 자료구조가 필요하다.
해쉬 테이블의 용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복 확인이 쉽기 때문)
충돌(Collision)의 문제
해쉬 펑션의 기능에 따라 여러 key에 대한 주소 공간이 중복되어 충돌이 발생하는 경우가 생긴다.
public static void main(String[] args) {
/* 2. 충돌(Collision) 문제점 */
HashTable hashTable2 = new HashTable(20);
hashTable2.saveData("DeanKim", "01012345678");
hashTable2.saveData("WonyoungJang", "01033335555");
hashTable2.saveData("DayeonLee", "01044558855");
hashTable2.saveData("Drake", "01011112222");
String value2 = hashTable2.getData("DeanKim");
System.out.println(value2); // 01011112222
// 현재 구현되어있는 hash function은 key의 첫번째 알파벳을 가져다가 주소 공간을 할당하도록 되어있다.
// 따라서 가장 마지막에 입력된 key인 Drake의 value가 해당 주소 공간에 저장되어 있는 것
// > 이러한 충돌 해결을 위해서는 saveData 시 별도의 자료구조를 이용한 로직 개선이 필요하다.
}충돌의 해결 기법
1. Chaining 기법
- 개방 해슁 또는 Open Hashing 기법 중 하나이다.
- Open Hashing : 해쉬 테이블 저장 공간 외의 추가적인 저장 공간은 활용한 충돌 방지 기법
- 충돌 발생 시, linked list를 사용하여, 데이터를 추가로 연결시켜 저장시키는 기법
public static class HashTable {
public boolean saveData(String key, String value) {
Integer address = this.hashFunc(key);
if(this.hashTable[address] != null) {
Slot findSlot = this.hashTable[address];
Slot prevSlot = this.hashTable[address];
while(findSlot != null) {
if(findSlot.key == key) {
findSlot.value = value;
return true;
} else {
prevSlot = findSlot;
findSlot = findSlot.next;
}
}
prevSlot.next = new Slot(key, value);
} else {
this.hashTable[address] = new Slot(key, value);
}
return true;
}
public String getData(String key) {
Integer address = this.hashFunc(key);
if(this.hashTable[address] != null) {
Slot findSlot = this.hashTable[address];
while(findSlot != null) {
if(findSlot.key == key) {
return findSlot.value;
} else {
findSlot = findSlot.next;
}
}
return null;
} else {
return null;
}
}
}
public static void main(String[] args) {
/* 3. 충돌 해결을 위한 기법 */
// 3-1. Chaining 기법
HashTable hashTable = new HashTable(20);
hashTable.saveData("DeanKim", "01012345678");
hashTable.saveData("WonyoungJang", "01033335555");
hashTable.saveData("DayeonLee", "01044558855");
hashTable.saveData("Drake", "01011112222");
String value2 = hashTable.getData("DeanKim");
System.out.println(value2); // 01012345678
}2. Linear Probing 기법
- 폐쇄 해슁 또는 Close Hashing 기법 중 하나이다.
- Close Hashing : 해쉬 테이블 저장 공간 안에서 빈 공간을 활용한 충돌 방지 기법
- 충돌 발생 시, 해당 hash address의 다음 address부터 검색하여 처음 나오는 빈 공간에 저장하는 기법
- 저장 공간 활용도를 높일 수 있다.
public static class HashTable {
public boolean saveData(String key, String value) {
Integer address = this.hashFunc(key);
if(this.hashTable[address] != null) {
if(this.hashTable[address].key == key) {
this.hashTable[address].value = value;
return true;
} else {
Integer currAddress = address + 1;
while(this.hashTable[currAddress] != null) {
if(this.hashTable[currAddress].key == key) {
this.hashTable[currAddress].value = value;
return true;
} else {
currAddress++;
if(currAddress >= this.hashTable.length) {
return false;
}
}
}
this.hashTable[currAddress] = new Slot(key, value);
return true;
}
} else {
this.hashTable[address] = new Slot(key, value);
}
return true;
}
public String getData(String key) {
Integer address = this.hashFunc(key);
if(this.hashTable[address] != null) {
if(this.hashTable[address].key == key) {
return this.hashTable[address].value;
} else {
Integer currAddress = address + 1;
while(this.hashTable[currAddress] != null) {
if(this.hashTable[currAddress].key == key) {
return this.hashTable[currAddress].value;
} else {
currAddress++;
if(currAddress >= this.hashTable.length) {
return null;
}
}
}
return null;
}
} else {
return null;
}
}
}
public static void main(String[] args) {
/* 3. 충돌 해결을 위한 기법 */
// 3-2. Linear Probing 기법
HashTable hashTable = new HashTable(20);
hashTable.saveData("DeanKim", "01012345678");
hashTable.saveData("WonyoungJang", "01033335555");
hashTable.saveData("DayeonLee", "01044558855");
hashTable.saveData("Drake", "01011112222");
String value = hashTable.getData("DeanKim");
System.out.println(value); // 01012345678
}3. 해쉬 테이블 저장 공간 확대 및 해쉬 함수 재정의
- 저장 공간의 확대보다는 hash function 자체를 개선하여 key에 대한 주소 공간이 중복되지 않을 수 있게끔 하는 것이 좀 더 실질적인 개선 기법이다.
public Integer hashFunc(String key) {
// hashtable의 길이로 나눈 나머지를 주소로 리턴한다면,
// hashTable의 길이 - 1 만큼의 주소를 만들어낼 수 있으므로,
// 모든 hashTable의 주소의 공간을 가리킬 수 있다.
return (int) key.charAt(0) % this.hashTable.length;
}
public Integer hashFuncUp(String key) {
int address = 0;
for(int i = 0; i < key.length(); i++) {
address += (int) key.charAt(i);
}
return address % this.hashTable.length;
}기존에는 key 맨 앞글자로 hashTable 주소 공간을 리턴하도록 하는 hash function 이었지만, key 문자열의 모든 문자를 더하는 식으로 변경하는 경우 중복의 확률이 낮아질 수 있다.
HashMap (해쉬맵)
해쉬 테이블 구조를 활용하여 구현된 JAVA Collection Framework에 속한 클래스
/* 4. HashMap (해쉬맵) */
HashMap<Integer, String> map1 = new HashMap<Integer, String>();
map1.put(1, "포르쉐");
map1.put(2, "아우디");
map1.put(3, "벤츠");
System.out.println(map1.get(1));
HashMap<String, String> map2 = new HashMap<String, String>();
map2.put("DeanKim", "01012345678");
map2.put("WonyoungJang", "01033335555");
map2.put("DayeonLee", "01044558855");
System.out.println(map2.get("DeanKim"));
Opportunities are never lost. The other fellow takes those you miss.