해쉬 테이블 (HashTable)

해쉬 테이블 (HashTable)

키 (Key) 에 데이터(Value) 를 매핑할 수 있는 데이터 구조
키 (Key) 를 통해 주소를 알 수 있으므로, 저장 및 탐색 속도가 빨라짐

 

용어

해쉬 함수 (Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

해쉬 테이블 (Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

 

 

해쉬 테이블 구현

public class Hash {
    public Slot[] hashTable;
    
    public Hash(Integer size) {
    	this.hashTable = new Slot[size];
    }
    
    public class Slot {
        String value;
        Slot(String value) {
            this.value = value;
        }
    }
    
    
    /*
    * 해시 함수
    * Key 가 문자열일 때, 앞 글자를 숫자로 변환해서, Division 기법을 사용
    * 주소 (인덱스 번호) 계산
    *     Division 기법 : 가장 간단한 해쉬 함수 중 하나로, 나머지 값을 사용하는 기법
    */
    public hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }
    
    
    /*
    * key 에 대한 value 저장
    */
    public boolean saveData(String key, Strign val) {
        Integer address = this.hashFunc(key);
        
        if(this.hashTable[address] != null) {
            this.hashTable[address].value = val
            
        } else {
            this.hashTable[address] = new Slot(val);
        }
        return true;
    }
    
    
    /*
    * key 에 대한 value 값 조회
    */
    public String getData(String key) {
        Integer address = this.hashFunc(key);
        
        if(this.hashTable[address] != null) {
            return this.hashTable[address].value;
            
        } else {
            return null;
        }
    }
}


Hash mainHash = new Hash(20);
mainHash.saveData("Kims", "11111");
mainHash.saveData("aaa", "22222");
mainHash.getData("Kims");    // 11111

 

해쉬 테이블 장단점과 사용

• 장점
  • 데이터 저장/읽기 속도가 빠름
  • 키에 대한 중복 확인이 쉬움
• 단점
  • 저장공간이 좀 더 많이 필요함
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
• 사용
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현 시

 

해시 함수는 입력값의 길이가 어떻든 고정된 길이의 값을 출력하기 때문에 입력값이 다르더라도 같은 결과값이 나오는 경우가 있음, 이것을 해시 충돌이라 함.

 

해시 충돌 (Collision)

해시 충돌이 1도 없는 해시 함수를 만드는 것은 불가능함
해시 충돌을 완화해야함

 

Chaining 기법

Open Hashing 기법 중 하나, 저장 공간 외의 공간을 활용
충돌이 일어나면, Linked List 를 사용해서 데이터를 뒤로 연결시켜 저장

 

public class Hash {
    public Slot[] hashTable;
    
    public Hash(Integer size) {
    	this.hashTable = new Slot[size];
    }
    
    public class Slot {
        String key;
        String value;
        Slot next;
        
        Slot(String key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
    
    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }
    
    
    /*
    * key 에 대한 value 저장
    */
    public boolean saveData(String key, String val) {
        Integer address = this.hashFunc(key);
        
        if(this.hashTable[address] != null) {
            // head
            Slot findSlot = this.hashTable[address];
            Slot prevSlot = this.hashTable[address];
            
            while(findSlot != null) {
                // key 와 같으면
                if(findSlot.key == key) {
                    findSlot.value = val;
                    return true;
                    
                } else {
                    prevSlot = findSlot;
                    findSlot = findSlot.next;
                }
            }
            prevSlot.next = new Slot(key, val);
            
        } else {
            this.hashTable[address] = new Slot(key, val);
        }
        return true;
    }
    
    
    /*
    * key 에 대한 value 조회
    */
    public String getData(String key) {
        Integer address = hashFunc(key);
        
        if(this.hashTable[address] != null) {
            Slot findSlot = this.hashTable[address];
            
            while(findSlot != null) {
                if(findSlot == key) {
                    return findSlot.value;
                    
                } else {
                    findSlot = findSlot.next;
                }
            }
            return null;
            
        } else {
            return null;
        }
    }
}

Hash mainHash = new Hash(20);
mainHash.saveData("aaaaa", "223355");
mainHash.saveData("bbbb", "335544");
mainHash.saveData("abcde", "445566");
mainHash.saveData("asdf", "778899");
mainHash.getData("abcde");    // 445566

 

 

Linear Probing 기법

Close Hashing 기법으로 해쉬 테이블 저장 공간 안에서 충돌 문제를 해결하는 기법
충돌이 일어나면 해당 address의 다음 address부터 맨 처음 나오는 빈공간에 저장 ➡️ 저장 공간 활용 ⬆️

 

public class Hash {
    public Slot[] hashTable;
    
    public Hash(Integer size) {
    	this.hashTable = new Slot[size];
    }
    
    public class Slot {
        String key;
        String value;
        
        Slot(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }
    
    
    /*
    * key 에 대한 value 저장
    */
    public boolean saveData(String key, String val) {
        Integer address = this.hashFunc(key);
        
        if(this.hashTable[address] != null) {
            if(this.hashTable[address].key == key) {
                this.hashTable[address].value = val;
                return true;
                
            } else {
                Integer curAddress = address + 1;
                
                while(this.hashTable[curAddress] != null) {
                    if(this.hashTable[curAddress].key == key) {
                        this.hashTable[curAddress].value = val;
                        return true;
                        
                    } else {
                        curAddress++;
                        if(curAddress >= this.hashTable.length) {
                            return false;
                        }
                    }
                }
                
                this.hashTable[curAddress] = new Slot(key, val);
                return true;
            }
            
        } else {
            this.hashTable[curAddress] = new Slot(key, val);
        }
        return true;
    }
    
    
    /*
    * key 에 대한 value 조회
    */
    public String getData(String key) {
        Integer address = hashFunc(key);
        
        if(this.hashTable[address] != null) {
            if(this.hashTable[address].key == key) {
                return this.hashTable[address].value;
                
            } else {
                Integer curAddress = address;
                
                while(this.hashTable[curAddress] != null) {
                    if(this.hashTable[curAddress].key == key) {
                        return this.hashTable[curAddress].value;
                        
                    } else {
                        curAddress++;
                        if(curAddress >= this.hashTable.length) {
                            return null;
                        }
                    }
                }
                return null;
            }
            
        } else {
            return null;
        }
    }
}


Hash mainHash = new Hash(20);
mainHash.saveData("aaaaa", "223355");
mainHash.saveData("bbbb", "335544");
mainHash.saveData("abcde", "445566");
mainHash.saveData("asdf", "778899");
mainHash.saveData("besde", "6644888");
mainHash.getData("bbbb");    // 335544

 

충돌 개선

해쉬 테이블 저장공간 확대, 해쉬 함수 재정의

String name = "Kim";
int key = 0;

for(int i = 0; i < name.length(); i++) {
    key += name.charAt(i);
}

(int)(key) % 200;    // 194

 

시간 복잡도

• 일반적인 경우 O(1)
• 최악의 경우 O(n)

검색에서 해쉬 테이블의 사용

• 배열에 데이터를 저장, 검색할 때 O(n)
• 일반적인 해쉬 테이블에서 데이터를 검색 할 때 O(1)

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스