'레드블랙트리' 태그의 글 목록

HashMap - HashTable과 다르게 쓰레드 동기화를 하지 않음(single-thread에서 유용) - 기본적으로 해쉬값을 반환하는 해쉬함스로써 hashCode()를 사용함 - hashCode()의 반환형은 int임 - int는 32비트(4Byte)이고 2^32개로 완벽한 해쉬값을 만들 수 없음(표현해야 할 key가 2^32개 보다 많을 경우) - HashMap은 O(1)을 보장하기 위해 random access가 가능하게 하려면 HashMap의 크기는 2^32개 여야 함 - 그래서 보통 2^32보다 작은 숫자 M을 이용해 해쉬값을 다음과 같이 다시 정의함 (int index = X.hashCode() % M) - 여기서 M은 2의 지수승 형태임. 즉, M이 2^a 형태라면 hashCode()의 ..