해시 테이블 Java 구현

ㅇ해시테이블

- 키 값이 특정한 함수로 도출된 해쉬코드를 인덱스로 사용하는 테이블

- 해쉬코드로 인덱스에 바로 접근하니 속도가 빠르다 - O(1)

 

ㅇ충돌

- 서로 다른 키값으로 동일한 해쉬코드가 만들어지는 경우

 

*충돌 해결방법

- 체이닝, 개방주소법, 선형탐색 등등이 있지만 체이닝을 사용하여 구현해보겠습니다

 

- Node 클래스

public class Node {
    String key;
    String value;
    
    public Node(String key, String value) {
        this.key = key;
        this.value = value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public String getValue() {
        return value;
    }
}

 

- HashTable 클래스

import java.util.LinkedList;

public class HashTable {
    // 체이닝을 사용하여 충돌을 해결하기위해 연결리스트 사용
    LinkedList<Node>[] data;

    // 생성자 - 해시테이블 크기
    public HashTable(int size) {
        data = new LinkedList[size];
    }

    // 글자 글자마다 아스키코드로 변환 후 다 더하기
    // ex) ABC = 45 + 46 + 47 = 138
    int getHashCode(String key) {
        int hashCode = 0;
        for (char c : key.toCharArray()) {
            hashCode += c;
        }
        return hashCode;
    }

    // 해쉬코드를 테이블 크기로 나눈것을 인덱스로
    public int convertToIndex(int hashCode) {
        return hashCode % data.length;
    }

    // 인덱스와 키로 노드 찾기
    Node searchNode(LinkedList<Node> list, String key) {
        if (list == null) {
            return null;
        }

        for (Node n: list) {
            if (n.key.equals(key)) {
                return n;
            }
        } return null;
    }

    // 키, 값 넣는 메소드
    void put(String key, String value) {
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);

        LinkedList<Node> list = data[index];
        if (list == null) {
            list = new LinkedList<Node>();
            data[index] = list;
        }

        Node node = searchNode(list, key);
        if (node == null) {
            list.addLast(new Node(key, value));
        }
    }

    // 키에 매핑되는 값 찾기
    String get(String key) {
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);

        Node node = searchNode(data[index], key);
        return node == null ? "Not Found" : node.value;
    }
}

 

- Main 클래스

public class Main {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(5);

        hashTable.put("Mangchi", "This is Mangchi");
        hashTable.put("Hammer", "This is Hammer");
        hashTable.put("IE", "This is IE");

        System.out.println(hashTable.get("Mangchi"));
        System.out.println(hashTable.get("Hammer"));
        System.out.println(hashTable.get("IE"));
        System.out.println(hashTable.get("BAB"));
    }
}

 

결과창

 

ㅇ정보

- Map을 구현해서 만든게 HashTable이다. 자바에 Hashtable로 가보면 아래와 같이 볼 수 있다.

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

 

 

*출처

- 엔지니어 대한민국 (유투버)

- 코딩인터뷰 완전분석 (책)