11_해시

• 해시법: 검색/추가/삭제를 효율적으로 수행할 수 있는 방법
• 용어

       - 해시 함수(hash function): 키 값을 가지고 해시값을 만드는 과정

       - 해시 값(hash value): 해시함수와 키 값을 사용해서 만든 값. 해시 테이블의 인덱스. 데이터에 접근할 때 사용

       - 해시 테이블(hash table): 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열

       - 버킷(bucket): 해시 테이블의 각 요소

• 충돌(collision): 저장할 버킷이 중복되는 현상
• 해시 함수는 가능하면 해시 값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다.

① 체인법 (= chaining, 오픈 해시법, open hashing)

- 같은 해시 값을 갖는 요소를 연결리스트로 관리

- 각 버킷에 저장하는 값은 '같은 해시 값을 갖는 노드를 연결한 리스트'의 첫 번째 노드에 대한 참조!

public class ChainHash<K,V> {
    // 해시를 구성하는 노드
    class Node<K,V> {
        private K key;              // 키 값
        private V data;             // 데이터
        private Node<K,V> next;     // 다음 노드에 대한 참조

        // 생성자
        Node(K key, V data, Node<K,V> next) {
            this.key = key;
            this.data = data;
            this.next = next;
        }

        // 키 값 반환
        K getKey() {
            return key;
        }

        // 데이터 반환
        V getValue() {
            return data;
        }

        // 키의 해시 값 반환
        public int hashCode() {
            return key.hashCode();
        }
    }
    
    private int size;           // 해시 테이블의 크기
    private Node<K,V>[] table;  // 해시 테이블
    
    // 생성자
    public ChainHash(int capacity) {
        try {
            table = new Node[capacity];
            this.size = capacity;
        } catch (OutOfMemoryError e) {
            this.size = 0;
        }
    }
    
    // 해시 값을 구함
    public int hashValue(Object key) {
        return key.hashCode() % size;
    }
    
    // 키 값 key를 갖는 요소의 검색 (데이터를 반환)
    public V search(K key) {
        int hash = hashValue(key);  // 검색할 데이터의 해시 값 (→ 키 값을 변환)
        Node<K,V> p = table[hash];  // 선택 노드 (→ 버킷을 선택)
        
        while (p != null) {
            if (p.getKey().equals(key))
                return p.getValue();
            p = p.next;
        }
        return null;
    }
    
    // 키 값 key, 데이터 data를 갖는 요소의 추가
    public int add(K key, V data) {
        int hash = hashValue(key);  // 추가할 데이터의 해시 값
        Node<K,V> p = table[hash];  // 선택 버킷
        
        while (p != null) {
            if (p.getKey().equals(key))     //-- 이미 등록된 키 값이라 추가 실패     
                return 1;
            p = p.next;
        }
        // 노드를 연결리스트 맨 앞에 삽입
        Node<K,V> temp = new Node<K,V>(key, data, table[hash]);
        table[hash] = temp;
        return 0;
    }
    
    // 키 값 key를 갖는 요소의 삭제
    public int remove(K key) {
        int hash = hashValue(key);         // 삭제할 데이터의 해시 값
        Node<K,V> node = table[hash];      // 선택 버킷
        Node<K,V> nodePrev = null;         // 바로 앞의 선택 노드
        
        while (node != null) {
            if (node.getKey().equals(key)) {
                if (nodePrev == null)           // 그게 처음 노드라면,
                    table[hash] = node.next;    // 버킷이 node의 next 참조하도록
                else 
                    nodePrev.next= node.next;  
                return 0;
            }
            nodePrev = node;
            node = node.next;    
        }
        return 1;
    }
    
    // 해시 테이블을 모두 출력
    public void dump() {
        for (int i = 0; i < size; i++) {
            Node<K,V> p = table[i]; // 순서대로 버킷 선택
            System.out.printf("%02d  ", i);
            while (p != null) {
                System.out.printf("→ %s (%s)  ", p.getKey(), p.getValue());
                p = p.next;
            }
            System.out.println();
        }
    }
}

 

 

 

② 오픈 주소법 (= open addressing, 선형 탐사법, linear probing, 닫힌 해시법, closed hashing)

- 충돌이 발생했을 때 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법

public class OpenHash<K,V> {
    // 버킷의 상태
    enum Status {OCCUPIED, EMPTY, DELETED};     // {데이터저장, 비어있음, 삭제마침}

    // 버킷
    static class Bucket<K,V> {
        private K key;
        private V data;
        private Status stat;    // 상태

        // 생성자
        Bucket() {
            stat = Status.EMPTY;    // 버킷은 비어 있음
        }

        // 모든 필드에 값 설정
        void set(K key, V data, Status stat) {
            this.key = key;
            this.data = data;
            this.stat = stat;
        }

        // 상태 설정
        void setStat(Status stat) {
            this.stat = stat;
        }

        // 키 값 반환
        K getKey() {
            return key;
        }

        // 데이터 반환
        V getValue() {
            return data;
        }

        // 키의 해시 값 반환
        public int hashCode() {
            return key.hashCode();
        }
    }

    private int size;
    private Bucket<K,V>[] table;      // 해시 테이블

    public OpenHash(int size) {
        try {
            table = new Bucket[size];
            for (int i = 0; i < size; i++)
                table[i] = new Bucket<K,V>();
            this.size = size;
        } catch (OutOfMemoryError e) {
            this.size = 0;
        }
    }

    // 해시 값 구함
    public int hashValue(Object key) {
        return key.hashCode() % size;
    }

    // 재해시 값 구함
    public int rehashValue(int hash) {
        return (hash + 1) % size;
    }

    // 키 값 key를 갖는 버킷 검색
    private Bucket<K,V> searchNode(K key) {
        int hash = hashValue(key);  
        Bucket<K,V> p = table[hash];    
        
        for (int i = 0; p.stat != Status.EMPTY && i < size; i++) {
            if (p.stat == Status.OCCUPIED && p.getKey().equals(key))
                return p;
            hash = rehashValue(hash);   // 재해시
            p = table[hash];
        }
        return null;
    }
    
    // 키 값 key를 갖는 요소의 검색(데이터 반환) → 버킷당 key 한 개 들어있으니까
    public V search(K key) {
        Bucket<K,V> p = searchNode(key);
        if (p != null)
            return p.getValue();
        else 
            return null;
    }
    
    // 키 값 key, 데이터 data를 갖는 요소의 추가
    public int add(K key, V data) {
        if (search(key) != null)
            return 1;       // 이미 등록된 키 값 → 추가 실패
        
        int hash = hashValue(key);
        Bucket<K,V> p = table[hash];
        for (int i = 0; i < size; i++) {
            if (p.stat == Status.EMPTY || p.stat == Status.DELETED) {
                p.set(key, data, Status.OCCUPIED);
                return 0;
            }
            hash = rehashValue(hash);
            p = table[hash];
        }
        return 2;   // 해시테이블 가득 참
    }
    
    // 키 값 key를 갖는 요소 삭제
    public int remove(K key) {
        Bucket<K,V> p = searchNode(key);
        if (p == null)
            return 1;
        
        p.setStat(Status.DELETED);
        return 0;
    }
    
    // 해시 테이블 모두 출력
    public void dump() {
        for (int i = 0; i < size; i++) {
            System.out.printf("%02d ", i);
            switch (table[i].stat) {
                case OCCUPIED:
                    System.out.printf("%s (%s)\n"
                        , table[i].getKey(), table[i].getValue());
                    break;
                case EMPTY:
                    System.out.println("-- 미등록 --");
                    break;
                case DELETED:
                    System.out.println("-- 삭제 마침 --");
                    break;
            }
        }
    }
}