[JAVA] 자료구조 - 해시 테이블 (Hash Table)

---

(1) 해시 테이블(Hash Table)

• 키(Key) - 값(Value)을 대응시켜 저장하는 데이터 구조: 키 값을 이용해 해당 데이터(value)에 빠르게 접근
• 해싱: Key를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근

---

(2) 해시 테이블 구조

• 키(Key): 해시 테이블 접근을 위한 입력 값
• 해시 함수(Hash Function): 키를 해시 값으로 매핑하는 연산
• 해시 값(Hash Value): 해시 테이블의 인덱스
• 해시 테이블(Hash Table): 키-값을 연산하여 저장하는 데이터 구조

해시 테이블 구조

---

(3) 해시 충돌

• 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우
• ==> 서로 다른 키의 해시 함수를 통한 해시 값이 동일할 경우
• 해시 충돌 해결 방법으로는 크게 개방 주소법 / 분리 연결법이 존재

---

(4) 해시 충돌 해결 방안 1: 개방 주소법

• 개방 주소법(Open Address)
  • 충돌 시, 테이블에서 비어있는 공간의 hash를 찾아 데이터를 저장
  • hash:Value ==> 1:1 관계
  • 비어있는 공간 탐색에 따름 분류: 선형 탐사법 / 제곱 탐사법 / 이중 해싱

---

(4-1) 선형 탐사법(Linear Probing)

• 빈 공간을 순차적으로 탐색
  • 충돌 방생 지점부터 이후 빈 공간까지 순서대로 탐사
• 일차 군집화 문제 발생
  • 반복된 충돌 발생시 해당 지점 주변에 데이터 몰리는 현상 발생

개방 주소법 - 선형 탐색법

---

(4-2) 제곱 탐색법(Quadratic Probing)

• 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법
  • 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사
• 일차 군집화 문제 해결
• 이차 군집화 문제 발생 가능성

개방 주소법 - 제곱 탐색법

---

(4-3) 이중 해싱(Double Hashing)

• 해싱 함수를 이중으로 사용
  • 해시 함수 1: 최초 해시를 구할 때 사용
  • 해시 함수 2: 충돌 발생시, 탐사 이동 간격을 구할 때 사용
• 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포

개방 주소법 - 이중 해싱

---

(5) 해시 충돌 해결 방안 2: 분리 연결법

• 분리 연결법(Seperate Chaining)
  • 해시 테이블을 연결리스트(Linked List)로 구현
  • 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용해 해당 테이블에 데이터 연결

분리 연결법

---

(6) JAVA 코드로 학습하기

---

(1) JAVA가 제공하는 java.util.Hashtable 사용하고, 직접 해시 함수 만들어서 key값 넣어보기

// 선형자료구조-해시
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("k1", 10);  
        ht.put("k2", 20);
        ht.put("k3", 30);
        //key-value를 통해 만든 것이므로 충돌을 만들어보자면
        ht.put("k3", 100);  //마지막에 들어온 데이터로 바뀌어버림

        //key값 대응되는 entry들을 뽑아줌
        //hashtable은 map을 통해 만들어졌으므로 Map.entry로 설정
        for(Map.Entry<String, Integer> item : ht.entrySet()){
            System.out.println(item.getKey() + " : " + item.getValue());
        }
        line();

        //해시 충돌 케이스(해시 함수 사용)
        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());
        }
        line();

        System.out.println("== 충돌 후 ==");
        ht2.put(getHash(6), 60);
        for(Map.Entry<Integer, Integer> item : ht2.entrySet()){
            System.out.println(item.getKey()+" : "+item.getValue());
        }
        line();
        
    }
}

---

(2) Array를 이용한 해시 함수 구현하기

//배열 이용
class MyHashTable{
    Integer[] table;  //공간 선언
    int elemCnt;  //요소의 개수를 세는 변수
    
    MyHashTable(){}  //다음 연습에서 상속받아 사용할것이기 때문에 기본 생성자 생성
   
    MyHashTable(int size){
        this.table = new Integer[size];  //원하는 배열의 사이즈만큼 생성
        this.elemCnt = 0;  //요소의 개수 초기화
    }

    // hash 함수
    public int getHash(int key){
        return key % this.table.length;  //테이블의 인덱스가 빙글빙글 돔 -> 원형
    }

    // key와 value를 입력받아 테이블에 데이터 저장
    public void setValue(int key,int data){
        int idx = this.getHash(key);  //해시 함수를 통해 키 생성
        this.table[idx] = data;  //데이터 추가
        this.elemCnt++;  //개수 증가
    }

    // key를 입력받아 데이터 찾기
    public int getValue(int key){
        int idx = this.getHash(key);  //해시함수를 통해 만들어진 키를 찾음
        return this.table[idx];  //찾은 인덱스로 데이터(value) 찾음
    }

    // key를 통해 데이터(value) 지우기
    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]);  //Key : value 형식으로
        }
        System.out.println();
    }
}

---

(3) 해시 충돌 해결 - 개방 주소법 1(선형 탐색법)

//해시 충돌 해결 - 개방 주소법(선형 탐색법)
class MyHashTable2 extends MyHashTable{

    MyHashTable2(int size){
        super(size);  // 이전 (2)의 생성자를 사용
    }

    // key와 value를 입력 받아 데이터 저장
    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 ++;
    }
}

---

(4) 해시 충돌 해결 - 개방 주소법 2(제곱 탐색법)

//해시 충돌 해결 - 개방 주소법(제곱 탐색법)
class MyHashTable3 extends MyHashTable{
    MyHashTable3(int size){
        super(size);  //MyHashTable의 생성자 이용
    }

    // key와 value를 입력 받아 데이터 저장
    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;  //2의 거듭제곱만큼씩 증가하며 원형으로 찾음
                if(this.table[newIdx] == null){  //비어있는 곳을 찾으면
                    break;
                }
                cnt++;
            }
            this.table[newIdx] = data;
        }
        this.elemCnt++;
    }
}

---

(5) 해시 충돌 해결 - 개방 주소법 3(이중 해싱)

//해시 충돌 해결-개방주소법(이중 해싱)
class MyHashTable4 extends MyHashTable{
    int c;  //해시 충돌 시 이중 해싱에 사용할 소수
    MyHashTable4(int size){
        super(size);  //MyHashTable의 생성자 사용
        this.c = this.getHashC(size); //생성 시 미리 구해둠
    }

    // c를 구하는 함수
    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;
    }
    
    //c ==> 기본 사이즈보다 작은 소수
    public int getHash2(int key){
        int hash = 1 + key % this.c;  //기본적인 이중 해싱: 1 + (key % (c))
        return hash;
    }

    // key와 value를 입력 받아 데이터 저장
    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 + this.getHash2(newIdx) * cnt) % this.table.length;  //이중 해싱을 통한 key 구하기
                if(this.table[newIdx] == null){
                    break;
                }
                cnt++;
            }
            this.table[newIdx] = data;
        }
        this.elemCnt++;
    }
}

---

(6) 해시 충돌 해결 - 분리 연결법(Linked List 참고)

//해시 충돌 해결-분리 연결법
//단방향 연결리스트 사용  --> 연결 리스트 블로그 참고
class Node{
    int key;  //key와 data 둘 다 저장
    int data;
    Node next;  //다음 노드 정보 저장

    Node(int key, int data, Node next){
        this.key = key;
        this.data = data;
        this.next = next;
    }
}

// Linked List 이용
class LinkedList{
    Node head;

    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 key){
        if(this.isEmpty()){
            System.out.println("list is empty");
            return;
        }
        Node cur = this.head;
        Node pre = cur;
        while(cur != null){
            if(cur.key == key){
                if(cur == this.head){
                    this.head = cur.next;
                }else{
                    pre.next = cur.next;
                }
                break;
            }
            pre = cur;
            cur = cur.next;
        }
    }

    public Integer fidData(int key){
        if(this.isEmpty()){
            System.out.println("list is empty");
            return null;
        }
        Node cur = this.head;
        while(cur != null){
            if(cur.key == key){
                return cur.data;
            }
            System.out.println("Not found key");
            cur = cur.next;
        }
        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 extends MyHashTable{
    LinkedList[] table;  //Linked List의 배열로 구성
    
    MyHashTable5(int size){
        this.table = new LinkedList[size];  //원하는 사이즈로 생성
        for (int i = 0; i < this.table.length; i++) {  //초기화
            this.table[i] = new LinkedList(null);
        }
    }

    // hash 함수
    public int getHash(int key){
        return key % this.table.length;  //테이블의 인덱스가 빙글빙글 돔 -> 원형
    }

    // key와 value를 입력받아 테이블에 데이터 저장
    public void setValue(int key, int data){
        int idx = this.getHash(key);  //해시 함수를 통해 키 생성
        this.table[idx].addData(key, data);  //데이터 추가
    }

    // key를 입력받아 데이터 찾기
    public int getValue(int key){
        int idx = this.getHash(key);  // 해시 함수를 통해 만들어진 키를 찾음
        int data = this.table[idx].fidData(key);  //찾은 인덱스로 데이터(value) 찾음
        return data;
    }

    // key를 통해 데이터(value) 지우기
    public void removeData(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 + ": ");  //Key : value1, value2, ... 형식으로
            this.table[i].showData();
        }
        System.out.println();
    }
}