SQLP를 공부하며 Hash algorithm에 대한 이해를 기본 바탕으로 알고 있어야 공부를 하기 쉬웠었고,
그러한 Hash algorithm을 쉽고, 꼼꼼하게 설명해보고자 글을 작성하였다.
# Hash algorithm은 무엇인가?
Hash 알고리즘은 데이터들을 메모리에 저장할 때 메모리의 어느위치에 저장할지, 데이터의 저장위치를 지정할 때 사용되는
기법이며 오라클 내부에서 데이터 저장이나, 처리시 수행되는 여러 프로세스나, 기법에서 사용이 되고있다.
그리고 오라클에서 Hash algorithm이 사용되는 여러 프로세스나 기법은 아래와 같다.
1. Library cache라는 메모리 영역에 SQL커서(SQL 실행계획, 쿼리가 담겨있는 정보단위)를 저장할 때
2. 디스크에 있는 데이터를 Data buffer cache라는 메모리 영역에 올려서 저장할 때
3. 스칼라서브쿼리를 사용할 때, 메인쿼리와 서버쿼리의 값이 오라클의 UGA라는 메모리 영역에 데이터가 저장될 때
4. HASH 조인 수행 시 유저 프로세스의 PGA영역이라는 메모리 공간에 선행테이블( first table )로 HASH 테이블을 만들때
# Hash algorithm을 사용한 데이터가 메모리에 저장되는 과정
Hash algorithm을 사용해서 메모리에 데이터가 저장되는 프로세스는 아래와 같다
1. Hash 알고리즘에는 알고리즘에 사용될 특정함수가 존재한다. 이런 함수는 프로그램 개발자가 개발하거나
아니면 원래 존재했던 함수이다. 위 예시에서는 mod 함수이며 mod 함수는 특정상수를 입력값으로 나누었을 때
출력값은 나눈결과의 나머지인 함수이다.
--------------------------------------------------------------------------------------------------------
ex) mod 9 함수 : 입력값에 대해 출력값은 입력값을 9로 나누었을때 나머지가 되는 함수
입력값 : 10 출력값 : 1
입력값 : 11 출력값 : 2
입력값 : 12 출력값 : 3
입력값 : 8 출력값 : 8
입력값 : 1 출력값 : 1
--------------------------------------------------------------------------------------------------------
2. 여러 데이터들이 메모리에 저장될 위치를 찾기위해 Hash 알고리즘에 입력이 되면
입력되는 각 데이터들은 ( 위 그림에서 노란색 동그라미 )들은 hash함수를 거쳐 출력값이 발생하고, 발생한 출력값들은
하나의 hash bucket으로 생성이 되며 hash bucket에 연결지정된 메모리 위치에 입력값들이 저장된다.
hash bucket : ( 위 그림에서 흰색동그라미 )
3. 만약 다른 여러 입력값들이 hash 함수를 거쳤을 때 출력값들이
- 동일한 hash bucket값을 갖는다면, 앞서 먼저 저장되었던 메모리 공간에 덮어씌워 저장하지 않고
hash collision(해시충돌)을 일으키며 앞선 데이터의 메모리공간 뒤에 포인터(메모리 주소값을 가르키는 화살표)로
연결되어 저장되며, 이를 hash chain이라 한다. ( 위 그림에서 마지막에 나타나는 빨간색 테두리 )
- 동일한 값이 또 입력되면 당연히 동일한 출력값과 동일한 hash bucket 값을 갖지만, 이때는 동일한 값을 메모리에
따로 저장하지 않는다. 그냥 해당값( 동일한 중복값 )을 저장하지 않는다.
4. 해시함수에 입력되는 값 ( 위 그림에서 노란색 동그라미 )의 종류가 많다면,
그만큼 hash collision(해시충돌)이 일어날 가능성이 커진다.
해시충돌이 발생하면, 데이터를 저장해야할 공간을 hash chain을 따라 탐색해야 하기 때문에
탐색 작업을 하는 만큼 CPU사용률이 올라가게 된다. 따라서 hash 알고리즘을 사용할 때는
해시함수에 입력되는 입력값의 종류를 작게 하여, 해시충돌이 적게 일어나게 해야 한다.
입력값의 종류가 많다면 동일한 hash bucket값을 가진 값이 많을 가능성이 커지기 때문에 해시충돌이
일어날 가능성이 커진다. 해당 내용에 대해 예시를 들자면 아래와 같다.
ex) hash 함수 = 성씨의 자음 함수 : 입력값에 대해 출력값은 입력값의 첫번째 글자의 자음
hash bucket = ㄱ, ㄴ, ㄷ, ㄹ, ㅁ, ㅂ, ㅅ, ㅇ, ㅈ, ㅋ, ㅌ, ㅍ , ㅎ, ㅃ, ㅉ, ㄸ, ㄲ (= 발생할수 있는 출력값의 종류)
경우1)
입력데이터 : 김민주, 김민주, 이주동, 오희철, 주상도, 이주동, 주상도 ( 7개 Data, 동명이인 3명 있음 )
입력데이터의 종류 : 김민주, 이주동, 오희철, 주상도 ( 4개 )
생성되는 해시버켓 : ㄱ, ㅇ, ㅈ ( 3개 )
해시충돌 횟수 : 1번
경우2)
입력데이터 : 김설, 지상두, 김호근, 양수진, 이대성, 강상준, 우상철 ( 7개 Data )
입력데이터의 종류 : 김설, 지상두, 김호근, 양수진, 이대성, 강상준, 우상철 ( 7개 )
생성되는 해시버켓 : ㄱ, ㅇ, ㅈ ( 3개 )
해시충돌 횟수 : 4번
댓글