[자료구조/Java] 해시 테이블 (Hash Table)

 

https://www.youtube.com/watch?v=Vi0hauJemxA&t=4s

 

검색하고자 하는 key 값을 입력받아 해시 함수를 돌려 반환받은 HashCode를 인덱스로 해서 데이터에 접근하는 방법!

(key : 문자열, 숫자, 파일데이터)

 

암호화폐의 핵심 기술인 블록체인에서도

각 사용자들의 공공장부를 비교할 때도 해시코드를 이용한다.

 

해시테이블의 장점

검색 속도가 매우 빠르다! O(1)

(해시 함수를 통해 만들어낸 해시 코드는 정수이다 → 배열 공간을 고정된 크기만큼 미리 만들어놓고 나눠담는다

해시코드 자체가 배열방의 인덱스로 쓰이기 때문에, 검색을 할 필요가 없고 바로 데이터의 위치에 접근할 수 있다!)

 

해시테이블의 단점

규칙에 따라 공간 활용이 비효율적으로 될 수 있다(Collision이 일어날 수 있다, 최악의 경우 O(n)까지 걸릴 수 있다)

→ 규칙을 잘 만드는 것이 필요! (Hash Algorithm)

 

Hash Algorithm & Collision

- 다른 키 값으로 같은 코드를 만들어 내기도 한다.

   - 키 값은 무한한데 반해서 코드는 정수개 만큼만 제공할 수 있기 때문에 중복이 발생

- 해시코드는 다른데 인덱스가 같을 수도 있다.

이런 경우 Collision(충돌)이 발생한다.

 

 

코드

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;
    }
    
    //index
    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);
        System.out.println(key+", hashcode("+ hashcode +"), index("+index+")");
        
        //기존 배열방에 있는 것을 가져옴
        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 Main{
	public static void main (String[] args){
    	HashTable h = new HashTable(3);
        
        h.put("sung", "She is smart");
        h.put("jin", "She is ambitious");
        h.put("hee", "She is loud");
        h.put("min", "She is strict");
        h.put("min", "She is not strict");
        
        System.out.println(h.get("sung"));
        System.out.println(h.get("jin"));
        System.out.println(h.get("hee"));
        System.out.println(h.get("min"));
    }
}

 

결과

sung, hashcode(445), index(1)
jin, hashcode(321), index(0)
hee, hashcode(306), index(0)
min, hashcode(324), index(0)
min, hashcode(324), index(0)
She is smart
She is ambitious
She is loud
She is not strict

 

-끗-