y-log

용어 정리

Hash 자료구조란

key와 value를 갖는 자료구조로 효율적인 검색과 저장을 위해 사용된다. 

linked list와 달리 해당 자료가 위치한 버킷의 주소값을 바로 알아내어 찾아갈 수 있다.

시간 복잡도가 O(1)에 수렴하게 된다.

Hash 함수, Hash 알고리즘, Hash 코드

임의의 길이의 데이터를 고정 길이의 데이터로 매핑하는 함수

비둘기집 원리에 의해 해시함수의 결과값이 중복 되어 해시 충돌을 야기할 수 있다.

* 비둘기집 원리 : n+1개의 물건을 n개의 상자에 넣을 때, 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리

데이터의 value값을 배열의 인덱스인 정수로 변환하기 위해서는 일련의 과정이 필요하다.

예를들어 데이터를 문자열로 받게 되었을 때 문자 한글자 한글자의 아스키 코드 값을 더하는 과정으로 문자열을 정수 값으로 변환할 수 있습니다. 

만약, 
hello 라는 문자열을 정수형 key 값으로 바꾼다면,
h + e + l + l + o -> 104 +101 + 108 + 108 + 111 = 532라는
해시코드로 변환할 수 있다.

여러가지 방법으로 데이터를 해시코드로 바꾸기 위한 과정을 진행하게 되는데, 주어진 문제마다 적절한 해시 함수(해시 알고리즘)을 구현하는 것은 개발자의 역량에 달려있다.

Hash 코드를 사용해서 Hash table에 저장하기

해시코드로 나올 수 있는 숫자의 경우의 수는 아주 많다. 저장할 배열의 크기는 물리적 한계가 있고 수 많은 해시코드들을 대처 할 수 없다.

이런 경우 해시코드를 배열의 크기로 나누고, 그 나머지를 인덱스로 사용하게 되면 0부터 배열의 사이즈-1 만큼의 숫자로 변환하여 사용 할 수 있다.

예를들어 해쉬코드가 532이고 배열의 크기가 10인 경우 나머지가 2가 나오고, 이 나머지 값을 인덱스로 사용한다.

* 각 버킷은 몇 개의 슬롯으로 구성되어 있다.

OverFlow란 

여러개의 키값이 공통된 버킷을 가리키는 경우, 버킷들의 공간은 유한해서 결국 버킷이 꽉 차게 된다.

꽉 차있는 순간 또하나의 키값이 해당 버킷에 맵핑된다면 오버플로우가 발생한다.

충돌 Collision

다른 해시코드임에도 같은 인덱스가 나오는 경우가 발생할 수 있다.

이런 경우 충돌이 발생했다고 하는데 충돌의 해결방식은 여러가지가 있다. 

분리 체인법, 선형 탐사법, 2차 탐사법, 이중 해싱 등이 존재한다.

* 이러한 이유로 자바에서 hashCode( )를 오버라이딩 할 때 equals( )도 오버라이딩 해야한다. 별개의 객체가 우연히 해시코드가 똑같이 나오게 되더라도 equals로 값의 동등성을 한번 더 확인하는 과정을 거치게 되면 충돌을 방지할 수 있다.

충돌 해결하기

1. 분리 체인법 seperate chaning (open hashing)

같은 인덱스를 가지는 데이터가 여러개인 경우, 그 인덱스의 Linked List를 선언하고 각 데이터들을 이 리스트에 저장한다.

이 인덱스의 값을 저장, 검색하는 경우 먼저 인덱스의 접근하고 인덱스에 존재하는 링크드 리스트의 데이터들을 하나씩 조회합니다.

한 인덱스의 링크드 리스트의 사이즈가 크게 나오게 되면 해시 함수 (해시 알고리즘)이 주어진 문제에 적절하지 않은 경우이므로 설계를 다시 고려해봐야 한다. 

* 충돌이 발생하면 주어진 해시테이블 공간외의 새로운 공간을 할당해주기 때문에 open hashing이라고도 불린다.

2. Open Addressing (Closed Hashing)

주어진 해시테이블에서 정해진 규칙에 따라 버킷을 찾아 저장하는 방법이다. open addressing의 버킷 결정 방법에는 몇가지가 있다.

2.1 선형 조사

충돌이 일어난 다음 자리에 저장하는 방법

제 1 군집 현상이 발생한다

* 제 1 군집 현상 : 특정 영역에 데이터가 몰릴 때, linked list의 순차 탐색으로 데이터의 저장공간이 지정되어 성능이 치명적으로 저하된다. ( 이차원 조사로 해결 가능하다)

2.2 이차원 조사

충돌이 발생한 경우 다음 데이터의 자리를 이차함수로 결정한다.

2.3 더블 해싱

2.4 무작위 처리 방법

<참고>

https://siyoon210.tistory.com/85 https://galid1.tistory.com/171