HashTable 구현

Linear Probing 방식의 HashTable 구현

해시 테이블은 Key-Value 형태의 데이터를 저장하고 검색하는 자료구조로, 평균 O(1)의 시간 복잡도로 작업을 수행합니다. 저는 구현한 해시테이블에서 문자열 키를 해시 함수를 통해 인덱스로 변환하여 데이터를 저장하고, 충돌을 해결하기 위해 Open addressing 방식 중 Linear Probing을 사용하였습니다.

또한 데이터를 추가할 때, 먼저 입력된 키를 해시 함수를 통해 인덱스로 변환한 후 현재 인덱스에 데이터를 저장합니다. 만약 현재 인덱스에 이미 데이터가 있다면, 충돌이 발생한 것으로 간주하고 다음 인덱스로 이동하여 빈 슬롯을 찾습니다. 이때, 다음 인덱스는 현재 인덱스에서 일정한 간격을 더한 위치로 계산됩니다. 이 과정을 반복하여 데이터를 저장합니다.

데이터를 조회할 때도 마찬가지로 입력된 키를 해시 함수를 통해 인덱스로 변환하고, 현재 인덱스에 저장된 데이터를 확인합니다. 만약 데이터의 키와 찾고자 하는 키가 일치하지 않으면 충돌이 발생한 것으로 판단하고 다음 인덱스로 이동하여 일치하는 데이터나 빈 슬롯을 찾을 때까지 반복합니다. 이렇게 Linear Probing을 활용하여 충돌을 처리하고 데이터를 효율적으로 저장하고 조회하도록 구현하였습니다.

HashTable 구현

public class HashTable {
    private Map<Integer, Pair<String, Integer>> nodes;
    private int size;

    public HashTable(int size) {
        this.nodes = new HashMap<>();
        this.size = size;
    }

    public int hash(String key) {
        int tot = 0;
        for (char word : key.toCharArray()) {
            tot += (int) word;
        }
        int index = tot % this.size;
        if (index >= this.size) {
            throw new IllegalArgumentException("Hash Table Is Full");
        }
        return index;
    }

    public void put(String key, int value) {
        int currNode = hash(key);
        if (!nodes.containsKey(currNode) || nodes.get(currNode) == null) {
            nodes.put(currNode, new Pair<>(key, value));
            return;
        }

        int i = 1;
        int nextNode = (currNode + i) % this.size;
        while (nodes.containsKey(nextNode) && nodes.get(nextNode) != null) {
            nextNode = (nextNode + i) % this.size;
            i++;
            if (i >= this.size) {
                throw new IllegalArgumentException("Hash Table Is Full");
            }
        }
        nodes.put(nextNode, new Pair<>(key, value));
    }

    public int get(String key) {
        int currNode = hash(key);
        if (nodes.containsKey(currNode) && nodes.get(currNode) != null && nodes.get(currNode).getKey().equals(key)) {
            return nodes.get(currNode).getValue();
        }

        int i = 1;
        int nextNode = (currNode + i) % this.size;
        while (nodes.containsKey(nextNode) && nodes.get(nextNode) != null) {
            if (nodes.get(nextNode).getKey().equals(key)) {
                return nodes.get(nextNode).getValue();
            }
            nextNode = (nextNode + i) % this.size;
            i++;
            if (i > this.size) {
                return -1; 
            }
        }
        return -1; 
    }
}

테스트 케이스

public static void main(String[] args) {
    HashTable table = new HashTable(10);
    table.put("데이터1", 0);
    table.put("데이터2", 1);
    table.put("데이터3", 2);
    table.put("데이터4", 3);

    System.out.println(table.get("데이터1")); 
    System.out.println(table.get("데이터2")); 
    System.out.println(table.get("데이터3")); 
    System.out.println(table.get("데이터4")); 
}

/* 출력
0
1
2
3
*/