[DataStructure] Map과 Hash Table

Map

• key-value pair들을 저장하는 ADT(Abstract Data Type)이다.
• key는 중복되지 않고 value는 중복될 수 있다.
• associative array, dictionary라고 불리기도 한다.

Hash Table

이미지 출처: https://khalilstemmler.com/img/blog/data-structures/hash-tables/hash-table.png

• Hash Table(해시 테이블)은 Hash function(해시 함수)과 Array을 활용한 Map 자료 구조이며, 모든 데이터에 상수 시간 접근이 가능하다.
• 해시 함수의 역할은 데이터를 고정된 크기의 데이터로 변환하는 것으로, 해시 테이블에서는 데이터를 정수 값으로 변환하는 함수다.
• 해시 함수를 통해 값이 할당된 인덱스에 데이터를 저장하며, 배열의 크기로 모듈러 연산을 통해 인덱스 위치 지정한다.

Hash Collision

• Hash Collision(해시 충돌)은 Key가 다르지만 해시값이 동일할 때 발생하며, 해시테이블의 한계 때문에 피할 수 없는 현상이다.
• 또한, key가 다르고 해시값이 다른 경우에도 모듈러 연산으로 같은 결과가 나와 해시 충돌이 발생할 수 있다.
• 해결 방법으로는 'Open addressing'과 'Seperate chaining'이 있다.

Separate Chaining

• Separate Chaining 방식은 특정 해시값에 대해 체인 형태로 처리하여 충돌을 해결한다.
• 충돌 시 체인 방식 사용해 LinkedList로 관리하며, 리스트 형태로 키-값 연결.
• 여러 개 키에 대한 value 페어를 연결하여 충돌을 해결함.

Open addressing (linear probing)

• Open addressing 방식은 비어 있는 버킷에 데이터를 저장하는데, linear probing 방식으로 다음 비어 있는 공간에 데이터를 저장한다.
• 즉 키를 비교해 충돌 확인 후 다음 공간에 데이터를 저장하는 과정을 거친다.
• 값이 다를 때는 이전 동작을 고민하며, 같은 키를 발견하면 삭제 작업 수행함.
• 키를 삭제할 때는 영구히 지우는 대신 더미 값을 넣어 해당 위치에 데이터 삭제된 사실을 알 수 있도록 함.

Hash Table resizing

• Hash Table resizing은 데이터가 많아지면 테이블 크기를 조정하는 작업이다.
• 예를 들어, 데이터가 테이블의 75%를 차지하면 크기를 2배로 늘려주며 새로운 해시 값을 계산하여 효율적인 작업을 진행한다.
• 해시 값을 배열에 함께 저장하면 Resizing시 연산을 한 번 더 동작하지 않아도 되어 성능을 향상시킬 수 있다.
• Hash Table resizing 시 자바는 2배씩 늘리고, 파이썬은 맞춤 방식을 사용함.

Java의 HashMap과 CPython의 Dictionary

• 자바에서는 HashMap 클래스로 구현되는 반면, 파이썬에서는 'dictionary'로 구현된다.

기능	CPython 딕셔너리	Java HashMap
데이터 구조	체이닝 방식 해시 테이블	체이닝 방식 해시 테이블
데이터 접근/삽입/삭제 시간	보통 모든 데이터를 상수 시간에 접근
해시 충돌 해결 방법	Open addressing	Separate chaining
키 유형	변경 불가능한 객체	hashCode()과 equals() 메서드 구현 객체
null 처리	키, 값 모두 허용	키: 허용하지 않음, 값: 허용
순서	순서 없음	순서 없음 (반복 순서 변화 가능)
스레드 안전성	스레드 안전하지 않음	스레드 안전하지 않음

• 파이썬은 더미 데이터를 감소시키며 해쉬테이블 크기를 줄이는 동작을 한다는데, 이는 유용한 데이터보다 더미 데이터가 많을 때 적용된다.

참고

• https://youtu.be/ZBu_slSH5Sk?si=DzRgGLU2e6cJLGzw