Map & Hash table

• 해시 테이블은 키-값 쌍을 효율적으로 저장하고 검색하기 위한 자료구조이다.
• 데이터를 저장할 때 키를 해시 함수에 입력하여 해시 값을 생성하고, 이 값을 이용해 배열(버킷 배열)의 특정 위치에 데이터를 저장한다.
• 자바의 HashMap과 같은 자료구조가 이에 해당한다.

 

동작 방식

1. 키를 해시 함수에 입력: 해시 함수는 주어진 키를 입력으로 받아, 고정된 크기의 해시 값을 생성한다. 이 해시 값은 보통 정수 형태이다.
2. 해시 값의 인덱스 계산: 생성된 해시 값에 배열의 크기(해시 테이블의 크기, capacity)를 나누는 모듈러 연산(%)을 수행하여 인덱스를 계산한다. 이 인덱스는 데이터가 저장될 배열의 위치를 결정한다.
3. 데이터 저장: 계산된 인덱스에 키와 값을 함께 저장한다. 해시 테이블은 일반적으로 (key, hash, value) 쌍으로 데이터를 저장한다. 해시를 함께 저장하는 이유는 리사이징시에 재연산을 피하기 위함이다.

 

해시 충돌 (Hash Collision)

서로 다른 키들이 해시 함수에 의해 동일한 해시 값을 생성할 때 발생하는 문제를 해시 충돌이라고 한다. 해시 충돌은 다음 두 가지 경우에서 발생할 수 있다.

• 키는 다르지만 해시 값이 동일한 경우: 해시 함수가 두 개의 다른 키에 대해 동일한 해시 값을 생성할 때.
• 키와 해시 값이 다르지만, 모듈러 연산 후 인덱스가 동일한 경우: 해시 함수가 서로 다른 해시 값을 생성했지만, 배열 크기에 대한 모듈러 연산 결과가 동일할 때.

 

해시 충돌 해결 방법

Separate Chaining (분리 연결법)

각 배열 인덱스가 연결 리스트를 가리키도록 하여, 동일한 인덱스에 여러 개의 키-값 쌍을 저장할 수 있도록 한다.

• 동작 방식:
  1. 해시 충돌이 발생하면, 해당 인덱스에 이미 존재하는 연결 리스트에 새로운 키-값 쌍을 추가한다.
  2. 탐색 시에는 해당 인덱스의 연결 리스트를 순회하여 원하는 키를 찾는다.
• 장점: 테이블의 크기와 상관없이 충돌을 효과적으로 처리할 수 있으며, 테이블이 꽉 차지 않는 한 성능이 저하되지 않는다.
• 단점: 연결 리스트를 사용하므로, 메모리 오버헤드가 발생할 수 있다.

Open Addressing (개방 주소법)

충돌이 발생했을 때, 다른 빈 슬롯을 찾아 데이터를 저장하는 방법이다. 배열 내의 빈 공간을 활용하여 충돌을 해결한다.

3가지 방식이 존재한다.

• 종류
  • Linear Probing (선형 탐사): 충돌이 발생하면, 일정한 간격(보통 1씩 증가)으로 다음 인덱스를 확인하며 빈 슬롯을 찾는다.
  • Quadratic Probing (제곱 탐사): 충돌이 발생하면, 제곱 간격(1, 4, 9,...)으로 다음 인덱스를 확인하며 빈 슬롯을 찾는다.
  • Double Hashing (이중 해싱): 충돌이 발생하면, 첫 번째 해시 함수에 이어 두 번째 해시 함수를 사용해 새로운 해시 값을 계산한 후, 해당 인덱스에 빈 슬롯이 있는지 확인한다.
• 동작 방식
  • 탐색 과정: containsKey() 실행 시 초기 인덱스를 계산한 후, 해당 인덱스부터 시작해 다음 인덱스를 차례로 확인한다.
  • 데이터 삭제: 데이터 삭제시에 더미 데이터를 넣어 이전에 값이 있었음을 표시한다. 찾고자 하는 데이터가 다른 인덱스에 존재할 수 있음을 나타내기 위해 더미 데이터를 넣는다.
• 장점: Separate Chaining에 비해 메모리 효율이 높으며, 모든 데이터가 동일한 배열 내에 저장되므로 메모리 접근 패턴이 더 효율적일 수 있다.
• 단점: 테이블이 가득 차기 시작하면 충돌이 많아져 성능이 저하될 수 있다. 탐색 및 삽입 시 충돌 처리로 인해 시간이 소요될 수 있다.

 

객체를 HashMap의 키로 쓴다면 어떻게 동작할까?

• 객체의 메모리 주소를 입력으로 해시를 생성한다.
  • 자바에서 HashMap은 기본적으로 객체의 hashCode() 메서드를 사용하여 해시값을 생성한다. hashCode() 메서드를 재정의하지 않으면, 기본적으로 객체의 메모리 주소를 기반으로 해시값이 생성된다.
• 같은 값을 가진 객체라도 해시값이 다를 수 있다.
  • 두 객체가 동일한 값을 가지고 있어도, hashCode() 메서드를 재정의하지 않으면, 메모리 주소가 다르기 때문에 해시값도 다르게 나온다. 따라서, 같은 내용을 가진 객체라도 서로 다른 해시값을 가지게 된다.
• 해시 충돌이 발생하여 객체를 비교할 때, 기본적으로 메모리 주소를 비교한다.
  • 해시 충돌이 발생하면, HashMap은 equals() 메서드를 사용해 키 객체들을 비교한다. equals() 메서드를 재정의하지 않았다면, 기본적으로 메모리 주소를 비교하게 되므로, 동일한 값을 가진 다른 객체는 다른 객체로 판단된다.
• 이 동작 방식은 HashSet에서도 동일하다.
  • HashSet은 내부적으로 HashMap을 사용하여 동작하므로, 키 객체의 해시값을 계산하고 비교하는 방식이 동일하다. 따라서, HashSet에서도 같은 값을 가진 객체들이 서로 다른 해시값을 가지며, 다른 객체로 인식된다.
• 만약 hashCode()와 equals() 메서드가 객체의 멤버 변수를 기반으로 구현되어 있다면, 다음과 같은 문제가 발생할 수 있다.
  • 객체가 HashMap에 처음 저장될 때, 객체의 hashCode()를 계산하여 해당 해시값에 대응하는 버킷에 객체를 저장한다.
  • 저장된 객체의 멤버 변수를 변경하면, hashCode()의 결과가 달라질 수 있다. 이로 인해, HashMap이 객체를 저장할 때 사용했던 해시값과 현재 객체의 해시값이 다르게 된다.
  • 만약 HashMap에서 해당 객체를 키로 사용해 검색하거나 제거하려고 하면, HashMap은 새로운 hashCode()를 기준으로 해시값을 계산한다. 하지만 객체는 여전히 기존 해시값을 사용하여 저장된 상태이므로, HashMap은 해당 객체를 찾지 못할 수 있다.