Hash 자료구조 알아보기

본 포스팅은 jisikTank 스터디에 참여하며 정리한 문서입니다.
jisikTank CS지식 Git Repository

---

 

해시(Hash)

유튜버 A가 업로드한 영상을 다른 유튜버가 같은 파일을 올리려고 하면 오류 메세지 and 유튜버 A에게 알림이 뜬다?! 어떻게 하는 걸까..? -> Hash Table

• 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
• 해시 함수를 구현하여 데이터를 해시 값으로 매핑한다.

 

Hash Function(key: 숫자, 파일데이터, 문자열..) -> HashCode -> Index -> Value

배열 공간을 고정된 크기 만큼 만들어 두고, 해시 코드를 배열의 크기 만큼 나머지 연산을 통해 배열에 나눠 담는다.

해시코드 자체가 배열의 인덱스로 사용되기 때문에 해시코드로 데이터의 위치에 바로 접근할 수 있어서 검색 속도가 빠르다!

cf) 블록체인 해시 코드 : 블록체인의 기본 원리는 거래 정보를 모두 공유하는 것인데, 거래 데이터를 모두 나눠가지면 메모리의 심한 낭비. 해시 코드만 저장하면 매우 단축 가능!

 

• 탐색, 삽입, 삭제 연산 모두 해시 함수를 거치는 시간만 소요되기 때문에 일반적으로 O(1)의 시간 복잡도
• 해시 테이블
  • 버킷(Bucket)과 슬롯(Slot)으로 구성된 이차원 배열
  • 버킷 개수 : 해시 함수를 통해 나오는 주소 값의 범위
  • 슬롯 개수 : 각 버킷에 저장할 수 있는 데이터(key)의 개수

 

Collision

서로 다른 키값으로 동일한 해시코드를 만들어 내기도 한다.

키 값은 가지수 무한한데 해시코드는 정수이기 때문, 또 value 배열의 크기가 한정되어 있다!

 

Lee -> 해시함수 -> 5

Kim -> 해시함수 -> 3

Park -> 해시함수 -> 2

Chun -> 해시함수 -> 5 // Lee와 해시값 충돌

 

최악의 경우: 한 Index에 모든 데이터가 집중되는 경우 탐색이 빠른 이점을 가질 수 없다. O(1) -> O(N)

 

그래도 해시 테이블을 쓰는 이유는?

적은 자원으로 많은 데이터를 효율적으로 관리하기 위함.

하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해짐!

• 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능해진다.
• 이상적인 해시 테이블의 시간복잡도 O(1), 이진탐색트리는 O(log N)

 

Collision 해결 방법

• Chaining : 연결리스트로 노드를 계속 추가해나가는 방식(제한 없이 계속 연결 가능, but 메모리 문제)
• Open Addressing: 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용(해당 키 값에 저장되어 있으면 다음 주소에 저장)
• 선형 탐사: 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
• 제곱 탐사: 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

 

실습(LinkedList)

int getHashcode(sung)

s(115) + u(117) + n(110) + g(103) = 445

g(103) + i(105) + n(110) = 321

h(104)+ e(101) + e(101) = 306

m(109) + i(105) + n(110) = 324

int convertToIndex(HashCode) : HashCode % size

445 % 3 = 1

321 % 3 = 0

306 % 3 = 0

324 % 3 = 0

Java code로 해시 테이블 살펴보기

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 getKey() {
			return key;
		}
		public void setKey(String key) {
			this.key = key;
		}
		public String getValue() {
			return value;
		}
		public void setValue(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;
			}
		}
		// 해당 index에 찾으려는 key값이 존재하지 않으면 null 반환 
		return null;
	}
	
	// key값과 value로 데이터 저장
	void put(String key, String value) {
		int hashcode = getHashCode(key);
		int index = convertToIndex(hashcode);
		
		// 각 key별 hashcode, index 확인해보기 
//		System.out.println(key +", hashcode("+hashcode+"), index(" + index+")");
		
		LinkedList<Node> list = data[index];
		
		// 해당 Index에 기존 생성된 LinkedList가 없는 경우 생성
		if(list == null) {
			list = new LinkedList<Node>();
			data[index] = list;
		}
		Node node = searchKey(list, key);
		
		if(node == null) {
			// key값과 동일한 노드가 없다면 만들어서 넣어줌
			list.addLast(new Node(key, value));
		}else {
			// key값과 동일한 노드가 이미 있다면 대체 
			node.setValue(value);;
		}
	}
	
	// key 값을 가지고 data 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 Test {

	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"));
		
		// 없는 data?
		System.out.println(h.get("jee"));
		
	}

}

 

참고자료

• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Hash.md
• [자료구조 알고리즘] 해쉬테이블에 대해 알아보고 구현하기 - 엔지니어대한민국(Youtube)
• 삼성SDS 대학생 알고리즘 특강 2021 교재