[PerformancePattern] ArrayMap vs HashMap

HashMap

Key값의 hashCode를 index로 Array에 값을 저장함.

기본적으로 배열이 커야 충돌확률이 줄어들기때문에 큰 배열을 사용한다.

따라서 검색 속도는 O(1)로 매우 빠르다.

(hash값이 겹칠 경우 chaining등의 방법을 이용한다.)

ArrayMap

두 개의 배열을 이용한다.

1번 배열에는 HashCode를 순서대로 저장한다.

2번 배열에는 Key/Value를 순서대로 저장한다.

값을 가져올 때는 1번 배열을 HashCode로 이진탐색하여 2번 배열의 index를 구한다.

2번 배열의 index 다음 값을 가져온다.(hashIndex * 2, hashIndex * 2 + 1)

검색속도는 O(logN) 이다.

요약: 

HashMap은 속도는 빠르지만 메모리를 많이 먹는다. 

ArrayMap은 속도는 조금 느리지만 메모리를 조금 먹는다.

ArrayMap은 저장할 값이 1000개 이하일 때만 써라

동영상 링크:

 https://www.youtube.com/watch?v=I16lz26WyzQ&index=20&list=PLOU2XLYxmsIKEOXh5TwZEv89aofHzNCiu