https://school.programmers.co.kr/learn/courses/30/lessons/1845?language=java
import java.util.HashMap;
class Solution {
public int solution(int[] nums) {
int length = nums.length;
int maxCount = length / 2;
HashMap<Integer, Integer> pocketmons = new HashMap<>();
for(int i = 0; i < length; i++) {
pocketmons.put(nums[i], 1);
}
int answer = pocketmons.size() > maxCount ? maxCount : pocketmons.size();
return answer;
}
}
HashMap을 이용하면, key값이 중복되지 않기 때문에 이를 이용하였다.
nums[i]를 키 값으로 하여 HashMap에 넣고, 마지막에는 그 size()를 구하여 maxCount 보다 클 경우에는 maxCount를 최대포켓몬 수로 정하고, 반대일 경우에는 size() 값을 최대포켓몬 수로 정하였다.
HashMap
은 hashCode
를 이용하기 때문에 대용량 데이터를 조회하는데 유용하다.
여기서 hashCode
란 해시 알고리즘에 의해 생성된 정수 값이다.
HashMap
은 key
값을 통해 hashCode
(정수)를 생성하고, 생성된 hashCode
를 bucket
에 접근할 수 index
로 변환해 배열에 값을 저장한다. 즉, 하나하나 확인을 하는 것이 아니라, key
값을 hashCode
로 변환하고 해당 값을 index
로 변환해 바로 탐색하는 것이다. 그렇기 때문에 대용량 데이터에서 조회가 빠르다.
하지만, hashCode
를 만드는 알고리즘이 좋지 않으면, 만든 hashCode
가 같아질 수 밖에 없기 때문에 배열의 한 방에 많은 데이터가 들어가게 된다. 이런 현상을 충돌현상이라고 하는데, 이것을 피하기 위해 Hash Algorithm
을 잘 만들어야 한다.
만약 아래처럼 구현한다면 이 클래스로 생성된 모든 객체들은 다 똑같은 해시코드를 갖는 것이기 때문에 충돌현상이 생겨 문제가 될 것이다.
@Override
public int hashCode() {
return 1; // 모든 객체들이 해시코드를 1을 갖게 됩니다.
}
원래는 배열의 인덱스를 조회하는 것이기 때문에 시간복잡도가 O(1)
이었겠지만, 이런식으로 충돌이 일어나면 탐색하는데 O(n)
까지 걸릴 수가 있다.
위 코드는 극단적인 예시이지만, hashCode
는 다른 Key
값으로 동일한 hashCode
를 만들어 내기도 하는데, 그 이유는 key
값은 문자열이고 그 가짓수가 무한한데 비해 hashCode
는 정수이기 때문에 알고리즘이 아무리 좋아도 어떤 Key
들은 중복되는 hashCode
를 만들어낼 수 밖에 없기 때문이다.
또는, 다른 hashCode
를 받았지만 Index
로 변환하는 과정에서 동일한 Index
를 받는 경우에도, 한 Index
에 값이 몰리기 때문에 충돌이 일어나서 O(n)
까지 걸릴 수가 있다.
HashMap
에서 데이터를 담는 공간을 bucket
이라고 칭한다. 자바에서 해당 bucket
의 크기는 동적으로 변경된다.
HashMap
의 기본 생성자에서 capacity
는 16
, load factor
는 0.75
로 생성되는데, threshold = capacity * load factor
가 된다. 여기서 threshold
는 버킷의 크기를 변경할 때의 임계점이라고 생각하면 된다.
즉, threshold
는 16 * 0.75 = 12
가 되는데, 이 말은 버킷안에 저장된 데이터가 12개
가 넘어가면 bucket
의 크기를 늘린다는 이야기이다. HashMap
은 버킷의 크기를 늘릴 때 2배
를 늘린다. 즉, 원래사이즈 16의 2배인 32개
가 되는 것이다. 따라서 데이터가 많아지면 메모리를 많이 사용하게 된다.
사이즈가 변경되는 과정을 rehashing
이라고 하는데, 해당 과정에서 사이즈만 변경되는 것이 아니라 해시코드를 다시 계산하여 해당 키-값들의 버킷 위치를 다시 정하게 된다.