해시 테이블(Hash Table)
다른 말로 해시 맵, 해시 표라고도 함
키-값을 대응시켜 저장하는 데이터 구조
-> 키를 통해 해당 데이터가 빠르게 접근 가능
해싱 : 키를 특정 계산 식에 넣어 나온 결과를 사용하여 값에 접근하는 과정
키: 해시 테이블 접근을 위한 입력 값해시 함수: 키를 해시 값으로 매핑하는 연산해시 값: 해시 테이블의 인덱스해시 테이블: 키-값을 연관시켜 저장하는 데이터 구조
해시 충돌
해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우
-> 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우
해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음
개방 주소법(Open Address)
충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터 저장
hash와 value가 1:1 관계 유지
비어 있는 공간 탐색 방법에 따른 분류
-> 선형 탐사법, 제곱 탐사법, 이중 해싱
-
선형 탐사법(Linear Probing): 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사
-> 일차 군집화 문제 발생 : 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생 -
제곱 탐사법(Quadratic Probing): 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사
-> 일차 군집화 문제를 일부 보완하였지만 이차 군집화 문제 발생 가능성 -
이중 해싱(Double Hashing): 해싱 함수를 이중으로 사용
-> 해시 함수 1 : 최초 해시를 구할 때 사용
-> 해시 함수 2 : 충돌 발생 시, 탐사 이동 간격을 구할때 사용
-> 선형 탐사,제곱 탐사에 비해 데이터가 골고루 분포된다는 장점
분리 연결법(Sepearte Chaining)
해시 테이블을 연결 리스트로 구성
충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결
자바에서 제공하는 해시 테이블 사용해보기
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); -> 이 경우 값이 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);
// 충돌 전
for(Map.Entry<Integer,Integer> item : ht2.entrySet()){
System.out.println(item.getKey() + " - " + item.getValue());
}
// 충돌 후
ht2.put(getHash(6), 60);
for(Map.Entry<Integer,Integer> item : ht2.entrySet()){
System.out.println(item.getKey() + " - " + item.getValue());
}
}
}해시 테이블을 배열로 구현해보기!
class MyHashTable{
Integer[] table;
int elementCnt;
MyHashTable(){};
MyHashTable(int size){
this.table = new Integer[size];
this.elementCnt = 0;
}
public int getHash(int key){
return key % table.length;
}
public void setValue(int key, int data){
int idx = this.getHash(key);
this.table[idx] = data;
this.elementCnt++;
}
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;
elementCnt--;
}
public void printHashTable(){
System.out.println("== Hash Table ==");
for(int i = 0; i < this.table.length; i++){
System.out.println(i + ": " + this.table[i]);
}
}
}해시 충돌 해결 - 개방 주소법(선형 탐사법)
class MyHashTable2 extends MyHashTable{
MyHashTable2(int size){
super(size);
}
@Override
public void setValue(int key, int data){
int idx = this.getHash(key);
if(this.elementCnt == 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){
// 앞의 getHash 함수를 참조하면 이렇게 한 이유 알수 있음
newIdx = (newIdx + 1) % this.table.length;
if(this.table[newIdx] == null){
break;
}
}
this.table[newIdx] = data;
}
elementCnt++;
}
}해시 충돌 해결 - 개방 주소법(제곱 탐사법)
class MyHashTable3 extends MyHashTable {
MyHashTable3(int size) {
super(size);
}
@Override
public void setValue(int key, int data) {
int idx = this.getHash(key);
if (this.elementCnt == 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 = (int) (newIdx + Math.pow(2,cnt++) % this.table.length);
if(this.table[newIdx] == null){
break;
}
}
this.table[newIdx] = data;
}
this.elementCnt++;
}
}해시 충돌 해결 - 개방 주소법(이중 해싱)
class MyHashTable4 extends MyHashTable{
int c; // HashTable length 보다 조금 작은 소수로 하는 것이 효율적!
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.elementCnt == this.table.length){
System.out.println("Hash table is Full!");
} 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.elementCnt++;
}
}해시 충돌 해결 - 분리 연결법
class MyHashTable5{
LinkedList[] table;
MyHashTable5(int size){
this.table = new LinkedList[size];
for (int i = 0; i < 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 < table.length ; i++) {
System.out.print(i + " : ");
this.table[i].showData();
}
}
}
public class Practice5 {
public static void main(String[] args) {
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 값으로 해당 데이터 가져오기");
// 각각의 값이 LinkedList배열에서 같은 인덱스에 들어있다 해도 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();
}
}연습문제
문제1 : 해시테이블을 이용한 수 찾기
// 입출력 예시)
// 배열1 : 1, 3, 5, 7, 9
// 배열2 : 1, 2, 3, 4, 5
// 출력 : True, False, True, False, True
public class Practice6 {
public static void solution(int[] arr1, int[] arr2){
Hashtable<Integer, Integer> ht = new Hashtable<>();
for(int i = 0; i < arr1.length; i++){
ht.put(arr1[i], arr1[i]);
}
for(int i = 0; i < arr2.length; i++){
if(ht.containsKey(arr2[i])){
System.out.println("True");
}else{
System.out.println("False");
}
}
}
public static void main(String[] args) {
int[] arr1 = {1,3,5,7,9};
int[] arr2 = {1,2,3,4,5};
solution(arr1,arr2);
}
}문제2
// 정수열 배열 nums와 target이 주어졌을 때, nums에서 임의의 두 수를 더해 target을 구할수 있는지 확인
// 두 수의 합으로 target을 구할 수 있으면 해당 값 index 반환, 없는 경우 null 반환
// 예시
// nums : 7 , 11, 5, 3 , target : 10 -> 출력 0, 3
// nums : 8, 3, -2, target: 6 -> 출력 0,2
import java.util.Arrays;
import java.util.Hashtable;
public class Practice7 {
public static int[] solution(int[] numbers, int target){
int[] result = new int[2];
Hashtable<Integer, Integer> ht = new Hashtable<>();
for(int i = 0; i < numbers.length; i++){
if(ht.containsKey(numbers[i])){
result[0] = ht.get(numbers[i]);
result[1] = i;
return result;
}
ht.put(target - numbers[i], i);
}
return null;
}
public static void main(String[] args) {
int[] nums = {7, 11, 5, 3};
System.out.println(Arrays.toString(solution(nums,10)));
nums = new int[]{8, 3, -2};
System.out.println(Arrays.toString(solution(nums, 6)));
nums = new int[]{1, 2, 3};
System.out.println(Arrays.toString(solution(nums, 12)));
}
}
참고1 : HashTable과 HashMap
public class Practice8 {
public static void main(String[] args) {
Hashtable<Integer, Integer> ht = new Hashtable<>();
ht.put(0,10);
System.out.println(ht.get(0));
HashMap<Integer, Integer> hm = new HashMap<>();
hm.put(0,10);
System.out.println(hm.get(0));
// 둘다 Map인터페이스를 구현한 클래스들
Map<Integer, Integer> map1 = ht;
Map<Integer, Integer> map2 = hm;
// 차이점
// hashTable에는 null을 키값으로 사용하면 Exception
ht.put(null, -9999);
System.out.println(ht.get(null));
// hashMap은 null을 키값으로 사용 가능
hm.put(null, -9999);
System.out.println(hm.get(null));
// HashTable과 HashMap 차이
// 공통점 : 둘다 Map 인터피스를 구현한 것
// 차이 :
// key에 null 사용 여부 -> table : X, Map : O
// thread-Safe 측면(ex: Lock) -> table : O(멀티쓰레드 환경에서 우수). Map : X(싱글 스레드 환경에서 우수)
// synchronizedMap, ConcurrentHashMap 사용시엔 Concurrent 하게 사용가능
}
}
Journey for Backend Developer