기본 콘텐츠로 건너뛰기

개발 공부 - 해시 테이블 탐색법

* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - 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 -> 시작점으로 가는 것이 포인트...






댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야