HashMap 에 대해 공부해보자

ideal dev·2023년 6월 22일

기술면접

목록 보기

2/3

해시

Key와 Value를 이용해 값을 저장하는 형태
데이터의 효율적인 관리를 목적으로 사용

사용예시

// java입니당
HashMap<Integer, String> hm = new HashMap<>();
hm.put(1,"hi"); // hm.put(key,value);

여기서 Key는 1, Value는 hi가 된다.
그럼 어떻게 저장되길래 효율적인걸까?🧐

해시함수

해시에는 해시함수란 기능이 있는데,
해시함수는 key를 넣으면, 미리 약속해둔 길이로 변환시켜주는 기능을 한다.

John Smith 를 넣으면 -> 02 로 변환시켜준다
key를 넣으면 -> hash Value로 변환시켜준다
key : 매핑전 값
hash Value : 매핑후 값
hashing : ->, 매핑하는 과정

그럼, 위 이미지처럼 만드려면, Key 값을 아래와 똑같이 넣어주면 된다.

HashMap<String, Integer> hm = new HashMap<>();
hm.put("John Smith",01011112222); 
hm.put("Lisa Smith",01022223333); 
hm.put("Sam Doe",01033334444); 
hm.put("Sandra Dee",01044445555);

그럼, 뒤의 저 전화번호는 어디 저장되는걸까? 바로바로!

해시 테이블

key를 hash value로 매핑하고 hash value를 인덱스 삼아서, 저장하고자 하는 value를 저장하는 자료구조
이를 통해 해시맵은 O(1)의 시간복잡도로 접근이 가능해진다!
- 해시맵을 사용하게 되면, key가 hash value 로 변환 -> hash value를 통해 바로 value에 접근

근데, 위 이미지에서 John Smith와 Sandra Dee가 똑같이 02 라는 키로 변경되는 걸 볼 수 있다.
이럼 충돌이 일어나는 거 아닌가!?

해시 충돌

Hash Value가 겹쳐서 같은 버킷에 저장하려고 할 때 발생
해결 방법
- Separate Chaining(분리 연결법) 내자리에 누가 있네!? 뒤에 연결해서 넣지 뭐 ㅎㅎ
  해시 충돌 시 추가적인 메모리를 사용해 LinkedList or Tree 를 이용해서 해결하는 방법
  +) 자바 8 이상에서는 데이터의 사이즈가 커지면 Tree를 사용
- Open Addressing(개방 주소법) 내자리에 누가 있네!? 다음 칸에 저장하지 뭐 ㅎㅎ
- Linear Probing(선형 탐사)
  - 한칸씩 뒤로 이동하며 빈자리에 넣음
  - 특정 해시 값 주변 버킷이 모두 채워져 있는 primary clustering에 취약
- Quadratic Probing(제곱 탐사)
  - 제곱칸씩 뒤로 이동하며 빈자리에 넣음
  - 여러 개의 서로 다른 키들이 동일한 초기 해시값을 갖는 secondary clustering에 취약
- Double Hashing(이중 해싱)
  - 3가지 중 캐시 효율이 가장 좋지 않고, 많은 연산량을 요구
  - 해싱함수를 한 번 더 사용해서 나온 hash value값에 넣음.