[HashTable] JAVA로 간단히 구현해보며 HashTable을 알아보자!

개요

• HashTable 은 Key - Value 로 이루어진 자료구조다.
• HashTable.get(Object key)를 쓰면 해당 key와 맞는 value를 반환한다.
• 이름에서 알 수 있듯이 HashCode를 이용한다.
• Key를 HashFunction를 통해 정수 Hash를 만들어내고, 그 Hash를 이용해 데이터에 접근하기 때문에 속도가 매우 빠르다.( O(1) )
  • 정수 Hash를 통해 데이터에 접근해서 속도가 빠르다는데.. 그렇다면 동일한 Hash를 반환해서 동일 인덱스에 데이터가 중복될 수 있다. 이를 Hash Colliision(해시 충돌)이라 부른다. 최악의 경우 데이터 검색에 O(n) 이 걸린다. 때문에 Hash를 만들어내는 HashFunction에 쓰이는 Hash Algorithm을 잘 만들어야 한다. 입력받은 Key를 Hash로 만들 때, 최대한 잘 분배해야한다

HashTable과 HashMap의 차이는 ?
HashTable은 Thread Safe 하다.
HashMap은 Thread Unsafe 하다.
동작방식은 비슷하다.

Hash Collision이 발생한다면?

• 해당 인덱스의 배열 저장 위치에다 바로 데이터를 집어넣는 게 아니라, LinkedList를 이용해서 차곡차곡 쌓는 방법을 쓸 수 있다.
• 인덱스 중 비어있는 인덱스를 할당한다.

구현

key와 value를 가지고 있는 Node이너클래스 작성.

private static class Node {
    private String key;
    private String value;

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

MyHashTable을 만들고, 위에서 작성한 Node를 제네릭파라미터로 갖는 멤버 LinkedList배열 선언.

public class MyHashTable {
    LinkedList<Node>[] data;

    public MyHashTable(int size) {
        this.data = new LinkedList[size];
    }
}

HashCode를 생성해내는 getHashCode(String key) 메서드 작성

private int getHashCode(String key) {
    int hashcode = 0;
    for(char c : key.toCharArray()) {
        hashcode += c;
    }
    return hashcode;
}

• 간단한 해쉬 알고리즘이다. key 문자열의 각각 문자를 아스키코드로 만들어 모두 더한다.
• 맘에 들지 않는다면 Objects.hashcode(Object o) 를 쓰자

hashcode를 위에 작성한 LinkedList배열의 인덱스로 변환하는 메서드 작성

private int convertToIndex(int hashcode) {
    return hashcode % data.length;
}

• 역시 간단한 로직이다. hashcode를 위에서 선언한 LinkedList 배열의 길이로 나머지 연산한 결과다.

입력받은 key로 LinkedList에서 Node를 찾는 searchKey 메서드 작성

private Node searchKey(LinkedList<Node> list, String key) {
    if(list == null) return null;
    for (Node node : list) {
        if (node.key.equals(key)) {
            return node;
        }
    }
    return null;
}

데이터를 집어넣는 public api인 put 메서드 작성

public 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 = searchKey(list, key);
    if (node == null) {
        list.addLast(new Node(key, value));
    }else {
        node.value = value;
    }
}

1. key를 hashcode로 변환한다.
2. (1)에서 변환한 hashcode를 index로 변환한다.
3. 위에서 선언한 LinkedList 배열에서 index로 LinkedList를 찾는다.
   • 만약 null 이라면 새로운 LinkedList를 만들고 해당index의 배열에 할당한다.
4. searchKey 메서드로 (3)에서 찾은 LinkedList와 key를 파라미터로 넘겨주면 Node가 나온다.
   • Node가 null 이라면 key에 해당하는 value가 없다는 뜻이므로 LinkedList의 마지막 위치에 Node를 만들어 저장한다.
   • null이 아니라면 기존에 있는 value를 바꿔치기한다.

데이터를 꺼내오는 public api인 get 메서드 작성

public String get(String key) {
    int hashCode = getHashCode(key);
    int index = convertToIndex(hashCode);
    LinkedList<Node> list = data[index];
    Node node = searchKey(list, key);
    return node == null ? null : node.value;
}

1. key를 hashcode로 변환한다.
2. (1)에서 변환한 hashcode를 index로 변환한다.
3. searchKey 메서드로 해당 key를 갖고있는 Node를 찾는다.
4. Node가 null 이라면 key에 해당하는 값이 없다는 뜻이므로 null을 반환하고, null이 아니라면 key에 해당하는 값이 있다는 뜻이므로 value를 return 한다.

전체 코드

/**
 * @author : Eunmo Hong
 * @since : 2020/06/27
 */

public class MyHashTable {

    LinkedList<Node>[] data;

    public MyHashTable(int size) {
        this.data = new LinkedList[size];
    }

    public 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 = searchKey(list, key);
        if (node == null) {
            list.addLast(new Node(key, value));
        }else {
            node.value = value;
        }
    }

    public String get(String key) {
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        LinkedList<Node> list = data[index];
        Node node = searchKey(list, key);
        return node == null ? null : node.value;
    }

    private int getHashCode(String key) {
        int hashcode = 0;
        for (char c : key.toCharArray()) {
            hashcode += c;
        }
        return hashcode;
    }

    private int convertToIndex(int hashCode) {
        return hashCode % data.length;
    }

    private Node searchKey(LinkedList<Node> list, String key) {
        if(list == null) return null;
        for (Node node : list) {
            if (node.key.equals(key)) {
                return node;
            }
        }
        return null;
    }



    private static class Node {
        private String key;
        private String value;

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

실행

/**
 * @author : Eunmo Hong
 * @since : 2020/06/27
 */

public class HashSample {
    public static void main(String[] args) {
        MyHashTable map = new MyHashTable(3);
        map.put("hong" , "Eunmo Hong");
        map.put("grace" , "GraceLove");
        map.put("github", "https://github.com/gracelove91");
        map.put("tistory", "https://gracelove91.tistory.com");
        map.put("email", "govlmo91@gmail.com");
    }
}

• map.put("hong" , "Eunmo Hong");
  1. 'h(104)', 'o(111)', 'n(110)', 'g(103)' 의 각각 아스키코드 값을 모두 더한다. (총합 428)
     • private int getHashCode(String key)
  2. hashCode와 위에서 선언한 LinkedList 배열의 length를 나머지 연산을 한다. (428 % 3 = 2)
     • private int convertToIndex(int hashcode)
  3. LinkedList[2]에 위치한 LinkedList를 찾아온다.

     • public void put(String key, String value) {
         ...
         LinkedList<Node> list = data[index];
         ...
       }

  4. (3)에서 찾은 LinkedList는 null이니 새로운 LinkedList를 만들어서 (3)에서 찾는 LinkedList 변수에 할당한다.

     • public void put(String key, String value) {
         ...
         if(list == null) {
          list = new LinkedList<>();
          data[index] = list;
       }
       ...
       }

  5. searchKey로 key와 (4)에서 할당한 LinkedList를 넘겨주면 Node를 반환한다.

     • public void put(String key, String value) {
       ...
         Node node = searchKey(list, key);
       ...
       }

  6. Node가 null이므로 key와 value로 새로운 Node를 만들어서 (3)에서 찾은 LinkedList의 마지막 위치에 할당해준다

     • public void put(String key, String value) {
       ...
           if (node == null) {
            list.addLast(new Node(key, value));
         }
       ...
       }