[자료구조] Hash Table

Hash Table 이란?

검색하고자 하는 키 값을 입력 받아서 Hash 함수를 돌려서 반환 받은 Hash Code를 배열의 인덱스로 환산을 해서 데이터 접근을 하는 방식의 자료구조

F(key) -> HashCode -> Index -> Value

• Hash Table은 검색속도가 매우 빠르다
• Hash Algorithm은 collision(충돌)이 얼마나 일어나지 않냐에 따라 갈린다.

# Hash Table 코드 구현
import java.util.LinkedList;

class HashTable{
	class Node{
    	String key;
        String value;
        public Node(String key, String value){
        	this.key = key;
            this.value = value;
        }
        String value(){
        	return value;
        }
        void value(String value){
        	this.value = value;
        }
    }
    
    LinkedList<Node>[] data;
    
    HashTable(int size){
    	this.data = new LinkedList[size];
    }
    
    int getHashCode(String key){
		int hashcode = 0;
        for(char c : key.toCharArray()){
        	hashcode += c;
        }
        return hashcode;
	}
    
    int convertToIndex(int hashcode){
    	return hashcode % data.length;
    }
    
    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.value(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.value();
    }
}

# 테스트 클래스
public class HashTableTest{
	public static void main(String[] args){
    	HashTable h = new HashTable(3);
        h.put("sung", "She is pretty");
        h.put("jin", "She is a model");
        h.put("hee", "She is an angel");
        h.put("min", "She is cute");
        System.out.println(h.get("sung"));
        System.out.println(h.get("jin"));
        System.out.println(h.get("hee"));
        System.out.println(h.get("min"));
    }
}

# 결과 값