Map
Key-Value로Key-Value로 데이터를 저장하는 ADT(추상 자료형)
key는 중복될 수 없다.
Associative Array, Dictionary라고 불리기도 한다.
Hash Table(Hash Map)
배열과 해시 함수(hash function)를 사용하여 Map을 구현한 자료 구조
(일반적으로) 상수 시간으로 데이터에 접근하기 때문에 매우 빠르다.
Hash Function
임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수
(hash table에서)임의의 데이터를 정수로 변환하는 함수
예를 들어) "김철수" 라는 이름을 hash function을 거치면 20030이 나온다. 이렇게 해시를 통해"김철수"라는 이름이 중복되지 않게 유지한다.
hash table은 어떻게 동작하는가?
- 키 입력: 데이터를 저장할 때, 키와 값을 함께 해시 테이블에 전달한다.
- 해시 함수: 해시 함수는 전달받은 키를 입력으로 받아 해시 값을 계산한다.
- "사과"라는 키를 해시 함수에 넣으면 10이라는 해시 값이 나올 수 있다.
- 인덱스 계산: 해시 값은 해시 테이블의 크기에 따라 조정되어 실제 저장 위치(인덱스)로 변환된다.
- 해시 테이블의 크기가 100이라면, 해시 값 10은 그대로 인덱스 10으로 사용될 수 있다.
- 데이터 저장: 계산된 인덱스에 키와 값의 쌍이 저장된다.
Hash Collision(해시 충돌)
- Key는 다른데 hash가 같을 때
- key도 hash도 다른데 hash % map_capa 결과가 같을 때
해시충동을 피할 수 없지만 충돌이 최대한 없게 만들어야 한다.
Hash Collision 해결 방법
- Open Addressing
- Separate Chaining
Separate Chaining(분리 연결법)
각 해시 테이블의 슬롯(bucket)은 LinkedList의 헤더 역할을 합니다. 즉, 각 슬롯은 해당 해시 값으로 해싱되는 모든 키-값 쌍의 목록을 저장하는 연결 리스트의 시작점을 가리킵니다.
Open Addressiong
선형 탐색은 충돌이 발생한 후, 해당 인덱스에서부터 차례대로 하나씩 다음 슬롯을 확인해 가며 빈자리를 찾는 방식입니다.
ex) index 1에 데이터가 있다면 다음 인덱스가 비었다면 index 2에 데이터를 저장한다.
Hash Table의 Capacity는 2의 거듭제곱으로 늘어난다.
- 비트 AND 연산을 통한 빠른 인덱스 계산
- 균등한 분포
- 메모리 관리 효율성
- 효율적인 크기 조정
비트 AND 연산을 통한 빠른 인덱스 계산
빠른 인덱스 계산 (비트 마스크): capacity가 2의 거듭제곱(예: 2^n) 일 경우, 모듈러 연산을 비트 AND 연산으로 대체할 수 있습니다. 비트 AND 연산은 모듈러 연산보다 훨씬 빠릅니다.
- 예를 들어,
capacity가 16(2^4)인 경우,hashValue % 16은hashValue & 15와 같습니다. 여기서 15는 이진수로1111입니다. - 일반적인 모듈러 연산은 나눗셈 연산을 포함하지만, 비트 AND 연산은 단순히 비트 단위의 AND 연산만 수행하면 되므로 훨씬 빠릅니다. 균등한 분포
- Hash Table* 은 Hash Function을 통해서 해시 값을 추출하고 추출된 Hash값을 Hash Teble의 Capacity로 "%" 모듈러 연산(이론적으로는)을 한다. 그렇게 나온 값을 Hash Table의 index로 사용하는 것이 일반적입니다.
그래서 2의 거듭제곱일 경우 실제로 내부적으로 모듈러연산 => 비트연산으로 대체하여 성능을 최적화합니다.
메모리 관린 효율성
컴퓨터 시스템은 메모리를 2의 거듭제곱 단위로 할당하는 경우가 많습니다. 따라서, 해시 테이블의 용량을 2의 거듭제곱으로 관리하면 메모리 할당 및 관리가 더욱 효율적일 수 있습니다.
효율적인 크기 조정
해시 테이블의 데이터 개수가 일정 수준을 넘어서면 성능 유지를 위해 테이블의 크기를 조정해야 합니다. 이때, 용량을 2배로 늘리는 것이 일반적(Java에서는)인데, 2의 거듭제곱으로 관리하면 크기 조정이 비교적 간단하고 효율적으로 이루어질 수 있습니다. 새로운 용량으로 모든 데이터를 다시 해싱해야 하지만, 2의 거듭제곱을 유지하면 비트 연산을 활용하여 효율성을 높일 수 있습니다.
