해시(Hash)

해시란

해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행되는 방법이다. 아주 빠르게 진행될 수 있는 이유는 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 됩니다. (인덱스마다 바로 데이터를 찾을 수 있다는 얘기)

 

• 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것
• 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 자료구조이다.
• 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이때 사용하는 함수(알고리즘)를 해시함수 라고 한다
• 해시값 자체를 index로 사용하기 때문에 평군 시간복잡도가 O(1) 로 수렴한다. (검색과 저장이 아주 빠르게 진행되는 방법이다. )
• 저장장치에 데이터를 저장하는 방법 중에는 해시 함수의 결과를 배열 인덱스로 활용하는 방법이 있는데 이런 배열을 해시 테이블(hash table)이라고 한다.

 

해시 함수, 해시 알고리즘, 해시코드? 

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

즉, 일반적인 개념은 검색에 사용할 키에 대해 이들을 균일하게 뿌려주는 해시 함수를 적용하는 것이다.

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

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

 

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

 

 

해시코드를 사용해서 해시 테이블(배열)에 저장하기

해시코드로 나올 수 있는 숫자의 경우의 수는 아주 많습니다. 저장할 배열의 크기는 물리적 한계가 있고 수 많은 해시코드들을 대처 할 수 없습니다. 이런 경우 해시코드를 배열의 크기로 나누고, 그 나머지를 인덱스로 사용하게 되면 0부터 배열의 사이즈-1 만큼의 숫자로 변환하여 사용 할 수 있습니다. 예를들어 해쉬코드가 532이고 배열의 크기가 10인 경우 나머지가 2가 나오고, 이 나머지 값을 인덱스로 사용합니다.

 

ex) 월 ~ 금 요일에 생년월일을 5로 나눈 나머지를 저장하는 해시 함수

 

충돌(collision)

하지만 위와 같이 인덱스를 한정된 인덱스로 바꾸게 된다면 다른 해시코드라도 같은 인덱스가 나올 수 있는 경우가 생길 수 있습니다. (혹은 완전히 같은 해시코드가 나올 수도 있습니다.) 이런 경우 충돌(collision)이 발생했다고 하는데, 이 충돌을 어떤식으로 해결하는지 여러가지 방법이 있습니다. 이 포스팅에서는 분리 체인법을 설명하도록 하겠습니다. (다른 방법들로는 선형 탐사, 2차 탐사, 이중해싱등이 있습니다.)

 

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

 

충돌 해결하기 - 분리 체인법

같은 인덱스를 가지는 데이터가 여러개인 경우, 그 인덱스의 링크드 리스트 (Linked List)를 선언하고 각 데이터들을 이 리스트에 저장합니다. 이 인덱스의 값을 저장, 검색하는 경우 먼저 인덱스의 접근하고 인덱스에 존재하는 링크드 리스트의 데이터들을 하나씩 조회합니다. 그러므로 한 인덱스의 링크드 리스트의 사이즈가 크게 나오게 되면 해시 함수 (해시 알고리즘)이 주어진 문제에 적절하지 않은 경우이므로 설계를 다시 고려해봐야 합니다. 

즉, 체인이 길어질수록 검색 시간이 느려집니다.

따라서 삽입정렬로 체인에 원소를 넣을 수도 있는데

이경우 삽입에 시간이 더 걸리지만 어떤 원소가 체인에 들어 있는지 여부를 결정하기 위해 체인을 다 뒤질 필요는 없어 진다.

그 외 해시 충돌을 처리하는 다른 방법도 있다.

 

효율성과 성능

성능과 효율이 분리된 상황을 응용하는 방법으로 데이터베이스 샤딩(sharding)이 있다.

샤딩은 다른말로 수평 파티셔닝(horizontal partitioning)이라고도 부른다.

샤딩은 데이터베이스를 각각 다른 기계에서 실행되는 여러 샤드로 나누는 방식을 말한다.

(인덱스의 크기를 줄이고, 작업 동시성을 늘리기 위한 것이다.)

 

인터페이스를 통해 요청이 들어온 데이터 베이스 연산을 모든 샤드에 전달한다.

그리고 컨트롤러가 결과를 하나로 모은다. 이 기법을 사용하면 작업을 여러 작업자로 나눠(동시에 병렬적으로) 수행할 수 있기 때문에 성능이 향상된다.

 

단점 - 프로그래밍 운영적인 복잡도가 더 높아진다.

 

 

자료 출처

https://siyoon210.tistory.com/85

https://power-overwhelming.tistory.com/42