Hash Table

Hash Table

---

해시 테이블(Hash Table) 은 키(key)와 값(value)으로 하나의 쌍으로 데이터를 저장하는 자료구조이다. 또한 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문에 자료구조 중에서 데이터를 빠르게 검색할 수 있는 구조를 가지고 있다. 

 

key를 해시 함수(hash function)로 계산하여 그 값을 배열(버킷)의 인덱스로 사용한다. 이때, 해시 함수에 의해 반환된 데이터의 고유 숫자 값을 해시값 또는 해시 코드라고 한다. 그리고 해시값을 배열의 인덱스로 사용하여 해당 인덱스 자리에 데이터를 저장한다. 아래는 hash table을 사용하여 데이터를 저장하는 일련의 과정의 예시이다.

 

1. John Smith라는 key를 hash function으로 넘긴다

2. Hash Function은 John Smith라는 Key에 대한 Hash값(Hash code)인 02를 return

3. return 받은 Hash값 02를 버킷의 인덱스로 사용하여 전화번호인 521-1234라는 data를 저장

 

hash table 구현해보기

---

public class MyHash{
    
    //hash table
    public Slot[] hashTable;
    
    //hash table의 크기를 지정해주는 생성자
    public MyHash(int size){
        this.hashTable = new Slot[size];
    }
    
    //hash table 안의 각각의 슬롯
    public class Slot{
        String value;
        
        public Slot(String value){
            this.value = value;
        }
    }
    
    //hash값을 return 해주는 hash function 메소드
    public int hashFunction(String key){
        return (int)(key.charAt(0))%this.hashTable.length;
    }
    
    //hash table에 data를 저장하는 메소드
    public boolean saveData(String key, String value){
        
        //hash값 생성
        int hashCode = this.hashFunction(key);
        
        if(this.hashTable[hashCode] == null){
            //해당 hash값에 대한 슬롯이 존재하지 않는 경우
            this.hashTable[hashCode] = new Slot(value);
            return true;
        }else{
            //해당 hash값에 대한 슬롯이 존재할 경우
            this.hashTable[hashCode].value = value;
            return true;
        }
        
    }
    
    //hash table에서 data를 가져오는 메소드
    public String getData(String key){
        
        //hash값 생성
        int hashCode = this.hashFunction(key);
                
        if(this.hashTable[hashCode] == null){
            //해당 hash값에 대한 슬롯이 존재하지 않는 경우
            return null;
        }else{
            //해당 hash값에 대한 슬롯이 존재할 경우
            return this.hashTable[hashCode].value;
        }
        
    }
    
    
}

 

Hash Collision(해쉬 충돌)

---

기본적으로 Hash Table 자료구조는 key를 통해 Hash Function에서 Hash값을 반환받기만 하면 원래 데이터 값을 바로 찾을 수 있기 때문에 Insertion, Deletion, Search 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있어 우수한 자료구조라고 할 수 있다. 하지만 이러한 자료 구조라도 단점은 존재한다. 그 단점 중 하나는 바로 충돌이라는 것이다.

 

충돌이란 무한한 값(해시 테이블에서는 KEY를 의미)을 유한한 값(해시 테이블에서는 Hash를 의미)으로 표현하면서 서로 다른 두 개 이상의 유한한 값이 동일한 출력 값을 가지게 된다는 것이다. 이러한 충돌로 인해 최악의 경우 O(n)이라는 시간 복잡도를 갖게 된다.

 

위의 그림을 예시로 보게 되면 John Smith와 Sandra Dee가 hash function에서 02라는 같은 hash값을 반환받게 되었다. 이러한 경우를 충돌이라고 한다. 이러한 충돌을 해결하는 대표적인 방법에는 개방 해슁 기법인 chaining 기법과 폐쇄 해슁 기법인 linear probing 기법이 있다.

 

 

Chaining 기법

---

Chaining이란 충돌이 발생했을 때 이를 동일한 슬롯에 저장하는데 이를 연결 리스트 형태로 저장하는 방법을 말한다. 아래의 그림을 보면 John Smith와 Sandra Dee의 인덱스가 152로 충돌하게 된 경우인데 이때 Sandra Dee를 John Smith 뒤에 연결함으로써 충돌을 처리하는 것을 볼 수 있다. 

 

 

 

 

chaining 기법으로 hash table 구현해보기

---

public class MyHash{
    
    //hash table
    public Slot[] hashTable;
    
    //hash table 길이 지정해주는 생성자
    public MyHash(int size){
        this.hashTable = new Slot[size];
    }
    
    //hash table 각각의 slot
    public class Slot{
        
        String key;
        String value;
        Slot next = null;
        
        public Slot(String key, String value){
            this.key = key;
            this.value = value;            
        }
        
    }
    
    //hash값을 return 해주는 hash function 메소드
    public int hashFunction(String key){
        return (int)(key.charAt(0))%this.hashTable.length;
    }
    
    //hash table에 data을 저정하는 메소드
    public boolean saveData(String key, String value){
        
        //hash값 생성
        int hashCode = this.hashFunction(key);
        
        if(this.hashTable[hashCode] == null){
            //해당 hash값에 대한 slot이 null일 경우
            this.hashTable[hashCode] = new Slot(key, value);
            return true;
        }else{
            //해당 hash값에 대한 slot이 null이 아니어 충돌 발생 시
            Slot slot = this.hashTable[hashCode];
            if(slot.key == key){
                //첫 slot 키와 저장하려는 key와 같을 경우 value 덮어쓰기
                this.hashTable[hashCode].value = value;
                return true;
            }
            //slot에 연결된 리스트를 돌면서 slot 키와 저장하려는 key와 같은지 검사하고 같을 시 value 덮어쓰기
            while(slot.next != null){
                slot = slot.next;
                if(slot.key == key){
                    slot.value = value;
                    return true;
                }
            }
            //slot에 연결된 리스트에 같은 key가 없을 경우 마지막 slot뒤에 새로운 data 추가
            slot.next = new Slot(key,value);
            return true;
        }
        
    }
    
    //hash table에서 해당 key에 대한 data를 찾는 메소드
    public String getData(String key){
        
        //hash값 생성
        int hashCode = this.hashFunction(key);
        
        if(this.hashTable[hashCode] == null){
            //해당 hash값에 대한 slot이 null일 경우
            return null;
        }else{
            //해당 hash값에 대한 slot이 null이 아닐 경우
            Slot slot = this.hashTable[hashCode];
            
            //첫 slot 키와 찾고자하는 key와 동일할 경우
            if(slot.key == key){
                return slot.value;
            }
            
            //찾고자하는 key와 같은 key가 있는지 검사
            while(slot.next != null){
                slot = slot.next;
                if(slot.key == key){
                    return slot.value;
                }
            }
            
            //hash table에 찾고 싶은 key가 없을 경우
            return null;
        }
    }
}

 

 

Linear probing 기법

---

충돌이 발생했을 시 그 해당 자리의 다음 자리를 시작으로 비어있는지 확인 후 가장 처음에 나오는 빈 공간에 데이터를 저장하는 기법이다. 아래의 그림을 보게 되면 John Smith와 Sandra Dee가 같은 hash값인 152로 중복이 되어 Sandra Dee는 다음 주소인 153에 저장이 되었고 153이라는 hash값을 반환받은 Ted Baker는 154에 저장이 되었다. 이렇게 충돌이 일어났을 시 다음 주소를 시작으로 빈 공간을 탐색하여 저장을 하여 해결한다.

 

 

 

 

Linear probing 기법으로 hash table 구현해보기

---

public class MyHash{
    
    //hash table
    public Slot[] hashTable;
    
    //hash table의 크기를 지정해주는 생성자
    public MyHash(int size){
        this.hashTable = new Slot[size];
    }
    
    //hash table 안의 각각의 slot
    public class Slot{
        String key;
        String value;
        
        public Slot(String key, String value){
            this.key = key;
            this.value = value;
        }
    }
    
    //hash값을 return 해주는 메소드
    public int hashFunction(String key){
        return (int)(key.charAt(0))%this.hashTable.length;
    }
    
    //hash table에 data을 저정하는 메소드
    public boolean saveData(String key, String value){
        //hash값 생성
        int hashCode = this.hashFunction(key);
        
        if(this.hashTable[hashCode] == null){
            //해당 hash값에 대한 slot이 null일 경우
            this.hashTable[hashCode] = new Slot(key, value);
            return true;
        }else{
             //해당 hash값에 대한 slot이 null이 아니어 충돌 발생 시
            int curHashCode = hashCode;
            while(this.hashTable[curHashCode] != null){
                if(this.hashTable[curHashCode].key == key){
                    //검사하는 slot의 key값과 저장하려는 key값과 동일한 경우 value 덮어쓰기
                    this.hashTable[curHashCode].value = value;
                    return true;
                }else{
                    //검사하는 slot의 key값과 저장하려는 key값과 다른 경우 다음 주소로 이동
                    curHashCode++;
                    if(curHashCode >= this.hashTable.length){
                        //hash table의 마지막 slot을 벗어날 경우 종료
                        return false;
                    }
                }
            }
            //hash table에 비어있는 slot이 있을 경우
            this.hashTable[curHashCode] = new Slot(key, value);
            return true;
        }
    }
    
    //hash table에서 해당 key에 대한 data를 찾는 메소드
    public String getData(String key){
        //hash값 생성
        int hashCode = this.hashFunction(key);
        
        if(this.hashTable[hashCode] == null){
            //해당 hash값에 대한 slot이 null일 경우
            return null;
        }else{
            //해당 hash값에 대한 slot이 null이 아닐 시
            int curHashCode = hashCode;
            while(this.hashTable[curHashCode] != null){
                if(this.hashTable[curHashCode].key == key){
                    //검사하는 slot의 key값과 저장하려는 key값과 동일한 경우
                    return this.hashTable[curHashCode].value;
                }else{
                    //검사하는 slot의 key값과 저장하려는 key값과 다른 경우 다음 주소로 이동
                    curHashCode++;
                    if(curHashCode >= this.hashTable.length){
                        //hash table의 마지막 slot을 벗어날 경우 종료
                        return null;
                    }
                }
            }
            //hash table에 찾으려는 key가 없을 경우
            return null;
        }
    }
}