해시테이블(Hashtable)

해시테이블은 해시맵(HashMap)과 함께 Map을 구현한 키와 값 쌍을 데이터로 저장한 컬렉션(Collection)입니다. 여기서 키는 유일해야만 합니다. 해시테이블은 이 키를 가지고 키에 해당하는 값을 찾습니다.

Hashtable과 HashMap의 차이

Hashtable과 HashMap과의 차이점은 Thread-Safe인지 아닌지가 그 차이점인데요. Hashtable은 동기화가 걸려있어서 Thread-Safe하다고 할 수 있으며 HashMap은 동기화가 없어 unsafe하다고 할 수 있습니다. 그래서 안전성을 추구한다면 Hashtable을 쓰시면 되고, 데이터의 빠른 처리를 위해서라면 HashMap을 사용하시면 됩니다.

여기서 Hastable의 Thread-Safe가 무슨 의미를 하는지 맨 아래의 예제를 통해서 알아보도록 하세요.

해시맵의 사용법을 알고싶으신 분은 아래의 링크를 참고해주세요.

reakwon.tistory.com/151

 

[자바] 해시맵(HashMap)의 개념과 사용 예, 기본 메소드와 같은 키인지 판별하는 방법

해시맵(HashMap) 해시맵은 이름 그대로 해싱(Hashing)된 맵(Map)입니다. 여기서 맵(Map)부터 짚고 넘어가야겠죠? 맵이라는 것은 키(Key)와 값(Value) 두 쌍으로 데이터를 보관하는 자료구조입니다. 여기서

reakwon.tistory.com

 

인터페이스인 Map을 구현한 만큼 HashMap과 사용법이 거의 비슷합니다. put으로 키와 값을 저장하고 get으로 키에 해당하는 값을 읽어옵니다. Hashtable에서 table은 소문자라는 점! 유의해주시길 바라요.

예 ) put, get 메소드 사용방법

import java.util.Hashtable;
import java.util.HashMap;
import java.util.Map;
public class Main {
	public static void main(String[] ar) {
		Map<String,Integer> ht=new Hashtable();
		ht.put("key1", 50);
		ht.put("key2",100);
		ht.put("key2",250);	//같은 키가 들어갈 경우에는?
		System.out.println(ht);
		System.out.println(ht.get("key1"));
		System.out.println(ht.get("key2"));
		System.out.println(ht.get("key3"));	//키가 없을 경우에는?
		
	}
}

 

결과

{key2=250, key1=50}
50
250
null

 

만약 동일한 키를 가지고 데이터를 집어넣게 된다면 가장 마지막의 키와 값 요소로 저장이 됩니다. 그리고 키가 존재하지 않으면 null을 반환합니다. 

예) 갖고 있는 모든 키를 순회(keySet)

만약 Hashtable이 갖고 있는 모든 키를 알고 싶다면 어떻게 할까요? 그럴때는 keySet()메소드로 모든 키를 가져올 수 있습니다. 이때 반환하는 자료형은 Set입니다. 아래의 코드같이 키와 값을 추출할 수 있습니다.

public static void main(String[] ar) {
	Map<String,Integer> ht=new Hashtable();
	ht.put("foo",100);
	ht.put("bar",250);
	for(String key:ht.keySet()) {
		System.out.println("{"+key+","+ht.get(key)+"}");
	}
}

 

결과

{bar,250}
{foo,100}

 

예) Hashtable에 Hashtable을 추가(putAll)

만약 두 Hashtable을 합치고 싶다면 putAll() 메소드를 사용하면 됩니다. 다만 putAll()의 인자로 전달한 Hashtable의 키, 값의 변화가 있다해도 합쳐진 Hastable에는 영향을 받지 않습니다.

public static void main(String[] ar) {
	Map<String,Integer> ht1=new Hashtable();
	ht1.put("key1",9999);
	ht1.put("key2",2020);
		
	Map<String,Integer> ht2=new Hashtable();
	ht2.put("key3",3030);
	ht2.put("key4",8888);
		
	ht2.putAll(ht1);
	System.out.println(ht2);
		
	ht1.put("key5",5555);	//ht1에 데이터 추가
	System.out.println(ht2);
}

 

결과

{key4=8888, key3=3030, key2=2020, key1=9999}
{key4=8888, key3=3030, key2=2020, key1=9999}

 

예) ForEach() 메소드로 키와 값 순회하기

Hashtable에는 ForEach메소드가 존재하는데, 이것을 가지고 키와 값으로 동작을 정의할 수 있습니다. 람다식을 알긴해야하는데, 사용법만 알아도 상관은 없습니다. 

public static void main(String[] ar) {
	Map<String,Integer> ht=new Hashtable();
	ht.put("application layer", 7);
	ht.put("presentation layer", 6);
	ht.put("session layer", 5);
	ht.put("tranport layer", 4);
	ht.put("network layer", 3);
	ht.put("datalink layer", 2);
	ht.put("physical layer", 1);
	ht.forEach((key,value)->
	{
		System.out.println("{"+key+","+value+"}");
		
	});
 }

 

결과

{session layer,5}
{physical layer,1}
{datalink layer,2}
{presentation layer,6}
{tranport layer,4}
{network layer,3}
{application layer,7}

 

 

Hashtable의 Thread-Safe

이제 여기서 Hashtable이 왜 Thread-Safe한지 설명하도록 하겠습니다. 우선 쓰레드에 대한 개념에 대해서 알 필요가 있습니다. 자바 쓰레드의 사용법은 아래의 링크를 참고해주세요.

reakwon.tistory.com/84

 

[JAVA/자바] 쓰레드(Thread) 다루기( Thread상속, Runnable 구현, join)

쓰레드(Thread) 쓰레드(Thread)는 간단히 정의하면 하나의 프로세스(실행중인 프로그램이라고 합니다.)에서 독립접으로 실행되는 하나의 일, 또는 작업의 단위를 말합니다. 뭐, 더 간단히 말해 쓰레

reakwon.tistory.com

 

우선 Thread-Safe하지 않은 HashMap의 코드로 아래의 코드를 작성해보고 결과를 봅시다.

public class Main {
	static Map<String,Integer> hm=new HashMap();	//thread-unsafe
	public static void main(String[] ar) throws InterruptedException {
	
		Runnable runnable=new Thread() {
			@Override
			public void run(){
				hm.put("http",80);
				hm.put("ssh", 22);
				hm.put("dns", 53);
				hm.put("telnet",23);
				hm.put("ftp", 21);
				hm.forEach((key,value)->
				{
					try {
						Thread.sleep(1000);
					}catch(InterruptedException e) {
						e.printStackTrace();
					}
					System.out.println("{"+key+","+value+"}");
				
				});
			}
		};
		Thread thread=new Thread(runnable);
		thread.start();
		Thread.sleep(1000);
		hm.put("dhcp",67);
		System.out.println("MainThread end");

	}
}

 

보세요. 이 코드의 대한 저의 의도는 생성된 쓰레드(이하 thread라고 칭하도록 하겠습니다.)가 1초마다 run() 메소드의 저장된 키와 값을 순회하면서 출력하는 겁니다. 물론 예외없이 정상적으로요. 그러니 출력은 아래와 같아야하는 것이 이 코드의 의도입니다. 물론 MainThread가 끝나는 시점은 언제인지 예측 불가능하므로 어디서 나오든 상관없습니다. 중요한 것은 ftp~ssh까지만 출력되어야하는 것이 저의 의도입니다.

MainThread end
{ftp,21}
{telnet,23}
{dns,53}
{http,80}
{ssh,22}

 

하지만 우리의 예상과는 다르게 아래와 같이 출력됩니다. ConcurrentModificationException이라는 예외(Exception)가 발생하게 됩니다. 쓰레드들이 동시에 데이터를 변경할때 이 예외가 발생합니다.

MainThread end
{ftp,21}
{telnet,23}
{dns,53}
{http,80}
{ssh,22}
{dhcp,67}
Exception in thread "Thread-1" java.util.ConcurrentModificationException
	at java.base/java.util.HashMap.forEach(HashMap.java:1428)
	at aa.Main$1.run(Main.java:18)
	at java.base/java.lang.Thread.run(Thread.java:831)

 

왜 이런 예외가 발생할까요? 코드를 하나씩 해석해보도록 합시다.

자, HashMap은 두 스레드가 공용으로 사용할 수 있도록 static으로 지정해놓았고, 생성된 쓰레드는 해시맵에 http~ftp까지의 키와 값을 put하고 있습니다(여기서 value는 그 프로토콜의 포트번호를 의미합니다. 뭐 여기서는 중요한게 아니지요.) thread는 put으로 키,값을 저장하고 난 후에 forEach() 메소드를 이용해서 1초마다 갖고 있는 키와 값을 출력합니다. 

메인스레드에서는 thread가 forEach() 메소드를 수행할 시간을 벌어주기 위해서 1초간 잠재워줍니다. 그 후 thread는 자신의 루틴(routine) 중 forEach()메소드를 실행합니다. 

이때 thread가 forEach() 메소드가 수행하는 중에 메인 쓰레드에서 put으로 데이터를 집어넣고 있는 상황이죠. 즉, HashMap에 동시에 접근해서 변경이 발생하게 되는 그런 코드입니다. 

우리의 의도대로 동작하게 만드려면 어떻게 해야할까요? 이럴때 synchronized라는 키워드로 우리가 직접 동기화를 처리할 수도 있지만 더 간단한 방법으로는 바로 Hashtable을 사용하는 것입니다. 이 문제를 해결하려면 단 한줄만 바꾸면 됩니다.

static Map<String,Integer> hm=new Hashtable();	//thread-safe

 

물론 hm(HashMap)이라는 변수도 ht(Hashtable)로 바꾸면 더 일관성있겠죠. 그 후의 결과는 우리의 의도대로 아래와 같이 동작함을 알 수 있습니다.

{ftp,21}
{ssh,22}
{http,80}
{dns,53}
{telnet,23}
MainThread end

 

이처럼 스레드에 대해서 동시접근에 안전하려면 Hashtable을 쓰는 것이 좋고, 단일 쓰레드에서 사용한다면 HashMap을 쓰는 것이 좋습니다.

지금까지 Hashtable의 개념, 그리고 사용방법과 HashMap과의 차이점을 코드를 통해서 알아보았습니다.

반응형
블로그 이미지

REAKWON

와나진짜

,

 

 

해싱(Hashing)

해싱(Hashing)은 데이터를 관리하는 고급 기법으로 검색(search), 삽입(insert), 삭제(delete)를 단시간(O(1))에 할 수 있게 만들어주는 기법입니다.

예를 들면, 리스트에서 단어를 찾는 시간이 O(n)시간이 걸리고, 이진 트리의 경우 O(nlogn)이 걸리죠. 그런데 우리는 이것을 해싱이란 기법을 사용하여 O(1)만에 해결할 수 있습니다. 진짜 죠낸 빠르네요.

해싱은 산술적 연산을 이용해서 구현해야합니다. 이런 해싱은 크게 두 가지 종류가 있는데요. 하나는 정적 해싱(static hasing)이고 다른 하나는 동적 해싱(dynamic hasing)입니다. 이번 포스팅은 정적 해싱에 대한 이야기를 합니다.

 

정적 해싱(Static Hashing)

정적 해싱이라는 기법은 고정 크기의 버킷을 갖는 해시 테이블(담을 그릇)에 데이터를 담는 것을 말합니다.

해시 테이블(Hash Table)

설명 전에 해시 테이블(Hash Table)에 관해서 알고 가야합니다. 해시 테이블은 키(Key)값(Value)으로 구성되어 있는 데이터가 저장된 테이블이라고 보시면 됩니다. 해시 테이블은 행과 열로 구성되어 있다고 생각하세요. 여기서 두 가지 용어가 있는데 버킷(bucket)슬롯(slot)입니다.

 

버킷(bucket) : 버킷은 해시 테이블의 행 인덱스(주소)라고 입니다. 

슬롯(slot) : 슬롯은 그 행을 열의 인덱스(주소)라고 생각하시면 됩니다.

 

아래의 그림은 버킷이 11, 슬롯이 3인 해시 테이블입니다. 여기서 data가 전부 차있는 버킷도 존재하고 그렇지 않은 곳도 존재합니다. bucket[0]을 보시면 이미 데이터가 가득차있네요. 다음 들어올 데이터가 bucket[0]에 들어갈 데이터라면 어떻게 될까요? 넣을 수 없는 상황이 되겠죠? 

그것을 우리는 오버플로(Overflow)라고 하며 이 문제를 해결해야합니다. 잠시후 설명하도록 하겠습니다.

 

 

쳐넣는거는 알겠는데 어떻게 넣냐구요? 해시 함수를 이용해서 넣을 수 있습니다.

 

해시 함수(Hash Function)

해시 함수는 h()라 하고 찾을 키를 k라고 한다면 해시 함수는 h(k)라 표현합니다. 해시 함수는 k를 이용해서 해시 테이블에 매핑(mapping)하는 역할을 하게 됩니다. 즉, 데이터를 집어넣을 장소(주소)를 정합니다. 좋은 해시 함수는 계산이 쉬워야하고, 출돌을 최소화 시켜야합니다. 그리고 모든 버킷에  데이터가 고르게 분포되어야합니다. 앞서말한 오버플로를 최소화하기 위함이죠. 해시 함수에는 어떤 것들이 있을까요?

 

참고로 아래의 해시함수들은 모두 키가 양의 정수를 갖는데, 만약 키를 문자나 문자열로 쓰고 싶다면 문자(열)을 정수로 변환시키는 작업이 필요합니다.

1) Division

나눗셈을 이용하는 해시 함수입니다. 모듈러 연산(나머지를 구하는 연산으로 % 아시죠?)을 이용하여 집어 넣을 곳을 정합니다. 키들은 음수이면 안된다는 가정이 있습니다.

 

h(k) = k % D

 

해시 테이블은 적어도 D개의 버킷을 가지고 있어야합니다. k가 15이고 D가 7이라면 h(15) = 15 % 7 = 1 이 됩니다.

 

2) Mid-Square

키를 제곱하여 버킷을 정하는 건데요. 키를 제곱한 후 중간에 몇 비트를 선택하여 버킷의 주소를 구합니다. r비트를 선택하면 해시 함수 결과로 나올 수 있는 값의 범위는 0 ~ (2^r) -1이 되겠죠?

r을 3로 정해보고,  key값을 121으로 정해서 계산해보면 121^2 = 14,641인데 이것의 가운데 3개를 가져오면 h(121) = 464가 됩니다.

 

 

 

3) Folding

폴딩은 키를 몇몇 부분(Part)로 나눈후 그 값을 더하여 해시 함수의 결과를 도출합니다. 방식에 따라 두가지가 있는데요. 그냥 부분을 일정하게 나눈 후 더하는 방식인 시프트 폴딩(Shift Folding)과 부분의 경계를 뒤집어서 계산하는 경계폴딩(Boundary Folding)이 있습니다.

 

1. 시프트 폴딩(Shift Folding)

k가 12345678910일때 3개의 10진수로 나눈다면 h(12345678910) = 123 + 456 + 789 + 10이 되고 더하게 되면 1378이 되므로 h(12345678910) = 1,378 입니다.

 

 

2. 경계 폴딩(Boundary Folding)

k가 아까와 같이 12345678910이고 3개의 10진수로 나눈다면 h(12345678910) = 123 + 654 + 789 + 01이며 결과는 1,567입니다. 456과 10이 뒤집혀진 것을 알 수 있네요.

 

 

4) Digit Analysis

이 방식은 이미 모든 키들을 알고 있는 정적 파일에 유용한 방법으로 각 키의 주소를 결정할 때 많이 나오는 수는 제외하고 적게 나오는 키의 수만 선택됩니다. 

예를 하나 들어보겠습니다. 키가 5개가 미리 정해져있다고 칩시다. 각 키는 0112311, 0234522, 0167811, 0291022, 0111222 에서 숫자 3개를 선택해서 해시 함수의 결과를 꺼내면 hash(0112311) = 123, hash(0234522) = 345, hash(0167811) = 678, hash(0291022)= 910, hash(0111222) = 112 가 됩니다. 01 11 02 22는 많이 겹치는 수이기 때문에 고르지 않습니다.

이름에서 알 수 있듯이 키의 숫자들을 분석을 해야하는데요. 분석하려면 미리 결정된 데이터들이 있어야합니다. 즉, 키가 미리 결정되어져 있어야한다는 의미입니다. 그러니까 왜 정적 파일에 유용한지 이해가 가시죠?

 

오버플로 핸들링(Overflow Handling)

앞서 오버플로에 대해서 이야기했었죠? 오버플로를 해결하기 위해서는 두 가지 핸들링 기법이 있는데, 개방 주소법(Open Address)체이닝(Chaining) 방식이 있습니다.

 

1) 개방 주소(Open Address)

오버플로가 발생했을때 공간이 남는 버킷에 집어 넣는 것으로 공간이 남는 버킷 어느 곳이나 있으면 넣는 다고 하여 개방 주소라고 합니다. 남는 곳을 어떻게 구햐냐에 따라 4 가지 방식이 존재합니다.

 

1. 선형 탐사(Linear Probing)

선형 탐사만 알아도 나머지 probing방식은 이해할 수 있습니다. 고정된 폭을 정해서 그 폭만큼 버킷의 주소를 이동해서 남는 공간이 있는지 확인 후에 있으면 집어넣는 방식입니다. 그래도 남는 공간이 없다면 다시 그 폭만큼 버킷의 주소를 이동하죠. 만약 해시 테이블의 공간이 모자란다면 해시 테이블의 크기를 증가시키는데, 전부 찰때 증가시키는 것이 아니고 75% 정도 채워지면 해시 테이블의 크기를 증가시킵니다.

 

만약 폭을 i라고 하고 버킷의 크기를 b라고 한다면 해시 테이블은 (h(k) + i ) % b 의 식으로 계산됩니다.

 

 

 

2. 제곱 탐사(Quadratic Probing)

감 오시죠? 폭을 제곱하여 오버플로를 핸들링합니다. (h(k) + (i^2)) %b 로 계산됩니다. 만약 오버플로가 발생하면 i=1로 한칸 이동하여 찾고 그래도 실패하면 그 다음은 i=2가 되어 4칸을 이동하고, 그 다음은 i=3이 되어 9칸을 이동하여 검사하는 방식입니다.

 

아래 그림은 선형 탐사와 제곱 탐사를 비교한 그림입니다.

3. 무작위 탐사(Qandom Probing)

감 오시죠? 랜덤한 값을 폭으로 두고 계산합니다.

 

4. 이중 해시(Double Hashing)

해싱한 값을 한 번 더 해싱하는 방식입니다. 다른 방식보다 연산하는 시간이 걸립니다. 해시 연산을 한 번 더 하기 때문이죠.

 

2) 체이닝(Chaining)

체이닝은 이름과 같이 체인같이 연결하여 오버플로를 막는 방법인데요. 연결 리스트(Linked List) 배우셨죠? 각 버킷이 연결 리스트가 되고 원소가 계속 추가 될 수 있습니다.

아래는 체이닝 기법을 적용한 버킷이 6개있는 해시 테이블입니다.

이때 삽입할때 연결리스트의 앞에 삽입합니다. 이유는 매번 끝에 원소를 삽입하면 연결리스트에 끝까지 도달해야되기 때문에 삽입 시간이 오래 걸리기 때문입니다.

 

 

개방주소법이나 체이닝 방식이나 최악의 경우(Worst Case) 성공할때까지 검색하는 시간은 O(n)의 시간이 걸릴 수 있습니다. 하지만 균형잡힌 검색 트리(Balanced Search Tree)를 이용하면 이 시간은 O(logn)까지 줄일 수 있습니다.

 

다음 포스팅은 동적 해싱에 대한 이야기를 하도록 하겠습니다.

 

 

 

반응형
블로그 이미지

REAKWON

와나진짜

,