Hash알고리즘

🚗해쉬 / 해쉬 함수

-해쉬란 저장할 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것입니다.

배열에서 데이터가 저장될 때를 보자면,

위와 같이 오름차순으로 정렬된 11개의 크기를 가진 배열이 있습니다.
만일 , 6이란 값을 추가되면 어떻게 될까요??

위와 같이 8이 있던 위치에 6이란 값을 넣고, 나머지 데이터를 뒤로 밀어넣습니다.

데이터가 많으면 많아질수록 , 시간 복잡도와 비용은 증가합니다.

반면에 해시를 이용할 경우를 예시로 들자면,
원래의 값을 이용하여 해시 값을 얻어와서 인덱스로 사용합니다.

배열의 크기가 똑같이 11이라고 가정하고 , 저장할 데이터를 11로 나누어 보자면

위와 같이 구해진 hash값을 인덱스로 이용하여 값을 저장합니다.
그리고 결과는 아래와 같습니다.

여기서 7이란 값을 추가할 경우 , 11로 나뉘어진 나머지 값인 7의 위치에 값을 추가만 해주면 되기에, 데이터의 이동이 적어진다는 장점이 있습니다. 또한 이러한 테이블을 해시 테이블이라고 합니다.

이렇게 키값을 가지고 해시 값을 만드는 과정을 해시 함수,
그리고 각 요소를 버킷이라고 합니다.

🚗 충돌

하지만 문제가 있습니다.
11이란 값이 있고 , 21이란 값이 있습니다.
이를 데이터의 크기 혹은 지정한 방식으로 해시값을 얻어와서 사용할 때,

10으로 나눈다고 가정하겠습니다.
둘 다 모두 1이란 나머지 값을 가지게 되고 같은 인덱스를 사용하여 저장되기에 충돌이 발생합니다.

그래서 해시 함수는 가능하면 해시 함수는 가능하면 해시 값이 치우지지 않도록 고르게 분포된 값을 만들어야 합니다.

🚗 대처

Chaining 기법

• 데이터를 쇠사슬 모양으로 연결 리스트에서 연결하는 방법으로
  오픈 해시법이라고도 합니다.

  

(사진 출저 : 자료구조와 함꼐 배우는 알고리즘 입문)

위와 같이 같은 해시 값을 가지는 데이터들을 연결 리스트로 사슬처럼 연결합니다.

그로 인해 , 최초의 위치를 탐색하는 해쉬 과정을 제외하고 나면,
탐색, 삽입 , 삭제 과정은 연결리스트와 유사한 방식을 취하며 , 그 특징을 가지고 갑니다.

그로 인해 , 삽입과 삭제에서는 빠를 수 있으나 탐색에서 취약합니다.

오픈 주소법

• 충돌이 발생했을 때 재해시를 수행하여 비어 있는 버킷을 찾아내는 방법으로 닫힌 해시법이라고도 합니다.

즉 예를 들어 , 13이란 값을 10으로 나누니 3이란 해시값을 얻어왔습니다.
3이란 인덱스 위치를 보니 값이 있습니다. 그래서 기존의 해시값에 1을 추가하여 다시 10으로 나누어 4라는 인덱스 위치에 값을 추가하는 방식이라고 보시면 됩니다.

하지만 , 진짜 해시값이 4인 데이터가 추가될 경우 또 다른 버킷에 저장되어야 한다는 단점이 존재합니다.

🚗Hash를 이용하는 자료구조

• 자바에서는 hashCode()를 이용하여 배열에 넣습니다.
  이 때 32비트 크기 정수형으로 모든 해시 값을 담기에는 부족하므로 배열 크기로 나눈 나머지 값을 사용합니다.

• 충돌 방지로 Separating Chaining , Open addressing을 사용합니다.

  HashTable

  • 해시 테이블을 구현
  • 동기화를 지원합니다.
  • key에 null을 허용하지 않습니다.

  HashMap

  • 해시 테이블을 구현
  • 동기화를 지원하지 않습니다.
  • Key에 null을 허용합니다.
  • 보조 해시를 사용하여 HashTable에 비해 상대적으로 충돌이 적습니다.

  HashSet

  • HashMap을 사용해서 값을 저장합니다.
    따라서 , Hash알고리즘을 사용해서 값을 검색하고 ,
    존재한다면 값을 추가하지 않습니다.