* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.
해시 테이블 탐색법은 해시 테이블이라는 자료구조를 이용한 탐색 알고리즘이다.
기본적으로 배열 구조를 이용한다.
키 - 밸류 로 구성되어져 있다.
키 - 특정 값을 연결할 데이터
키를 해시 함수라는 계산식에 넣어 얻은 결과(해시 값(밸류))를 배열의 인덱스로 쓴다.
키로 계산한 배열의 인덱스와 연결된 저장소에 키와 연결될 값을 저장한다.
사실 기본적으로 제공되는 클래스 내에 해시 테이블이 있다.
(그리고 hash table 보다는 hash map을 많이 썼다!)
(이유는 table보다 충돌이 덜 난다고 하고(사실 이론상으로는 안 나야 하지만), 키 밸류에 "null" 값을 쓸 수 있어 편하다. - null을 못 쓰면 0 같은걸 써야 해서 귀찮아용.)
그런데 공부 목적이니까 교재를 따라서 열심히 구현해 본다,
어쨌든 해시 테이블은 어떤 키를 해시 함수에 넣어 얻은 결과를 배열의 인덱스로 삼아 값을 저장하는 자료구조이다.
해시 함수 의사코드는 아래와 같다.
○ 정수형 : hashFunc(정수형 : key)
．return key%10
해시 테이블의 의사 코드는 아래와 같다.
(생각보다 불편해서 다시 내 손으로... 써본다...)
오늘 철봉 설치를 했더니 떨리는 손으로 열심히 써 보았다.
이전보다는 뛰어나진 가독성!
구현하면 아래와 같다.
import java.util.Scanner;
public class 해시테이블 {
public static int[] hashtable = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
public static int hashFunc(int data){
return data % 10;
}
public static void main(String[] args) {
int data, hashValue;
Scanner scn = new Scanner(System.in);
do{
System.out.printf("\n저장할 데이터 = ");
data = scn.nextInt();
if(data < 0){
break;
}
hashValue = hashFunc(data); //해시값을 구한다
hashtable[hashValue] = data; //해시 테이블에 저장한다.
}while(true);
do{
System.out.printf("\n탐색할 데이터 = ");
data = scn.nextInt();
if(data < 0){
break;
}
hashValue = hashFunc(data); //해시값을 구한다.
if(hashtable[hashValue] == data){
System.out.println(hashValue+"번째에서 발견되었습니다.");
}else{
System.out.println("찾을 수 없습니다.");
}
}while(true);
scn.close();
}
}
저장할 데이터 = 37
저장할 데이터 = 51
저장할 데이터 = 79
저장할 데이터 = -1
탐색할 데이터 = 37
7번째에서 발견되었습니다.
탐색할 데이터 = 33
찾을 수 없습니다.
탐색할 데이터 = 51
1번째에서 발견되었습니다.
탐색할 데이터 = 70
찾을 수 없습니다.
탐색할 데이터 = 79
9번째에서 발견되었습니다.
탐색할 데이터 = -1
입력하면 이렇게 나온다.
사족 : 해시는 해시 포테이토 할 때 해시랑 같은 말이다
* 지금은 코드에 해시 key를 넣을 때 값에다가 %10을 하기 때문에 아주 중복 대잔치 코드이다! 실제로는 이렇게 짜지 말 것...
어쨌든 추적 코드를 넣으면 아래와 같다.
import java.util.Scanner;
public class 해시테이블 {
public static int[] hashtable = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
public static int hashFunc(int data){
System.out.println("해시 key는 이것이다 : " + data%10);
return data % 10;
}
public static void main(String[] args) {
int data, hashValue;
Scanner scn = new Scanner(System.in);
do{
System.out.printf("\n저장할 데이터 = ");
data = scn.nextInt();
if(data < 0){
break;
}
hashValue = hashFunc(data); //해시값을 구한다
hashtable[hashValue] = data; //해시 테이블에 저장한다.
System.out.println("삽입한 hashValue는 이것이다 " + data);
}while(true);
do{
System.out.printf("\n탐색할 데이터 = ");
data = scn.nextInt();
if(data < 0){
break;
}
hashValue = hashFunc(data); //해시값을 구한다.
if(hashtable[hashValue] == data){
System.out.println(hashValue+"번째에서 발견되었습니다.");
}else{
System.out.println("찾을 수 없습니다.");
}
}while(true);
scn.close();
}
}
저장할 데이터 = 37
해시 key는 이것이다 : 7
삽입한 hashValue는 이것이다 37
저장할 데이터 = 51
해시 key는 이것이다 : 1
삽입한 hashValue는 이것이다 51
저장할 데이터 = 79
해시 key는 이것이다 : 9
삽입한 hashValue는 이것이다 79
저장할 데이터 = -1
탐색할 데이터 = 37
해시 key는 이것이다 : 7
7번째에서 발견되었습니다.
탐색할 데이터 = 51
해시 key는 이것이다 : 1
1번째에서 발견되었습니다.
탐색할 데이터 = 79
해시 key는 이것이다 : 9
9번째에서 발견되었습니다.
탐색할 데이터 = 99
해시 key는 이것이다 : 9
찾을 수 없습니다.
탐색할 데이터 = -1
만약에 51 61 71을 넣으면 이렇게 된다.
저장할 데이터 = 51
해시 key는 이것이다 : 1
삽입한 hashValue는 이것이다 51
저장할 데이터 = 61
해시 key는 이것이다 : 1
삽입한 hashValue는 이것이다 61
저장할 데이터 = 71
해시 key는 이것이다 : 1
삽입한 hashValue는 이것이다 71
저장할 데이터 = -1
탐색할 데이터 = 51
해시 key는 이것이다 : 1
찾을 수 없습니다.
탐색할 데이터 = 61
해시 key는 이것이다 : 1
찾을 수 없습니다.
탐색할 데이터 = 71
해시 key는 이것이다 : 1
1번째에서 발견되었습니다.
탐색할 데이터 = -1
마지막에 삽입한 데이터를 찾게 된다.
저건 그냥 키가 중복되서 덮어쓰게 되는 거고... 사실 해시 충돌에 대응하기 위한 알고리즘이 필요하다.
해시 테이블 탐색법은 (이상적인) 시간 복잡도가 O(1)인데 (이상적인!) 해시 충돌(해시 값이 동일한 데이터가 생긴 상황)이 발생했을 경우에는 한번으로 찾을 수 없기 때문에 처리 방법을 생각해야한다.
1. 해시 값을 구한다
2. hashTable[해시값]이 -1이 아닌 경우(비지 않은 경우) 해시값 다음 순서의 배열 요소에 저정한다.
3. 배열의 마지막 요소를 넘는 경우에는 배열의 첫 번째 요소로 이동해 저장 위치를 탐색한다.
4. 해시값의 위치까지 돌아온 경우 "해시 테이블이 가득 찼습니다"를 표시한다.
탐색 시에도 해시 충돌을 해결해야 한다.
따라서
1. 탐색할 데이터의 해시값을 구한다
2. 해시값의 위치에 있는 데이터가 -1이 아니며,
원하는 데이터와 다른 경우 다음 순서의 배열 요소를 탐색한다.
마지막 요소까지 탐색했다면 다시 첫번쨰 요소로 돌아가 탐색한다.
3. 탐색할 데이터가 발견되면 해당 위치(배열의 인덱스)를 표시한다.
4. -1을 찾았거나, 탐색 시작 위치까지 돌아온 경우 "찾을 수 없습니다" 를 표시한다.
의사 코드는 아래와 같다.
데이터의 저장 위치를 정할 때는 해시값을 저장 위치에 해당하는 변수 pos에 저장한다.
그리고 hashTable[pos] 값이 -1이 아니면, pos값을 증가시켜서 -1 여부를 확인한다.
구현하면 아래와 같다.
import java.util.Scanner;
public class 해시테이블_충돌 {
public static int[] hashTable = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
public static int hashFunc(int data){
System.out.println("해시 key는 이것이다 : " + data%10);
return data % 10;
}
public static void main(String[] args) {
int data, hashValue;
int pos;
Scanner scn = new Scanner(System.in);
do{
System.out.print("\n 저장할 데이터 : ");
data = scn.nextInt();
if(data < 0){
break;
}
hashValue = hashFunc(data);
pos = hashValue;
while(hashTable[pos] != -1){
pos++;
if(pos >= hashTable.length){
pos = 0;
}
if(pos == hashValue){
break;
}
}
if(hashTable[pos] == -1){
hashTable[pos] = data;
}else{
System.out.println("해시 테이블이 가득 찼습니다.");
}
}while(true);
do{
System.out.print("\n 검색할 데이터 = ");
data = scn.nextInt();
if(data < 0){
break;
}
hashValue = hashFunc(data);
pos = hashValue;
while(hashTable[pos] != -1 && hashTable[pos] != data){
pos++;
if(pos >= hashTable.length){
pos = 0;
}
if(hashTable[pos] == -1 || pos == hashValue){
break;
}
}
if(hashTable[pos] == data){
System.out.println(pos+ "번째에서 발견되었습니다.");
}else{
System.out.println("찾을 수 없습니다.");
}
}while(true);
scn.close();
}
}
저장할 데이터 : 37
해시 key는 이것이다 : 7
저장할 데이터 : 51
해시 key는 이것이다 : 1
저장할 데이터 : 79
해시 key는 이것이다 : 9
저장할 데이터 : 28
해시 key는 이것이다 : 8
저장할 데이터 : 48
해시 key는 이것이다 : 8
저장할 데이터 : -1
검색할 데이터 = 37
해시 key는 이것이다 : 7
7번째에서 발견되었습니다.
검색할 데이터 = 51
해시 key는 이것이다 : 1
1번째에서 발견되었습니다.
검색할 데이터 = 79
해시 key는 이것이다 : 9
9번째에서 발견되었습니다.
검색할 데이터 = 28
해시 key는 이것이다 : 8
8번째에서 발견되었습니다.
검색할 데이터 = 48
해시 key는 이것이다 : 8
0번째에서 발견되었습니다.
검색할 데이터 = 99
해시 key는 이것이다 : 9
찾을 수 없습니다.
검색할 데이터 = 100
해시 key는 이것이다 : 0
찾을 수 없습니다.
검색할 데이터 = -1
추적코드를 넣으면 위와 같다.
시작점 -> 끝 -> 0 -> 시작점으로 가는 것이 포인트...
댓글
댓글 쓰기