해시테이블이란? Hash Table 구현 Java

해시테이블이란?

데이터의 키값을 해시함수를 이용해 인덱스화하고 배열의 해당인덱스에 데이터를 저장하는 자료구조

해시테이블 구조

해시함수는 해당 데이터를 배열의 몇번째 인덱스에 저장할 것인지 정해주는 함수이다. 이름과 연락처를 해시테이블에 저장하고 이름의 첫 번째 글자가 알파벳의 몇 번째 문자인지로 배열의 인덱스를 정하는 해시함수를 사용해보자. 예를 들어 Ann은 첫번째(index=0), Becca는 두번째(index=1)에 저장한다.

해시테이블 충돌해결 방식 (Collision Resolution)

서로 다른 데이터도 같은 인덱스값을 가질 수 있다. 예를 들어 위의 해시테이블에 Rachel의 전화번호를 삽입해보자. Rachel과 Racine 둘다 알파벳 첫글자가 r이기 때문에 인덱스 18을 가질 것이다. 이럴 경우에 충돌이 많이 발생하면 속도가 느려진다. 아무리 좋은 해시 함수라도 해시함수에 인덱스 충돌이 아예 안생기기란 거의 불가능하다(배열을 아주 크게 만들면 충돌이 거의 발생하지 않지만 당연히 메모리 낭비가 심하다 관심이 있다면 Birthday Paradox를 검색해봐라). 가장 많이 알려진 해결법 두가지를 알아 보자.

Linear Probing(선형 탐사)

데이터를 삽입할 때 해당 인덱스에 이미 데이터가 존재하면 그 다음 인덱스(+n)로 이동하는 방식이다. 위의 예시에 대입해 보자. Rachel은 원래 18번째 위치에 저장되어야 하는데 그자리에 이미 데이터가 있으므로 +1을 한다. 19번째에도 데이터가 있으므로 +1을 해주어 20번째에 저장한다. 이 상태에서 Tina의 연락처를 저장한다면 데이터는 21번째에 삽입될 것이다.

Chaining(체이닝)

체이닝은 중복된 인덱스값을 갖는 데이터들을 연결(chain)하는 것이다. 각 인덱스에 링크드리스트로 연결한다.

해시테이블 장단점

장점

데이터를 검색할 때 고유의 인덱스값으로 접근하기때문에 검색속도가 매우 빠르다.

단점

테이블내의 여유공간이 많아야 성능이 유지되기 때문에 저장공간을 상대적으로 많이 사용한다.

해시테이블 구현

아래 코드는 체이닝 해시테이블로 위의 예시를 구현한 것이다. 먼저 이름(key)과 연락처(value)를 가진 연락처(Contact) 클래스로 링크드리스트를 만든다.

public class Contact {
    private String key;        //name
    private String value;     //phone number
    public Contact(String key, String value) {
        this.key = key;
        this.value = value;
    }
    public String getKey() {
        return key;
    }
    public void setKey(String key) {
        this.key = key;
    }
    public String getValue() {
        return value;
    }
    public void setValue(String value) {
        this.value = value;
    }
}

이름의 첫 문자의 알파벳 순서대로 인덱스를 지정하고 같은 알파벳 때문에 충돌이 생기면 링크드리스트의 맨 뒤에 삽입한다. 연락처 검색시에는 키값을 이용해 해당인덱스의 링크드리스트를 순서대로 탐색한다.

import java.util.LinkedList;
 
public class ChainingHashTable {
    
    public LinkedList<Contact>[] data;
    
    public ChainingHashTable(int size) {
        data = new LinkedList[size];
    }
 
    int getHashCode(String key) {
        int hashCode = key.charAt(0)-'a';
        return hashCode;
    }
    
    int convertToIndex(int hashCode) {
        return hashCode % 26;
    }
    
    public void put(String key, String value) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        Contact contact = new Contact(key,value);
        if(data[index] == null) {
            data[index] = new LinkedList();
        }
        data[index].addLast(contact);
    }
    
    public String get(String key) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        LinkedList<Contact> contacts = data[index];
        for(Contact c : contacts) {
            if(c.getKey().equals(key)) {
                return c.getValue();
            }
        }
        return null;
    }
}