해시법

• 검색과 데이터의 추가와 삭제도 효율적으로 수행할 수 있는 방법
• 키 값을 해시 값으로 만드는 과정을 해시 함수(hash function)라고 한다.
• 해시 값(hash value)은 데이터에 접근하기 위한 인덱스
• 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열이 해시 테이블(hash table)
• 해시 테이블의 각 요소를 버킷(bucket)이라고 한다.
• 키 값과 해시 값은 반드시 1 대 1로 대응되지 않는다. 저장할 버킷이 중복되는 현상을 충돌(collision)이라고 한다.
• 해시 함수는 가능하면 해시 값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다.
• 충돌이 발생할 경우 체인법과 오픈 주소법으로 대처할 수 있다.

체인법(chaining)

• 같은 해시 값을 같는 데이터들을 사슬(chain) 모양으로 연결 리스트에서 연결하는 방법
• 오픈 해시법(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;
    }
    
    //키 값으로 요소 검색(데이터를 반환)
    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;
    }
    
    //요소 추가
    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;
    }
    
    //요소 삭제
    public int remove(K key) {
        int hash = hashValue(key);        //해시 값
        Node<K, V> p = table[hash];        //버킷
        Node<K, V> pp = null;            //바로 앞의 선택 노드
        
        while (p != null) {
            if (p.getKey().equals(key)) {
                if (pp == null) {        //연결 리스트의 맨 앞이라면
                    table[hash] = p.next;
                } else {
                    pp.next = p.next;
                }
                return 0;
            }
            pp = p;
            p = p.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)

• 충돌이 발생했을 때 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법
• 닫힌 해시법(closed hashing)이라고도 한다.
• 재해시할 때 해시 메서드는 자유롭게 결정할 수 있다.
• 빈 버킷을 만날 때까지 재해시를 여러 번 반복하므로 선형 탐사법(linear probing)이라고도 한다.

//오픈 주소법에 의한 해시
 
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];
            this.size = size;
            for (int i = 0; i < size; i++) {
                table[i] = new Bucket<K, V>();
            }
        } 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;
    }
    
    //요소 검색(데이터 반환)
    public V search(K key) {
        Bucket<K, V> p =searchNode(key);
        if (p != null) {
            return p.getValue();
        }
        return null;
    }
    
    //요소 추가
    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;                        //해시 테이블이 가득 참
    }
    
    //요소 삭제
    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("%02 ", 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;
            }
        }
    }
}