해시(Hash) 알고리즘

📝오늘 수업 도중 해시 알고리즘에 대해 들었는데.

정보를 조금 더 찾아보기로 했다.

본 글은 타 블로그에서 발췌한 내용으로 구성되었으며, 작성자가 수업을 들은 내용도 조금 추가가 되어있다.

구글 검색 기준 상위 5개를 참고하였고.

그중 괜찮다고 생각했던 블로그는 아래 블로그이다.(두고두고 볼 예정이다.)

hyeonstorage.tistory.com/265?category=578561

[자료구조] Java 해쉬(Hash) 기본 개념과 구조 (분리연결법)

💡 해시의 등장배경

해시의 등장배경은 배열과 리스트로 인함이였다.

배열은 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면

데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야 하기 때문에 많은 시간이 소요된다.

반면에 연결 리스트는 삽입, 삭제 시 인근 노드들의 참조 값만 수정해 줌으로써 빠른 처리가 가능했었다. 

단 처음 노드 마지막 노드 이외의 위치에서 데이터를 삽입, 삭제할 경우나 데이터를 검색할 경우네는 해당 노드를 찾기 위하여 처음부터 순회 검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어질 수 밖에 없는 구조다.

 

이러한 한계를 극복하기 위하여 제시된 방법이 바로 해쉬(Hash)이다.

 

 

💡 해시(Hash)란 ?

해시는 내부적으로 배열을 사용하여 데이터를저장하기 때문에 빠른 검색 속도를 가진다.

그리고 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 채우는 작업이 필요 없도록 특별한 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.

 

특정 데이터가 저장되는 인덱스를 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 삽입과 삭제 시 데이터의 이동이 없도록 만들어진 구조이다.

 

해시가 내부적으로 사용하는 배열을 Hash Table이라고 하며 그 크기에 따라서 성능 차이가 많이 날 수 있다. 

 

- 해시는 데이터를 다루는 기법 중 하나이다.

- 해시는 검색과 저장에서 아주 우수한 성능을 보인다.

- 해시의 핵심은 KEY, VALUE를 함께 저장하는 자료구조이다.

- KEY와 VALUE 가 한 쌍으로 존재한다. = Hash Table이라고 함.

- 배열의 인덱스와 다르게 순차적으로 저장되는 것이 아닌, 전 영역에 고르게 분포되어 저장된다는 특징을 가지고 있다. (🤜 배열보다 빠르게 값을 찾을 수 있다. )

- 연관 배열 구조 : Key와 Value가 1:1로 연관되어 있는 자료구조. Key를 이용해 Value를 알아낼 수 있다.

블로그에서 따옴. https://velog.io/@adam2/~

💡 해시 메소드

해시는 HashTable을 이용하여 데이터를 저장한다.

이때 특별한 알고리즘을 이용하여 고유한 숫자값을 만들어 인덱스로 사용하는데 

이 알고리즘을 구현한 메소드를 Hash Method 라고 하며

Hash Method에 의해 반환된 데이터 고유의 숫자 값을 hash Code라고 한다.

Java에서는 Object 클래스의 hashCode() 라는 메소드를 이용하여 모든 객체의 Hash Code를 쉽게 구할 수 있다.

 

💡 해시 메서드 Java Object 클래스 정리

Hash Method를 구현하는  방법은 여러가지가 있지만 가장 간단한 방법으로는 나머지 연산자를 이용하는 것이다.

데이터의 고유한 hashCode를 구한 뒤 hashCode를 테이블 크기로 나머지 연산을 한 결과를 해당 데이터의 인덱스로 사용하는 것이다.

 

예를들어 "a", "b", "c"의 hashCode가 각각 97,98,99라고 하고 Hash Table의 크기가 10이라고 했을 때 테이블에 저장될 인덱스는 다음과 같다.

 

97 % 10 = 7

98 % 10 = 8

99 % 10 = 9

 

즉, Hash Table의 인덱스 7에는 "a"를 저장하고 8에는 "b", 9에는 "C"를 저장하는 방식이다.

이후에 "a"를 검색할 때에는 "a"의 hashCode를 가지고 나머지 연산을 한 결과인 7번 인덱스를 바로 참조하여 데이터를 꺼낼 수 잇다.

 

또 다른 예를 들어보자

4,8,12,16,20,24,28,32 라는 hashCode를 가진 데이터가 있다고 했을 때, 데이터를 저장하기 위해 Hash Table의 크기를 8로 지정했다면 테이블에 저장될 인덱스는 다음과 같다.

4 % 8 = 4

8 % 8 = 0

12 % 8 = 4

16 % 8 = 0

20 % 8 = 4

24 % 8 = 0

28 % 8 = 4

32 % 8 = 0

데이터를 저장하기 위한 인덱스가 0번과 4번에 집중되는 것을 볼 수 잇다.

이처럼 hashCode가 다르더라도 나머지 연산을 한 결과는 같을 수 있으므로 Hash Table의 동일한 인덱스에 저장을 시도하려 할 경우 문제가 발생한다.

이렇게 저장하려는 위치에 이미 다른 데이터가 있어서 저장을 할 수 없는 현상을 충돌(collision)이라고 하며 이런 충돌을 최소화 하기 위한 방법으로는 나머지 연산의 값이 최대한 중복되지 않도록 테이블의 크기를 소수(prime number)로 만드는 것이다.

 

다음은 8보다 큰 소수인 11을 테이블의 크기로 지정했을 때 각 데이터들이 테이블에 저장될 인덱스 값이다.

4 % 11 = 4

8 % 11 = 8

12 % 11 = 1

16 % 11 = 5

20 % 11 = 9

24 % 11 = 2

28 % 11 = 6

32 % 11 = 10

이제는 충돌이 발생하지않는다. 하지만 Hash Table의 크기를 소수로 만드는 것은 충돌을 줄이는 방법이지 해결하기 위한 방법은 아니다. 추가적으로 10을 저장하려고 한다면 10 % 11 = 10이 되므로 이미 10번의 인덱스에는 32가 들어있기 때문에 충돌이 발생한다.

 

이처럼 충돌이 발생할 경우 이를 해결하기 위한 방법이 필요하며 충돌 해결 방법으로 개방주소법과 분리 연결법 두가지가 있다.

 

 

 

💡 KEY?

- Hash 에서 매핑할 때 사용하는 인덱스이다.

- Key는 절대로 중복되지 않는다는 특징을 가지고 있다.(고유한 값)

- 해시 함수의 input이 됨.

- 만약 Key가 중복이라면 나중에 들어온 값만 남는다.[해시 충돌(Hash Collision)]

- 키 값 그대로 저장소에 저장할 경우 다양한 키의 길이만큼 크기를 구성해두어야 하기 때문에 일정한 길이의 해시로 변경한다.

 

💡 VALUE?

- Key로 매핑 시 나오는 값이다.

- 저장소(bucket, slot)에 최종적으로 저장되는 값으로 hash와 매칭되어 저장.

 

💡 HashTable

- 해시 함수를 사용하여 키를 해시값으로 매핑하고 이 해시값을 주소로 삼아 데이터(value)를 key와 함께 저장하는 자료구조

- 데이터가 저장되는 곳을 버킷 또는 슬롯이라고 함.

- 해시테이블의 기본 연산은 삽입, 삭제, 탐색이다.

 

📝 key는 hash function을 통해 hash로 변경이 되며 hash는 value와 매칭되어 저장소에 저장이 된다.

📝 장점 : 해시 테이블은 key-value 가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색 과정에서 모두 평균적으로 0(1)의 시간복잡도를 가지고 있다.

📝 단점 

  1) 해시 충돌이 발생

  2) 순서/관계가 있는 배열에 어울리지 않는다. => 순서에 상관없이 key만을 가지고 삽입 검색 삭제하기 때문

  3) 공간 효율성이 떨어짐 => 데이터가 저장되기 전에 미리 저장공간을 확보해야하기 때문. 공간이 부족하거나 아예 채워지지 않은 경우가 발생

  4) hash function의 의존도가 높다 => 평균 시간 복잡도가 0(1) 이지만 해시함수가 매우 복잡하다면 해시 테이블의 연산 속도는 증가.

 

키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table 이라고 한다.

Direct-address table의 장점은 키의 개수와 테이블의 크기가 같기 때문에 해시 충돌의 문제가 발생하지 않는다.

하지만 실제 사용하는 키가 얼마 없는 경우, 즉 전체키 100개 중에 실제로는 10개 키만 사용한다 했을 때, 100개 크기의 데이블을 유지한다는 것이 메모리 낭비이다.

따라서 보통의 경우 실제 사용하는 키 개수보다 적은 해시테이블을운용하는데, 이런 이유로 해시 충돌이 발생하고 해시 충돌을 해결하기 위한 다양한 방법이 고안되었다.

 

 

💡 Hash코드?

- Hash로 값 생성 시, 고유의 주소값이 생성됨 🤜 이것을 숫자로 변환한 것을 해시코드라고 부름.

- 자바에서 해시코드는 Heap 영역의 인스턴스에 대한 참조 값이라고도 부를 수 있다.

 

💡 Hash Function(해시함수)

- Key를 고정된 길이의 hash로 변경해주는 역할을 한다. 이 과정을 hashing이라고 한다.

- 서로 같은 key가 같은 hash값을 갖게 되는 경우 해시 충돌이라고 한다. 

- 해시 충돌이 해시값 전체에 걸쳐 균등하게 발생하도록 하는 것도 중요하다.

  ex) 모든 키가 02라는 동일한 해시 값으로 매핑이 될 경우 데이터를 액세스 할 때 비효율성이 커지고 보안이 취약해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어진다.(서로 다른 키인데도 동일한 해시값)

- 아래 그림에서 Keys가 들어와서 hashfunction을 거쳐 hashes(HashValue)가 되는 것이다.

- 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수라고 할 수 있다.

 

 

위키백과 - 해시 그림

division method

숫자로 된 키를 해시테이블의 크기m으로 나눈 나머지를 해시값으로 변환한다.

간단하면서 빠른 연산이 가능한 것이 장점이다.

- h(k) = k mod m

- 예 : m = 20 and k = 91 ==> h(k) = 11

- 장점 : 한번의 mod 연산으로 계산, 빠름

- 단점 : 어떤 m 값에 대해서는 해시 함수값이 키값의특정 부분에 의해서 결정되는 경우가있음

           2^p이면 키의 하위 p비트가 해시 함수가 됨.

 

multiplication method

- 0에서 1사이의 상수A를 선택 : 0 < A < 1

- kA의 소수부분만을 택함.

- 소수부분에 m을 곱한 후 소수점 아래를 버린다.

- 예 : m=8, word size = w = 5, k = 21

       A = 13/32 를 선택

      kA = 21*13/32 = 273/32 = 8 +17/32

      m (kA mod 1) = 8 * 17/32 = 17/4 = 4.xxx

      h(21) = 4

꼭 위의 기법을 사용하여 해시 함수를 만들어야 하는 것은 아니다. 해시함수를 만드는 방법중 하나일 뿐이다.

 

숫자 키 k,A는 0과 1 사이의 실수일 때,

h(k) = (kA mod 1)*m

2진수연산에최적화된 컴퓨터 구조를 고려한 해시함수라고 한다.

나눗셈법보다는 다소 느리다.

 

univeral hashing

다수의 해시 함수를 만들고,이 해시함수의 집합h에서 무작위로 해시함수를 선택해 해시값을 만드는 기법

h에서 무작위로 뽑은 해시 함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 1/m로 만드려는 것이 목적

다음과 같은 특정 조건의 해시 함수집합 h는 1/m으로 만드는게가능하다고 수학적으로증명되엇다고한다.

- 해시 테이블의 크기 m을 소수로 정한다.

- 키값을 다음과 같이 r+1개로 쪼갠다 : k0, k1,...,kr

- 0부터 m-1 사이의 정수 가운데 하나를 무작위로 뽑는다. 분리된 키 값의 개수(r+1)만큼 반복해서 뽑는다.

  이를 a=[a0,a1,...,ar]로 둔다. 따라서 a의 경우의 수는 모두 mr+1가지이다.

- 해시함수를 다음과 같이 정의한다. 

- a가 mr+1가지이므로 해시함수의 집합 H의 요소 수또한 mr+1개이다.

위와 같은 조건에서는 키가 동일하더라도 a가 얼마든지 랜덤하게 달라질 수잇고,이에 해당하는 해시함수ha 또한 상이해지기 때문에 H는 유니버셜 함수가 된다.

 

💡 좋은 해시 함수란?

- 현실에서는 키들이 랜덤하지않음

- 만약 키들의 통계적 분포에 대해 알고있다면 이를 사용해서 해시 함수를 고안하는 것이 가능하겠지만 현실적으로어려움

- 키들이 어떤특정한 (가시적인)패턴을 가지더라도 해시함수 값이 불규칙적이 되도록 하는게 바람직함.

  * 해시 함수 값이 키의 특정 부분에 의해서만 결정되지 않아야함.

 

💡 해시 충돌

같은 Key에 값을 넣으면 이전 값은 사라지고 나중에 들어온 값만 남는다.

해시 충돌이 발생하게 되면 검출 속도를 느리게 만들고 버킷 오버플로우(?)를 발생시키는 문제가 나타난다.

- 버킷 오버플로우 ? 버킷의 크기가 작으면 서로 다른 키를 해시함수하여 같은 해시 값이 나와 버킷이 크기를 넘을 수 있음.

- 해시 충돌 발생 확률이 적을수록 좋다.

 

따라서 해시 충돌을 해결할 방법이 필요하다.

위의 그림에서 john과 sandra의 hash가 02로 같다. 이런 현상을 hash collision이라고 한ㄴ다.

해시 함수로 해시를 만드는 과정에서 서로 다른 key가 같은 해시로 변경되면 같은 공간에 2개의 value가 저장되므로 key-value가 1:1로 매핑되어야 하는 해시 테이블의 특성에 위배된다.

해시 충돌은 필연적으로 나타날 수 밖에 없다.

 

Hash Table에 이미 다른 데이터가 저장되어 있을 경우 데이터를 저장하지 못하는 충돌이 발생한다고 한다.

이를 해결하기 위한 방법으로는 개방주소법과 분리 연결법이 있지만 개방주소법은 충돌이 많이일어날 경우 심각한 성능저하가 발생할 수 있다.(특정블로그는 개방주소법을 아예 설명을안했음)

 

💡 해시 충돌 해결 법 1) - Chaning (JAVA - linkedList 활용) (분리 연결법)

 - 해시 테이블에 연결리스트에서 사용하는 Node객체를 저장하는 것.

즉 Hash Table의 셀마다 연결리스트 하나 씩 저장하도록 하고 충돌이 발생하는 데이터는 연결리스트의 다음 노드로 계속 추가해 가는 것이다.

이후에 데이터를 검색할 때에는 hash table의 인덱스를 찾은 후 셀에 연결된 리스트를 순차적으로탐색하며 찾으려는 hashCode와 저장된 노드의 hashCode를 비교하는 것이다.

 

 - 해시 충돌이 일어나면 연결 리스트를 이용해 데이터들을 연결하는 방식

 - 추가적인 메모리를 이용해 동일한 bucket(메모리라고 하면 되겠다) 연결 리스트로 하나씩 순차적으로 저장함.

 - 꼬리잡기 처럼 연결 리스트 내 하나의 노드가 되어 차례대로 연결되는 것을 의미함.

 - 연결 리스트만 사용하면 되므로 복잡하지 않고 같은 주소 값을 그대로 사용할 수 있음.

 - 하지만, 특정 주소에 계속 쌓이는 경우 성능이 현저하게 낮아지고 많은 메모리 공간을 잡아먹음

파포 귀찮아서 그림판..

 

체이닝은 저장소(bucket)에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트를 이용해 연결시키는 방법이다.

📝 장점

  - 한정된 저장소를 효율적으로 사용할 수 있다. => 미리 충돌을 대비해 많은 공간을 잡아놓을 필요가 없다.

  - 해시 함수를 선택하는 중요성이 상대적으로 적다 => 충돌이 나도 그냥 연결하면 되니까.

📝 단점

  - 한 hash에 자료들이 많이 연결되면 검색 효율이 낮아진다.(쏠림현상)

  - 외부 저장공간을 사용한다.

 

💡 분리 연결법을이용한 Hash 구현

package util;

public class Hash{
	
	//해쉬 테이블에 데이터를 저장할 Entry는 값과 다음 Entry를 가진다.
	private class Entry{
		private int value;
		public Entry next;
	}
	
	private int size;
	private Entry[] hTable;
	
//	Hash Table은 size와 배열 테이블을 생성한다.
	public Hash(int size) {
		this.size = size;
		this.hTable = new Entry[size];
	}
	
	
//	data를 가지고 hashCode를 생성하여 key를 추출한다.
//	실제 Hash 에는 특별한 알고리즘이 적용되어 hashCode를 생성하지만
//	본 코드에서는 data 값을 key로 함.
	public int getKey(int data) {
		return data;
	}
	
//	key 값으로 HashTable에 저장할 index를 결정하여 반환한다.
	public int hashMethod(int key) {
		return key % size;
	}
	
//	data를 HashTable에 저장한다.
//	Hash에 데이터 삽입은 키와 인덱스를 가지고 HashTable에서 해당 인덱스를 확인한다.
//	해당 인덱스가 비어있으면 Entry를 저장하면 되고
//	해당 인덱스에 값이 있다면 첫번째 Entry부터 순차적으로 탐색하여 Key가 삽입될 위치를 찾아 삽입한다.
//	Entry 리스트는 단순 연결 리스트이며 작은값부터 큰값 순서로 정렬되어 있다.
	public int add(int data) {
//		data의 hashCode를 key와 저장할 index를 얻는다.
		int key = getKey(data);
		int hashValue = hashMethod(key);
		
//		저장할 Entry 생성
		Entry entry = new Entry();
		entry.value = data;
		
//		hashTable의 저장할 index가 비어있다면, Entry를 저장하고 끝낸다.
		if(hTable[hashValue] == null) {
			hTable[hashValue] = entry;
			return 0;
		}
		
//		해당 인덱스에 값이 있다면 첫번째 Entry부터 순차적으로 탐색하여 Key가 삽입될 위치를 찾아 삽입한다.
//		Entry 리스트는 단순 연결 리스트이며 작은값부터 큰값 순서로 정렬되어 있다.
		Entry pre = null;
		Entry cur = hTable[hashValue];
		
//		해당 index의 연결리스트는 값의 크기가 작은 값부터 큰 순서로 정렬되어 잇다.
		while(true) {
			if(cur == null) {//Hash Table에 저장할 index가 비어있으면
				hTable[hashValue] = entry; //해당 index에 Entry를 저장한다.
				return 0;
			}else if(cur.value < key) {//해당 index의 커서노드 값이 key보다 작으면
				//커서를 하나 뒤로 옮긴다.
				pre = cur;
				cur =cur.next;
			}else {//해당 index의 커서 노드 값이 key보다 크다.(여기에 저장)
//				커서노드가 hashTable의 첫번째 노드이면
				if(cur == hTable[hashValue]) {
//					삽입 노드를 첫번재 노드로 삽입하고 다음 노드를 커서 노드로 지정한다.
					entry.next = cur;
					hTable[hashValue] = entry;
					return 0;
				}else {//첫번째 노드가 아니면
//					삽입 노드의 다음 노드로 커서 노드를 지정하고
//					전 노드의 다음 노드를 삽입 노드로 지정한다.
					entry.next = cur;
					pre.next = entry;
					return 0;
					
				}
			}
		}
	}
	
//	data가 있는 위치를 얻는다.
//	데이터의 위치 탐색은 hashMethod()로 index를얻은 후 해당 index에 데이터가 잇는지 탐색한다.
//  데이터가 있으면 index를 반환하고 없으면 -1을 반환한다.
	public int get(int data) {
		int key = getKey(data);
		int hashValue = hashMethod(key);
		
//		data가 있는 index의 첫번째 노드를 얻는다.
		Entry cur = hTable[hashValue];
		
		while(true) {
			if(cur==null) {//index가 비어있다면 -1반환
				return -1;
			}else if(cur.value == key) {//커서의 값과 키가 같으면 0 반환
				return hashValue;
			}else if(cur.value > key) {//커서의 값이 키보다 크면 -1 반환
//				리스트는 작은 값에서 큰값으로 정렬되어 있다.
				return -1;
			}else {//커서의 값이 키보다 작으면 다음 노드로 커서 이동
				cur = cur.next;
			}
		}
	}
	

//	data가 잇는 노드를 반환한다.
	private Entry getEntry(int data) {
		int key = getKey(data);
		int hashValue = hashMethod(key);
		// HashTable의 index의  첫번째 노드와 두번째 노드
        Entry pre = hTable[hashValue];
        Entry cur = pre.next;
        
        while(true){
            if(cur == null){    // 커서 노드가 null 이면 null 반환
                return null;
            }else if(cur.value == key){    // 커서 노드의 값이 키와 같으면 전 노드를 반환
                return pre;
            }else if(cur.value > key){    // 커서의 값이 키보다 크면 null 반환
                return null;
            }else{            // 커서의 값이 키보다 작으면 커서를 다음으로 이동
                pre = cur;
                cur = cur.next;
            }
        }
    }
    
    // data 를 제거를 위해서는 data에 해당하는 index의 Entry리스트에서 data의 앞 노드가 다음 노드를 data의 뒷 노드를 가리키게 하면 된다.
    public int remove(int data){
        Entry pre = null;
        // data가 있는 노드의 전노드를 가져오고 null이면 -1 반환
        if((pre=getEntry(data))== null){
            return -1;
        }
        // 전 노드가 data의 다음노드를 가리키게 한다.
        // data 노드를 건너뛰게 연결한다 (제거)
        Entry cur = pre.next;
        pre.next = cur.next;
        return 0;
    }
    
    public String toString(){
        StringBuffer result = new StringBuffer();
        Entry cur = null;
        for(int i=0; i<size; i++){
            result.append("[" + i + "]\t");
            cur = hTable[i];
            if(cur == null){
                result.append("n ");
            }else{
                while(cur!=null){
                    result.append(cur.value + "");
                    cur = cur.next;
                }
            }
            result.append("\n");
        }
        
        return result.toString();
    }
}

 

 

 

💡 해시 충돌 해결 법 2) 개방 주소법Open Addressing : 해시 충돌이일어나면 다른 buket에 삽입

  - 개방 주소법은 비어있는 hash를 찾아 데이터를 저장하는 기법. 따라서 개방주소법의 해시 테이블은 hash와 value 가 1:1 관계를 유지한다.

 

  - 개방 주소법은 chaning 처럼 추가적인 메모리가 필요 없다는 장점을 가지고 있다.

  - 또한 데이터를 직접 모두 읽어오기 때문에, 포인터를 쓸 일이없어 포인터를 사용함으로써 나타나는 오버헤드를 방지할 수 있다.

위의 그림에서 Jone과 Sandra의 hash가 동일해 충돌이 일어난다. 이때 sandra는 바로 그 다음 비어있던 153 hash에 값을 저장한다. 그 다음 ted가 테이블에 저장을 하려 했으나 본인의 hash에 이미 sandra로 채워져있어 ted도 sandra처럼 바로 다음 비어있던 154hash에 값을 저장한다.

이런식으로 충돌이 발생할 경우 비어있는 hash를 찾아 저장하는 방법이 개방주소법이다.

이때, 비어있는 hash를 찾아가는 방법은 여러가지가 있다.

 

 

💡 개방 주소법의 규칙

  - 개방 주소법은 대표적으로 3가지 방법을 추가적으로 가지고 잇음.

  1) 선형탐색(Linear Probing)

   - 해시 충돌 발생 시 다음 bucket 이나 몇 개의 bucket을 건너 뛰어 데이터를 삽입하는 방식

   - 해당 해시 값에서 고정폭(+n)을 건너 뛰어 비어있는 해시에 저장

   - 특정 해시 값 주변 버킷이 모두 채워져 있는 primary clustring 문제에 취약

 

최초 해시 값이 52이고 고정폭이 1일 경우 4번에탐색 과정을 거쳐야 함.

 

📝 chining은 해시 테이블의 크기를 유연하게 만들고, open addressing은 해시 테이블 크기는 고정시키되 저장해 둘위치를 잘 찾는데 관심을 둔 구조

 

 

  2) 제곱탐색(Quadratic Probing) : 해시 충돌 발생 시 제곱만큼 건너 뛰어 데이터를 삽입하는 방식

 충돌이일어난 해시의 제곱을 한 해시에 데이터를 저장

(1^2칸 -. 2^2칸 -. 3^2칸...)

여러개의 서로 다른키들이 동일한초기 해시값(아래에서 initial probe)를 갖는 secondary clustering에 취약

초기 해시 값이 같으면 동일한 폭으로 탐색하기 때문에 효율성이 떨어짐

 

  3) 이중해싱(Double Hashing) : 해시 충돌 시 다른 해시 함수를 한번 더 적용시킴.

다른 해시함수를 한번 더 적용해 나온 해시에 데이터를 저장

이중 해싱을 하면최초 해시값이 달라지므로 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시 값이 달라져 primary, secondary clustering을 완화할 수 있음

장점 - 또 다른 저장공간 없이 해시 테이블 내에서 데이터의 저장 및 처리가 가능

단점 - 해시함수의 성능에 따라 해시 테이블의 성능이 좌우된다.

      - 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해두어야 한다.

 

 

💡 결과 

Hash 는 탐색이 빠른 배열의 장점과 삽입/ 삭제 시 데이터의 밀어내기 이동이 필요없는 장점을이용해 성능을 향상시킨 데이터 저장 방법이다.

분리 연결법은 배열과 단순연결리스트를 혼합하여 데이터의 삽입/삭제/탐색의 성능을 높인다.

개방 주소법은 배열만을 사용하며, 저장 인덱스가 겹칠경우해당 인덱스의옆인덱스에 저장하는 방식이다ㅏ.이때 옆 인덱스와의 데이터 충돌이또다시 일어나면 다시 옆인덱스로 저장한다. 따라서 충돌 데이터가 많이 발생하면 성능에 심각한 문제가 발생하는 단점이있다.

 

 

💡 JAVA에서의 hash

HashMap과 HashTable

HashTable이란 JDK 1.0부터 있던 Java의 API이고, hashMap은 Java 2에서 처음 선보인 JavaCollections Framework에 속한 API이다.

HashTable 또한 Map 인터페이스를 구현하고 있기 때문에 HashMap과 HashTable이 제공하는 기능은 같다.

 

차이점

1. 보조 해시 함수

HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수잇어 상대적으로 성능상 이점이 있다.

2. 동기화

HashMap의 경우 동기화를 지원하지 않는다. 그래서 Hashtable은 동기화 처리라는 비용 때문에 HashMap에 비해 더 느리다고 한다. 프로그래밍 상의편의성 때문에 멀티쓰레드 환경에서도 Hashtable을 쓰기보다는 hashMap을 다시 감싸서

Map m = Collections.synchronizedMap(new HashMap(...)); 

과 같은 형태가 최근에는 더 선호한다.

 

💡 HashMap 살펴보기

1) 해시 충돌 기법

Java HashMap에서 사용하는 방식은 Separate Channing이다. Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기때문이다.

게다가 HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로많아지면 일반적으로 Open Addressing은 Separate Chaining 보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaning 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다.

 

2) 연결 리스트와 트리

위에서 체이닝 방식은 보통 연결 리스트를 사용해 value들을연결한다고 했다 HashMap또한 연결리스트를 사용하였지만 Java8부터 버킷의 데이터가 일정 개수 이상일 때는 연결리스트 대신 트리(Red-Black tree)를 사용한다고 한다.

이렇게 트리를 사용하는 ㄳ으로 변경후 기존 get()메서드 호출에 대한 기댓값

에서

으로 성능이 향상되었다.

하나의 해시 버킷에 8개 이상의 키-값 쌍이 모이면링크드리스트를 트리로 변경한다. 그리고 6개에이르게되면 다시 링크드리스트로 변경한다. 트리는 링크드 리스트보다 메모리 사용량이 많고 데이터의 개수가 적을 때 트리와 링크드리스트의 WorstCase 수행시간 차이비교는 의미가 없기 때문이다.

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

 

💡 해시 버킷 동적 확장

아까 해시 테이블의 크기를 메모리의 효율성을 위해서 기본적으로 전체키의 크기보다 작게 만든다고 했다. 하지만 이로 인해 해시 충돌이 발생하고 성능상 손실이 발생한다.

그래서 HashMap은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 수를 두배로 늘린다. 해시 버킷의 수를 늘려 해시 충돌의 확률을 줄이는 것이다.

 

해시 버킷 개수의 기본값은 16이고, 버킷의 최대 개수는 230개다. 그런데 이렇게 버킷 개수가 두배로 증가할 때마다, 모든 키-값데이터를 읽어 새로운 Separate Chaining을 구성해야하는 문제가 있다.

HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 잇으므로, 해당 HashMap 객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면 불필요하게 Separate Chaining을 재구성하지 않게 할 수 있다.

 

resize를 하게 되면 새 해시 버킷을 생성한 다음, 기존 모든 해시 버킷을 순회하면서 각 해시 버킷에 있는 링크드리스트를 순회하며 key-value쌍을 저장한다. 이때 해시 버킷개수가 변경되었기 때문에 index값(hashCode % M)을 다시 계산해야 한다.

 

그런데 이렇게 해시 버킷 크기를 두 배로 확장하는 것에는 결정적인 문제가 있다. 해시 버킷의 개수 M이 2a 형태가 되기 때문에, index = X.hashCode() % M을 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 된다는 것이다. 즉 해시 함수가32비트 영역을 고르게 사용하도록만들었다 하더라도 해시값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 잇다.

이때문에 보조 해시 함수가 필요하다.

 

 

💡 보조 해시 함수

보조 해시 함수의 목적은 key의 해시값을 변경해 해시 충돌 가능성을 줄이는 것이다.

//java 8 보조 해시 함수
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }  

Java 8 HashMap 보조 해시 함수는 상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수로 변경되었다.

이유로는 두가지가 있는데, 첫번째는Java 8에서는 해시 충돌이 많이 발생하면 링크드리스트 대신 트리를 사용하므로 해시 충돌 시 발생할 수있는 성능 문제가 완화되었기 때문이다. 두번째로는 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, Java 7 까지 사용했던 보조 해시 함수의 효과가 크지 않기 때문이다. 두번째 이유가 좀 더 결정적인 원인이 되어 Java8에서는 보조 해시 함수의 구현을 바꾸엇다.

 

💡 Hashing in Java

- Java의 Object 클래스는 hashCode() 메서드를 가진다. 따라서 모든클래스는 hashCode()메서드를 상속받는다. 

- 이 메서드는 하나의 32비트 정수를 반환한다.

- 32비트정수라는 것은 음수일 수도 있다는 이야기이다.

- 만약 x.equals(y)이면 x.hashCode() == y.hashCode() 이다. 하지만 역은 성립하지 않는다.

- Object 클래스의 hashCode() 메서드는 객체의 메모리 주소를 반환하는 것으로알려져 있다.

  (but it's implementation-dependent.)

- 필요에 따라 각 클래스마다 이 메서드를 override하여 사용한다.

  (예) Integer 클래스는 정수값을 hashCode로 사용

 

💡 해시함수의 예 : hashCode() for String in Java

public final class String{
	private final char[] s;
    ...
    public int hashCode(){
    	int hash = 0;
        for (int i = 0 ; i < length() ; i++)
        hash = s[i] + (31 * hash);
        
        return hash;
    }
}

 

💡 사용자 정의 클래스의 예

- 모든 멤버들을 사용하여 hashCode를 생성한다.

public class Record{
	private String name;
    private int id;
    private double value;
    ...
    public int hashCode(){
    	int hash = 17; //nonzero constant
        hash = 31 * hash + name.hachCode();
        hash = 31 * hash + Integer.valueOf(id).hashCode();
        hash = 31 * hash + Double.valueOf(value).hashCode();
        
        return hash;
    }
}

💡 hashCode와 hash 함수

 - hash code : -2^31에서 2^31사이의 정수

 - hash 함수 : 0에서 M-1까지의 정수(배열인덱스)

    * 0x7fffffff을 &연산하는 이유는 음수일 경우 양수로 바꿔주는 작업이다.

    * 나머지 연산의 피연산자가양수여야 하기 때문이다.

private int hash(Key key){
	return (key.hashCode() & 0x7fffffff) % M;
}

 

💡 HashMap in Java

- TreeMap클래스와 유사한 인터페이스를 제공(둘 다 java.util.Map 인터페이스를 구현)

- 내부적으로 하나의 배열을 해시 테이블로 사용

- 해시 함수는 24페이지의 것과 유사함

- chaining으로 충돌 해결

- Load factor를 지정할 수 있음(0~1사이의 실수)

- 저장된 키의 개수가 load factor를 초과하면 더 큰 배열을 할당하고 저장된 키를 재배치(re-hashing)

 

💡 HashSet in Java

HashSet<MyKey> set = new HashSet<MyKey>();
set.add(MyKey);
if (set.contains(theKey))
...
int k = set.size();
set.remove(theKey);
Iterator<MyKey> it = set.iterator();
while(it.hasNext()){
	MyKey key = it.next();
    if(Key.equals(aKey)
    	it.remove()
}

 

 

▼ 참고 블로그

velog.io/@kkw9312/javaHash

velog.io/@adam2/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94

 

ict-nroo.tistory.com/77