[묘공단] 코딩 테스트 합격자 되기 4주차

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다.

 

해시

- 해시는 해시 함수를 사용하여 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 이다

- 해시는 키를 이용해서 데이터 탐색에서 빠르다는 장점이 있다

 

 

특징

 

- 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 없다

- 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색 할 수 있다

- O(1)으로 동작

- 값을 적절하게 변환해야 인덱스로 사용 가능

 

 

 

해시 함수

 

우선 해시 함수를 구현할 때 고려할 사항

 

1. 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안된다

2. 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다

-> 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미

 

 

나눗셈법

 

- 키를 소수로 나눈 나머지를 활용한다

수식 -> h(x) = x mod k (x 는 키 , k 는 소수)

# 소수를 사용하는 이유

- 해시 값의 충돌을 줄이기 위해

- 해시 테이블의 크기가 k로 고정된다

 

단점은 매우 큰 소수를 구하는 효율적인 방법이 없어서 필요한 경우 기계적인 방법으로 구해야 한다

 

 

 

곱셈법

 

- 나눗셈과 비슷하게 모듈러 연산활용

- 소수 사용은 안한다

수식 -> h(x)=(((x∗A) mod 1)∗m)  (m은 해시테이블 크기, A는 황금비 0.6183)

 

- 수식 처럼 키에 황금비를 곱해서 소수 부분을 취해 m을 곱하여 정수부분만 취한 값으로 매핑한다

 

 

지금까지 숫자로만 했지만 키의 자료형이 문자열일 때에 대해서 알아 보겠습니다

 

 

 

문자열 해싱 

 

- 문자열의 값을 숫자로 변환하고, 이것을 다항식의 값으로 변환

hash(s)=(s[0]+s[1]∗p+s[2]∗p2+...+s[n−1]pn−1)mod m

 

p는 31, m 은 해시 테이블 최대 크기이다

-> p를 31로 정한 이유는 홀수이면서 메르센 소수이기 때문

 

- 문자열이 길 수록, 함수 값이 필요한 해시테이블에 비해서 매우 커져서 오버플로우가 발생할 가능성 있음

 

 

충돌 처리

- 서로 다른 키에 대해서 해시 함수의 결과값이 같으면 collsion(충돌) 이라고 한다

- 해시 테이블을 관리할 때는 반드시 충돌 처리를 해야 한다

 

 

1) 체이닝 처리

• 충돌이 발생하면 해당 버킷리스트에 링크드 리스트로 같은 해시값을 가지는 데이터를 연결
• 단점
  - 해시테이블 공간 활용성 저하
  - 검색 성능 저하 : N개의 링크드리스트 검색은 O(N)

 

2) 개방주소법

• 빈 버킷을 찾아 충돌한 값 저장
• 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용한다

① 선형 탐사 방식

• 충돌이 발생하면, 다른 빈 버킷을 찾아 일정한 간격으로 이동 (보통 1씩 이동)
  h(k,i)=(h(k)+i)mod m

② 이중 해싱 방식

• 해시함수 2개 사용
• 두번째 해시함수는, 첫번째 해시함수에서 충돌이 발생하면 해당 해시값을 기준으로 위치를 결정
  h(k,i)=(h1​(k)+i∗h2​(k))mod m
• 클러스터를 줄이기 위해 m을 제곱수나 소수로 사용

 

해시맵

- 해시맵을 위한 HashTable 클래스와 HashMap 클래스가 있다

두 클래스는 유사하지만 HashTable 클래스는 자바의 초기 버전과 호환성을 위해 남겨두었을 뿐 최근에는 잘 사용되지 않는다

 

구분	정의	설명
연산	valueType put (keyType key , valueType value)	해시맵에 데이터를 저장
	valueType get (keyType key)	key값에 대한 value 값 반환
	valueType remove (keyType key)	key에 해당하는 데이터 삭제
	boolean contains (keyType key)	key가 있다면 true, 없으면 false 반환
	void clear()	모든 데이터 삭제
상태	int isEmpty()	해시맵이 비어있는지 비어있다면 true, 데이터가 있ㅇ으면 false 반환
	int size()	데이터 갯수 반환

 

 

 

 

 

 

출처

 

https://goldenrabbit.co.kr/product/javapass/

[되기] 코딩 테스트 합격자 되기(자바 편) - 골든래빗