문제
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() 값을 최대포켓몬 수로 정하였다.
해시
hashCode
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)까지 걸릴 수가 있다.
bucket
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 이라고 하는데, 해당 과정에서 사이즈만 변경되는 것이 아니라 해시코드를 다시 계산하여 해당 키-값들의 버킷 위치를 다시 정하게 된다.
