개요

• 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));
         }
       ...
       }

스택

• 한 쪽 끝에서만 자료를 넣고, 뺄 수 있는 자료구조다.
• Push로 데이터를 집어넣고, Pop으로 데이터를 빼낸다.
  

  

• 그림 상으로는 스택의 각 인덱스에 있는 데이터를 알 수 있지만, 사실상 제일 위에 있는 데이터만 알 수 있는 자료구조다. 보통 제일 위에 있는 데이터를 top라고 한다.

스택의 구현

• 일차원 배열 하나로 구현이 가능하다.

public class Stack<T> {
    private T[] data;
    private int size;

    @SuppressWarnings("unchecked")
    public Stack(int capacity) {
        data = (T[])new Object[capacity];
        size = 0;
    }

    public Stack() {
        this(10);
    }

    public void push(T data) {
        this.data[size++] = data;
    }

    public T pop() {
        return this.data[--size];
    }

    public int getSize() {
        return size;
    }
}

• 1차원 배열 data와, stack의 크기를 알려주는 size를 선언했다.
• 사용자는 스택의 최대 크기를 지정할 수 있다. 만약 최대 크기를 정해주지 않는다면 최대크기는 default 10이다
• 앞서 말한 것처럼 push로 데이터를 저장할 수 있다.
  • 예를 들어 처음 push(10) 을 한다면 data[0]에 10이 저장된다.
  • 후위연산자로 식을 수행한 뒤 size + 1이 된다
• 앞서 말한 것처럼 pop으로 데이터를 빼낼 수 있다.
  • 예를 들어 배열에 [3,1,6] 이와 같은 값이 저장돼있다면, pop()을 수행할 시 맨 마지막 값인 6을 반환한다.
  • 현재 size는 3이기 때문에 data[3]은 null이다. 따라서 전위연산자로 식을 수행하기 전 size - 1을 한 뒤 값을 빼낸다