티스토리 뷰
해시 (Hash)
해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행됩니다! 아주 빠르게 진행될 수 있는 이유는 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 됩니다.
해시 함수, 해시 알고리즘, 해시코드?
데이터의 key값을 배열의 인덱스인 정수로 변환하기 위해서는 일련의 과정이 필요합니다. 예를들어 데이터를 문자열로 받게 되었을 때 문자 한글자 한글자의 아스키 코드 값을 더하는 과정으로 문자열을 정수 값으로 변환할 수 있습니다.
(만약, hello 라는 문자열을 정수형 key 값으로 바꾼다면, h + e + l + l + o -> 104 +101 + 108 + 108 + 111 = 532라는 해시코드로 변환 할 수 있습니다.)
앞서 말씀드린 예제 이외에도 여러가지 방법으로 데이터를 해시코드로 바꾸기 위한 과정을 진행하게 되는데, 주어진 문제마다 적절한 해시 함수(해시 알고리즘)을 구현하는 것은 개발자의 역량에 달려있습니다.
해시코드를 사용해서 해시 테이블(배열)에 저장하기
해시코드로 나올 수 있는 숫자의 경우의 수는 아주 많습니다. 저장할 배열의 크기는 물리적 한계가 있고 수 많은 해시코드들을 대처 할 수 없습니다. 이런 경우 해시코드를 배열의 크기로 나누고, 그 나머지를 인덱스로 사용하게 되면 0부터 배열의 사이즈-1 만큼의 숫자로 변환하여 사용 할 수 있습니다. 예를들어 해쉬코드가 532이고 배열의 크기가 10인 경우 나머지가 2가 나오고, 이 나머지 값을 인덱스로 사용합니다.
충돌(collision)
하지만 위와 같이 인덱스를 한정된 인덱스로 바꾸게 된다면 다른 해시코드라도 같은 인덱스가 나올 수 있는 경우가 생길 수 있습니다. (혹은 완전히 같은 해시코드가 나올 수도 있습니다.) 이런 경우 충돌(collision)이 발생했다고 하는데, 이 충돌을 어떤식으로 해결하는지 여러가지 방법이 있습니다. 이 포스팅에서는 분리 체인법을 설명하도록 하겠습니다. (다른 방법들로는 선형 탐사, 2차 탐사, 이중해싱등이 있습니다.)
+ 이러한 이유로 자바에서 hashCode()를 오버라이딩 할 때 단짝처럼 equals()도 오버라이딩 해야합니다. 별개의 객체가 우연히 해시코드가 똑같이 나오게 되더라도, equals()로 값의 동등성을 한번 더 확인 하는 과정을 거치게 되면 충돌을 방지 할 수 있습니다.
충돌 해결하기 - 분리 체인법
같은 인덱스를 가지는 데이터가 여러개인 경우, 그 인덱스의 링크드 리스트 (Linked List)를 선언하고 각 데이터들을 이 리스트에 저장합니다. 이 인덱스의 값을 저장, 검색하는 경우 먼저 인덱스의 접근하고 인덱스에 존재하는 링크드 리스트의 데이터들을 하나씩 조회합니다. 그러므로 한 인덱스의 링크드 리스트의 사이즈가 크게 나오게 되면 해시 함수 (해시 알고리즘)이 주어진 문제에 적절하지 않은 경우이므로 설계를 다시 고려해봐야 합니다.
'Algorithm' 카테고리의 다른 글
| 프로그래머스 알고리즘 - 위장 (0) | 2019.01.14 |
|---|---|
| 프로그래머스 알고리즘 - 완주하지 못한 선수 (0) | 2019.01.13 |
| 백준 알고리즘 - 케빈 베이컨의 6단계 법칙 (1389번) (0) | 2019.01.10 |
| 프로그래머스 알고리즘 - 단어변환 (0) | 2019.01.04 |
| 순열(permutation) 알고리즘 (2) | 2019.01.03 |