해시맵(HashMap)

---

<해시맵 노트 정리>

---

해시맵이란?

해시맵이란, 해싱(키 값을 특정한 연산을 거쳐 나온 결과를 이용하여 값에 접근하는 과정)을 거쳐 값을 저장하는 맵(map, 키-값의 한 쌍으로 이루어진 값들로 이루어진 자료구조) 형태의 자료구조이다.

해시 충돌

경우에 따라서, 여러 개의 키 값이 해시 함수를 거쳤을 때 해시 값이 같아질 때가 있다. 이를 해시 충돌이라고 하며, 이를 해결하지 않을 경우 데이터에 문제가 발생할 수 있다. 해결하는 방법은 크게 개방 주소법, 분리 연결법 두 가지로 나뉜다.

개방 주소법

충돌 발생 시 새로운 비어있는 해시 값을 찾아 저장한다. 이에 해당하는 방법으로는 선형 탐사법, 제곱 탐사법, 이중 해싱이 있다.

• 선형 탐사법 - 충돌 발생 지점 이후의 빈 공간을 순서대로 탐사(하나하나)
• 제곱 탐사법 - 충돌 발생 지점 이후의 빈 공간을 제곱의 간격을 두고 탐사
• 이중 해싱 - 두 개의 해시 함수를 이용하는 방법(최초 값을 구하기 위한 첫번째 해시 함수, 충돌이 발생하는 경우 이동 간격을 구하기 위한 두번째 해시 함수)

분리 연결법

충돌 발생 시 개방 주소법과는 다르게 저장할 다른 위치를 탐색하지 않고, 연결 리스트를 이용하여 연속적으로 값들을 연결한다.

---

JAVA에서의 해시맵 사용 예시

import java.util.HashMap;
// 순서대로 키의 클래스, 값의 클래스
// HashMap<K, V> hashMap = new HashMap<>()

주요 메소드(HashMap)

출처

메소드	타입	설명
containsKey(Object key)	boolean	해당 key값을 가지고 있는 경우 true 반환
containsValue(Object value)	boolean	해당 value값을 가지고 있는 경우 true 반환
get(Object key)	V	key값에 대응하는 value값을 반환. 없을 경우 null 반환
put(K key, V value)	V	key 값에 대응하는 value를 해시맵에 삽입
remove(Object key)	V	해당 key 값에 대응하는 value가 존재하는 경우 해시맵에서 삭제
replace(K key, V value)	V	해당 key 값에 대응하는 원래 value를 주어진 value로 변경

예시 코드

// 정수형의 key, 문자열의 value를 가지는 HashMap
HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(1, "apple");
hashMap.put(2, "banana");
hashMap.put(3, "melon");
  
System.out.println(hashMap.containsKey(1));			// true
System.out.println(hashMap.containsValue("peach"));	// false

System.out.println(hashMap.get(1));					// "apple"
System.out.println(hashMap.get(4));					// null
hashMap.put(4, "berry");
hashMap.replace(3, "kiwi");							// "melon" -> "kiwi"

System.out.println(hashMap);	// {1:apple, 2:banana, 3:kiwi, 4:berry}
hashMap.remove(4);
System.out.println(hashMap);	// {1:apple, 2:banana, 3:kiwi}