해시맵의 구조와 특징
가볍게 생각하면 해시맵은 python에서 dictionary와 같이 key와 value 값을 매핑된 상태로 저장할 수 있는 자료구조라고 생각할 수 있습니다.
그러나 가볍게 대충 보면 안되겠죠?
우선 기본적으로 자바에서 해시맵(HashMap)은 인터페이스 Map을 상속받고, Map은 key와 value으로 구성된 객체를 저장하는 구조를 가지고 있습니다.
따라서 상속받은 해시맵도 Map의 성질을 그대로 가져 key와 value값으로 구성된 객체를 저장하기 편한 자료구조입니다.
이때 null key와 null value를 허용한다고 합니다.
아주 조금 더 깊게 생각해봅시다.
이름에 있는 hash는 보통 hash function(해쉬함수)와 연관이 있다고 생각하시면 되는데요!
key값을 해쉬함수에 넣어 그 출력값인 HashCode가 나오는데 이것은 저장하는 장소(버킷)의 인덱스와 연관이 있습니다.
이것은 저장위치를 해쉬함수를 통해 바로 알 수 있기 때문에 특히 검색이 빠르다는 것, 시간복잡도가 작다는 것을 알 수 있습니다. 하지만 key값을 해쉬함수에 넣었기 때문에 key값을 검색하는데만 빠릅니다. 또한 HashMap은 key값을 통해서만 검색이 가능한것도 동일한 이유입니다.
-> 또한 이것은 해시테이블(Hash Table)이라고 합니다. Hash Table이란? 이 게시물에 다시 정리해놨습니다!
여기서 해쉬함수는 보통 보안에서도 연관이 있는데요! 간단한 개념만 짚고 넘어갈게요
해쉬함수는 다음과 같은 특징을 갖고 있습니다.
1. 어떠한 입력값에도 항상 고정된 길이의 해시값을 출력합니다.
2. 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력합니다.
3. 출력된 결과값을 통해 입력값을 유추할 수 없다.
해시맵의 관련 메서드 와 시간복잡도
| 메서드 | 기능 | 시간복잡도 |
| put(key, value) | HashMap에 key,value 삽입 삽입하는 순서는 따로 저장되지 않음 |
O(1) |
| containsKey(key) | HashMap에 해당 key가 있는지 확인 있으면 true, 없으면 false 반환 |
O(1) |
| containsValue(value) | HashMap에 해당 value가 있는지 확인 있으면 true, 없으면 false 반환 |
O(n) |
| get(key) | HashMap에 저장된 key를 입력하면 value값을 반환함 | O(1) |
| remove(key) | 특정 key와 value를 삭제함, 삭제하면서 value값을 반환함 |
replace() 등 여러 메서드가 있습니다.
remove()메서드의 시간복잡도는 찾지 못하겠습니다. 혹시 아시는 분 있으면 댓글로 공유 부탁드려요!
HashMap의 사용
코드
public class HashMapStudy {
public static void main(String[] args) {
HashMap<String, String> h1 = new HashMap<String, String>();
HashMap<String, String> h2 = new HashMap<String, String>();
h1.put("aaa", "1111");
h1.put("bbb", "2222");
h1.put("ccc", "3333");
h1.putIfAbsent("aaa", "0000");
h1.putIfAbsent("ddd", "4444");
h2.putAll(h1);
System.out.println("h1 : " + h1);
System.out.println("h2 : " + h2);
System.out.println("[1]: " + h1.containsKey("aaa"));
System.out.println("[2]: " + h1.containsValue("1111"));
System.out.println("[3]: " + h1.isEmpty());
System.out.println("[4]: " + h1.size());
System.out.println("[5]: " + h1);
System.out.println("[6]: " + h1.remove("aaa", "1111"));
System.out.println("[7]: " + h1.put("bbb", "0000"));
System.out.println("[8]: " + h1.replace("ccc", "0000"));
System.out.println("h1 : " + h1);
System.out.println("h2 : " + h2);
for (String key: h1.keySet()) {
String value = h1.get(key);
System.out.println("Key:" + key + ", Value:" + value);
}
}
}출력결과
h1 : {aaa=1111, ccc=3333, bbb=2222, ddd=4444}
h2 : {aaa=1111, ccc=3333, bbb=2222, ddd=4444}
[1]: true
[2]: true
[3]: false
[4]: 4
[5]: {aaa=1111, ccc=3333, bbb=2222, ddd=4444}
[6]: true
[7]: 2222
[8]: 3333
h1 : {ccc=0000, bbb=0000, ddd=4444}
h2 : {aaa=1111, ccc=3333, bbb=2222, ddd=4444}
Key:ccc, Value:0000
Key:bbb, Value:0000
Key:ddd, Value:4444참고할 만한 문제 :
https://www.acmicpc.net/problem/26008
https://school.programmers.co.kr/learn/courses/30/lessons/42578
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
해시맵의 구조와 특징
가볍게 생각하면 해시맵은 python에서 dictionary와 같이 key와 value 값을 매핑된 상태로 저장할 수 있는 자료구조라고 생각할 수 있습니다.
그러나 가볍게 대충 보면 안되겠죠?
우선 기본적으로 자바에서 해시맵(HashMap)은 인터페이스 Map을 상속받고, Map은 key와 value으로 구성된 객체를 저장하는 구조를 가지고 있습니다.
따라서 상속받은 해시맵도 Map의 성질을 그대로 가져 key와 value값으로 구성된 객체를 저장하기 편한 자료구조입니다.
이때 null key와 null value를 허용한다고 합니다.
아주 조금 더 깊게 생각해봅시다.
이름에 있는 hash는 보통 hash function(해쉬함수)와 연관이 있다고 생각하시면 되는데요!
key값을 해쉬함수에 넣어 그 출력값인 HashCode가 나오는데 이것은 저장하는 장소(버킷)의 인덱스와 연관이 있습니다.
이것은 저장위치를 해쉬함수를 통해 바로 알 수 있기 때문에 특히 검색이 빠르다는 것, 시간복잡도가 작다는 것을 알 수 있습니다. 하지만 key값을 해쉬함수에 넣었기 때문에 key값을 검색하는데만 빠릅니다. 또한 HashMap은 key값을 통해서만 검색이 가능한것도 동일한 이유입니다.
-> 또한 이것은 해시테이블(Hash Table)이라고 합니다. Hash Table이란? 이 게시물에 다시 정리해놨습니다!
여기서 해쉬함수는 보통 보안에서도 연관이 있는데요! 간단한 개념만 짚고 넘어갈게요
해쉬함수는 다음과 같은 특징을 갖고 있습니다.
1. 어떠한 입력값에도 항상 고정된 길이의 해시값을 출력합니다.
2. 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력합니다.
3. 출력된 결과값을 통해 입력값을 유추할 수 없다.
해시맵의 관련 메서드 와 시간복잡도
| 메서드 | 기능 | 시간복잡도 |
| put(key, value) | HashMap에 key,value 삽입 삽입하는 순서는 따로 저장되지 않음 |
O(1) |
| containsKey(key) | HashMap에 해당 key가 있는지 확인 있으면 true, 없으면 false 반환 |
O(1) |
| containsValue(value) | HashMap에 해당 value가 있는지 확인 있으면 true, 없으면 false 반환 |
O(n) |
| get(key) | HashMap에 저장된 key를 입력하면 value값을 반환함 | O(1) |
| remove(key) | 특정 key와 value를 삭제함, 삭제하면서 value값을 반환함 |
replace() 등 여러 메서드가 있습니다.
remove()메서드의 시간복잡도는 찾지 못하겠습니다. 혹시 아시는 분 있으면 댓글로 공유 부탁드려요!
HashMap의 사용
코드
public class HashMapStudy {
public static void main(String[] args) {
HashMap<String, String> h1 = new HashMap<String, String>();
HashMap<String, String> h2 = new HashMap<String, String>();
h1.put("aaa", "1111");
h1.put("bbb", "2222");
h1.put("ccc", "3333");
h1.putIfAbsent("aaa", "0000");
h1.putIfAbsent("ddd", "4444");
h2.putAll(h1);
System.out.println("h1 : " + h1);
System.out.println("h2 : " + h2);
System.out.println("[1]: " + h1.containsKey("aaa"));
System.out.println("[2]: " + h1.containsValue("1111"));
System.out.println("[3]: " + h1.isEmpty());
System.out.println("[4]: " + h1.size());
System.out.println("[5]: " + h1);
System.out.println("[6]: " + h1.remove("aaa", "1111"));
System.out.println("[7]: " + h1.put("bbb", "0000"));
System.out.println("[8]: " + h1.replace("ccc", "0000"));
System.out.println("h1 : " + h1);
System.out.println("h2 : " + h2);
for (String key: h1.keySet()) {
String value = h1.get(key);
System.out.println("Key:" + key + ", Value:" + value);
}
}
}출력결과
h1 : {aaa=1111, ccc=3333, bbb=2222, ddd=4444}
h2 : {aaa=1111, ccc=3333, bbb=2222, ddd=4444}
[1]: true
[2]: true
[3]: false
[4]: 4
[5]: {aaa=1111, ccc=3333, bbb=2222, ddd=4444}
[6]: true
[7]: 2222
[8]: 3333
h1 : {ccc=0000, bbb=0000, ddd=4444}
h2 : {aaa=1111, ccc=3333, bbb=2222, ddd=4444}
Key:ccc, Value:0000
Key:bbb, Value:0000
Key:ddd, Value:4444참고할 만한 문제 :
https://www.acmicpc.net/problem/26008
https://school.programmers.co.kr/learn/courses/30/lessons/42578
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
