해쉬(Hash) 자료구조 알아보기

🤔 해시(Hash) 란?

• 해시란 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 매핑한 값을 말한다.
• 해시 알고리즘을 이용해 고유한 인덱스를 얻는다.
• 인덱스를 이용하여 빠른 검색 속도와 빠른 저장 속도를 갖는다.

[해시 함수]

• 데이터를 효율적으로 관리하기 위해, 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다.
• 해시 함수에 의해 얻어지는 값을 해시 코드, 해시 라고 한다.
• 이 해시 값은 원본 데이터를 대표하며, 일반적으로 해시 테이블에 저장된다.

• 해시 함수의 입력 값이 조금만 바뀌어도 결과는 크게 달라지기 때문에 암호학에서 무결성을 검사할 때(Message Digest)에도 사용된다.

[해시 테이블]

• 키와 값을 매핑해둔 데이터 구조이다.
• 해시 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장한다.
• 동기화를 지원한다.
• key, value에 null 을 허용하지 않는다.

[HashTable vs HashMap]

	HashTable	HashMap
속도	상대적으로 느리다.	상대적으로 빠르다.
동기화 지원	O	X
key, value null 허용 여부	허용 x	허용 o

😭 충돌(Collision)

• 해시값은 결국 함수를 통해 생성되는 것이므로 입력값이 같으면 결과 해시값도 같다.
• 또한, 입력값은 무한하므로 반드시 겹치는 해시 값이 생긴다.

  짤막한 이야기 - 비둘기집의 원리

😤 충돌 해결 방법

[Separate Chaining]

• key에 대한 index(bucket index)가 가리키는 자료구조를 LinkedList 를 이용하는 방식이다.
• index로 인해서 충돌이 발생하면 그 index가 가리키고 있는 LinkedList 에 노드를 추가한다.
• 이 방법은 데이터를 검색할 때, 선형 탐색을 하기 때문에 느리다는 단점이 있다.
  • O(n)
  • LinkedList 대신 트리를 이용하면 성능을 개선시킬 수 있다. (O(log n))

JDK 1.8 의 경우 index에 노드가 8개 이하인 경우에는 LinkedList를 사용하고 8개를 넘어갈 경우에는 트리 구조로 데이터 저장 구조를 바꾸도록 설계되어 있다.

[Open Addressing]

• 해시 충돌이 발생하면 해시 함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장하는 방식이다.

• 선형 탐사(Linear Probing)
  • 현재 주소에서 고정 크기만큼 다음 주소로 이동하여 데이터를 저장한다.
• 제곱 탐사(Quadratic Probing)
  • 이동 크기가 제곱수로 늘어나는 방식이다.
  • ex. 1, 4, 9, 16…

• 이중 해싱(Double Hashing)
  • 해시 충돌 시 다른 해시 함수를 한번 더 적용하는 방식이다.
• 재해싱(Rehashing)
  • 해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 모든 데이터를 다시 해싱하는 방식이다.

[Open Addressing의 문제점]

• 삭제 처리 시에 문제가 발생할 수 있다.
  • 데이터 A를 저장하고 데이터 B를 저장할 때 충돌(A와 같은 해시값이 나옴)이 발생하여 다른 곳에 저장했다고 가정하자.
  • 이때, 데이터 A가 삭제되는 경우, A가 있던 index에 데이터가 존재하지 않는다.
  • 데이터 B를 조회하면 먼저 A가 있던 자리에 데이터가 있는지 확인하고 데이터가 없다면 삭제 연산은 해당 데이터를 찾을 수 없다고 판단하게 된다.
• 이러한 문제점을 해결하기 위해 데이터를 삭제한 후에 더미 노드를 삽입한다.
• 더미 노드는 데이터를 가지지는 않지만, 검색 시 다음 index까지 연결하는 역할을 한다.

누군가가 물어본다면

해시는 다양한 길이를 가진 데이터를 해시 함수를 통해 고정된 길이의 데이터로 매핑한 값을 말합니다.
인덱스를 이용하여 빠른 검색 속도와 저장 속도를 가집니다.

하지만 중복된 인덱스를 가지게 되는 충돌이 발생할 수 있어 이를 해결하기 위한 방법을 고민해야합니다.