해시 테이블(Hash Table)을 간단하게 알아보자.

해시 테이블을 간단하게 설명하면?

데이터의 해시 값을  테이블 내 주소로 이용하는 탐색 알고리즘!

 

1. 해시 테이블은 key-value 형식으로 데이터를 저장합니다.
2. 검색하고자 하는 키 값을 입력받아 F(key) 해시함수를 통해 반환합니다.
3. 반환받은 hashcode를 배열의 index로 환산해서 데이터 내 value에 접근합니다.

 

블록체인에서 각 사용자의 공공장부를 확인할 때 많이 사용합니다.

정보의 탐색 시간을 줄이기 위해 해시코드로 만들어 배포, 해시 코드를 비교합니다.

해시 코드를 배열의 개수로 나머지 연산해 배열에 나눠 담습니다.

즉 해시 코드 자체가 배열의 인덱스로 사용됩니다.

 

 

하나의 인덱스 안에 해시 코드가 중복돼서 모일 경우 Collision이 발생합니다.

O(1) -> O(n)

different key -> same code

different code -> same index

 

자료구조 측면에서 해시 테이블, 맵, 사전은 용어의 차이일 뿐 동일합니다.

 

 

해시 함수 

H(k)= k mod M

M: 해시 테이블의 슬롯 사이즈.

해시 주소 값의 범위는 0~M-1

테이블 크기는 소수로.

소수가 아닌 수 A라고 가정해 보면

A의 모든 약수는 자신의 배수가 곧 키값이 된다.

예를 들면, 12로 Mod 연산을 한다고 했을 때,

 

12의 약수

input : 3 6 9 12 15 18 21 24 ...

output : 3 6 9 0 3 6 9 0...

 

input : 4 8 12 16 20 24 ...

output : 4 8 0 4 8 0 ...

 

Open Addressing method

1. 선형 조사법 : 바로 옆의 자리가 비었는지 확인 후 비어있으면 그 자리에 데이터를 저장

f(k) + 1 -> f(k) + 2 -> f(k) + 3 -> …. 

DDD는 48에 저장.

 

 

2. 이차 조사법 : 말 그대로 공간을 좀 더 멀리 찾음.

f(k) + 1² -> f(k) + 2² -> f(k) + 3² -> ….

 

3. 이중 해시:  키가 다르면 빈 공간을 찾기 위해 건너뛰는 길이도 달라 클러스터 현상의 발생 확률을 현저히 낮출 수 있다.

첫 번째 해시 함수 : key를 해싱하는 과정에서 필요한 해시 함수
두 번째 해시 함수 : 충돌 발생 시 몇 칸 뒤가 비었는지 살피기 위한 함수

 

 

Closed Addressing method

체이닝 :  충돌이 발생해도 자신의 자리에 저장하는 방법.

즉 동일한 해쉬 값에 대해 여러 값이 저장

구현 과정

import java.util.*;

class HashTable {
	class Node {
		String key;
		String value;
		public Node(String key, String value) {
			this.key=key;
			this.value=value;
		}
		//get
		String value() {
			return value;
		}
		//set
		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;
		//key 문자열을 돌면서 각 문자를 c에 저장.
		for(char c : key.toCharArray()) {
			hashcode += c;
	}
		return hashcode;
	}
	
	//해시코드를 배열의 인덱스 값으로 변환
	int convertToIndex(int hashcode) {
		return hashcode % data.length;
	}
	
	//키 탐색 
	Node searchKey(LinkedList<Node> list, String key) {
		//리스트가 없으면 null
		if (list == null)
			return null;
		//리스트에 찾는 key가 있으면 해당 노드 반환.
		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);
		}
	}
	
	//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;
	}
}

class Main {
	public static void main(String[] args) {
       HashTable h = new HashTable(11);
       h.put("test", "Hello world");
       h.put("testing", "This is for you");
       h.put("Coding", "I dont like it");
       h.put("hi", "hashcode test");
       
       System.out.println();
       System.out.println(h.get("test"));
       System.out.println(h.get("testing"));
       System.out.println(h.get("Coding"));
       System.out.println(h.get("hi"));
    }
}

 

 

시간 복잡도 

• Worst : O(n)
• Best : O(1)