[자료구조] HashMap/HashTable

package hashmap;
 
import java.util.LinkedList;
 
class HashTable{
    class Node{
        String key;
        String value;
        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
        public String getValue() {
            return value;
        }
        public void setValue(String value) {
            this.value = value;
        }
    }
    
    LinkedList<Node>[] data;
    HashTable(int size){
        this.data = new LinkedList[size];
    }
    
    /*
     * HashCode를 만들때 String에 각 문자를 하나씩 아스키코드로 바꾼뒤에 그 값을 더해서 HashCode를 만든다.
     * ex) abc = a(97) + b(98) + (99) = 294
     * 하지만 위와같이 할 경우 bac = cab = cba 등 HashCode값이 같다.
     * 다른 방법으로는 97*2^0 + 98*2^1 + 98*2^2 와 같은 방법도 생각해 볼 수 있다.
    */
    int getHashCode(String key) {
        int hashcode = 0;
        for(char c : key.toCharArray()) {
            hashcode += c;
        }
        return hashcode;
    }
    /*
     * HashCode를 받아서 배열의 크기만큼 나머지 연산을 하여 배열의 인덱스로 추가해 주는 함수이다.
     */
    int convertToIndex(int hashcode) {
        return hashcode % data.length;
    }
    
    /*
     * key값을 이용해서 연결리스트에서 해당 key값을 찾고 일치하는 node를 반환해 준다.
     */
    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;
    }
 
    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.setValue(value);
        }
    }
    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? "Not found " : node.getValue();
    }
}
 
public class Main {
    public static void main(String[] args) {
        HashTable h = new HashTable(3);
        h.put("a", "123");
        h.put("b", "qwe");
        h.put("c", "asd");
        h.put("d", "zxc");
        h.put("e", "aa");
        
        System.out.println(h.get("a"));
        System.out.println(h.get("b"));
        System.out.println(h.get("c"));
        System.out.println(h.get("d"));
        System.out.println(h.get("e"));
    }
}
 

HashTable 작동원리

 

1. 입력 'x' 를 받아서 hashfunction을 이용해 hashcode를 생성한다.( f(x) = hashcode)

2. hashcode를 배열의 인덱스 값으로 환산한다.

3. 배열의 인덱스를 이용하여 값을 저장하고 검색한다.

 

자료구조

배열은 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 검색 속도가 빠르다.

하지만 데이터의 삽입 삭제시 데이터를 전부 한칸씩 밀어내고 삽입하거나 빈자리를 다시 채우기 위해 한칸씩 전부 이동해야 하기때문에 삽입과 삭제에서는 효율이 좋지 않다.

 

연결리스트는 삽입 삭제는 노드들의 참조하는 주소들만 수정해 주면 되기 때문에 삽입, 삭제는 빠르게 처리가 가능하다. 하지만 데이터를 삽입, 삭제할때 처음 노드 또는 마지막 노드가 아니면 데이터를 전부 순회검사해야하기 때문에 효율이 떨어진다. 검색할때도 마찬가지로 하나씩 순화검사를 해야하기 때문에 효율이 좋지 않다.

 

이러한 한계를 극복하기 위해서 해쉬를 사용한다.

 

해쉬는 입력값을 해쉬함수를 이용하여 어떤 정수값으로 치환하고 그 정수값 자체가 배열의 인덱스 값이기 때문에 검색하는데 효율이 좋다.

 

배열의 4공간에 데이터를 넣는다고 한다면 4개의 공간에 데이터가 골고루 들어가는것이 좋을 것이다.

예를들어 

김씨 공간, 이씨 공간, 박씨 공간 3가지 공간이 있는데

김씨만 자꾸 들어와서 김씨공간만 꽉차고 나머지는 비어있으면 공간활용도에서 손해를 보게 된다.

해쉬알고리즘을 짤때는 이러한 collision을 줄이는 방향으로 만드는것이 관건이다. 

 

해쉬알고리즘의 collision

- 다른 데이터가 들어왔지만 똑같은 해쉬 코드를 만들어 낼 경우(데이터는 무한하지만 해쉬코드는 한정적이기 때문에)

- 서로다른 해쉬코드가 있지만 동일한 배열방의 인덱스를 배정하는 경우

 

 

해쉬알고리즘

 

1. 고정크기배열을 선언한다.

2. hash함수로 만들어진 정수형태의 hashcode를 배열의 크키로 나머지연산을 하여 인덱스로 설정하고 배열에 할당해 준다.

3. 배열에 데이터를 추가하고 배열 내부에서의 데이터는 연결리스트를 이용한다.