HashMap, 로드 팩터

HashMap, 로드 팩터

Map

Map 컬렉션은 Key-Value로 구성된 객체를 저장하는 구조입니다. 키는 중복으로 저장될 수 없고 값은 중복으로 저장될 수 있습니다. 만약 중복된 Key값이 들어온다면 기존의 값은 없어지고 새로운 값으로 대치됩니다.

Map 클래스의 주요 메서드

map.put("key", "value"); // 추가 map.containsKey("key"); // 키가 있는지 확인 map.containsValue("value"); // 밸류가 있는지 확인 map.keySet(); // 모든 키를 Set에 담아 리턴 map.entrySet(); // 모든 Map Entry객체를 Set에 담아 리턴 map.get("key"); // 키값으로 값 반환. map.isEmpty(); // 비어있는지 확인 map.size(); // 객체의 수를 리턴 map.values(); // 모든 밸류 리턴 map.remove("key"); // 해당 키 삭제. map.clear(); // 전체 삭제

HashMap

HashMap은 Map 인터페이스를 구현한 대표적인 Map 컬렉션입니다. HashMap은 이름 그대로 해싱을 사용하고 있기 때문의 많은 양의 데이터를 검색하는데 뛰어난 성능을 보입니다.

HashMap은 저장공간보다 값이 추가로 들어오게 되면 저장공간을 추가로 늘리는데, 한 칸씩 늘리지 않고 약 두배로 늘리게 됩니다. 여기서 과부하가 많이 발생하기 때문에, 초기 용량을 지정해주는 것이 효율적입니다.

HashMap 사용

HashMap map = new HashMap(); HashMap map = new HashMap<>(map1);//map의 모든 값을 가진 HashMap생성 HashMap map = new HashMap<>(10); //초기 용량(capacity)지정 HashMap map5 = new HashMap<>(10, 0.7f);//초기 capacity, load factor지정 map.put("1", "사과"); map.remove(1); map.clear(); System.out.println(map); // 전체 출력 System.out.println(map.get(1)); for (Entry entry : map.entrySet()) { System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue()); } for(Integer i : map.keySet()){ //저장된 key값 확인 System.out.println("[Key]:" + i + " [Value]:" + map.get(i)); } Iterator> entries = map.entrySet().iterator(); while(entries.hasNext()){ Map.Entry entry = entries.next(); System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue()); } Iterator keys = map.keySet().iterator(); while(keys.hasNext()){ int key = keys.next(); System.out.println("[Key]:" + key + " [Value]:" + map.get(key)); }

TreeMap은 이진트리를 기반으로 한 Map컬렉션이며, 키와 값이 저장된 Map, Entry를 저장합니다. TreeMap에 객체를 저장하면 자동으로 정렬이 되는데, 키는 저장과 동시에 자동 오름차순으로 정렬됩니다. 데이터를 저장할 때 즉시 정렬을 하기에 추가나 삭제가 일반적으로 HashMap보다 성능이 떨어집니다. 하지만 정렬된 상태로 Map을 유지하고나 정렬된 데이터를 유지해야 하는 경우 TreeMap을 사용하는 것이 더 유리합니다.

TreeMap map = new TreeMap(); TreeMap map = new TreeMap<>(); TreeMap map = new TreeMap<>(map1); //map의 모든 값을 가진 TreeMap생성 map.put(1, "사과"); map.remove(1); map.clear(); map.get(1); // key: 1의 밸류 반환 System.out.println(map.firstEntry()); // 최소 Entry System.out.println(map.firstKey()); // 최소 key System.out.println(map.lastEntry());// 최대 Entry System.out.println(map.lastKey());// 최대 Ke System.out.println(map); // 전체 출력 for (Entry entry : map.entrySet()) { System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue()); } for(Integer i : map.keySet()){ //저장된 key값 확인 System.out.println("[Key]:" + i + " [Value]:" + map.get(i)); } Iterator> entries = map.entrySet().iterator(); while(entries.hasNext()){ Map.Entry entry = entries.next(); System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue()); } Iterator keys = map.keySet().iterator(); while(keys.hasNext()){ int key = keys.next(); System.out.println("[Key]:" + key + " [Value]:" + map.get(key)); }

Load Factor

로드팩터는 Hash Table내에 얼마나 원소가 차 있는지를 나타내는 수치입니다. 보통 loadFactor의 값은 해쉬 테이블의 크기 / 키 개수로 구할 수 있습니다. 로드 팩터가 1 이하일 경우 Direct Address Table이지만, 1보다 큰 경우에는 해시 충돌이 발생하게 됩니다. 해시 충돌 문제를 해결하기 위한 대표적인 방법으로 해시 테이블의 구조 개선과 해시 함수를 개선하는 방법이 있습니다.

해시 테이블 구조 개선.

1. Chaining

자바 HashMap에서 사용하는 방식입니다. 해시 충돌 문제를 해결하기 위한 간단한 아이디어로 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는 방법입니다. 해당 버킷에 데이터가 이미 존재한다면 노드를 추가해 다음 노드를 가리키는 방식(링크드 리스트)으로 구현하기 때문에 체인이라는 이름이 붙게 되었습니다. 유연 하단 장점을 가지고 있으나 메모리 문제를 야기할 수 있습니다. 자바에서는 데이터 개수가 많아지게 되면 연결 리스트에서 트리로 변경해서 사용하게 됩니다.

2. Open Addressing

Chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블입니다. 해시 함수로 얻은 주소가 아닌 다른 주소에 저장할 수 있도록 허용한다는 취지에서 시작되었습니다. 메모리 문제를 발생하지 않으나 해시 충돌이 발생할 수 있습니다. 해시 충돌 문제가 발생했을 시 특정 해시값에 키가 물리게 되었을 경우 효율성이 크게 떨어지게 됩니다. 해시 충돌 방식은 Probing방식으로 해결할 수 있습니다. Probing은 해시 테이블 내 새로운 주소를 찾는 과정입니다.

Probing의 종류

Linear probing: 버킷에 데이터가 존재한다면 고정 폭(예컨데 1칸)을 옮겨 해당하는 버킷에 액세스 하는 방법

Quadratic Probing: 제곱탐사 말 그대로 1^2, 2^2, 의 방식으로 탐사하는 방식.

Double Hasing: 이중 해싱

해시 함수 개선

해시테이블의 크기가 m이라면 좋은 해시함수는 임의의 키값을 해시값에 매핑할 확률이 1/m이 될 것입니다. 다시 말해 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수입니다.

HashMap - 로드 팩터

HashMap 객체를 선언할 때 별도의 설정을 하지 않으면, capacity=16, loadfactor=0.75의 값을 가지고 bucket이라는 ArrayList가 생성되게 됩니다. capacitry는 bucket의 크기입니다. loadfactor는 (hashMap 데이터의 수 / capacitry)라고 볼 수 있습니다.

데이터가 들어갈 때 다음과 같은 방식으로 index를 구해 해당 버킷에 데이터가 들어가게 됩니다.

int index = key.hashCode % capacity;

해당 버킷에 데이터가 존재한다면 Chaining 방식으로 데이터가 들어가게되며 이후 값을 조회할 때는 첫 번째 공간부터 시작해 해당 key값이 일치할 때까지 equals()로 연결 리스트를 탐색하는 식으로 동작하게 됩니다.

아무리 Chaining으로 해당 버킷에 제한없이 데이터를 넣을 수 있다고 하더라도 버킷의 크기에 비해 데이터의 크기가 많아지게 되면 성능에 문제가 발생할 수 있습니다. 그렇기에 HashMap은 자신의 capacity에 얼마 이상 데이터가 차게 되면 자동으로 버킷의 크기를 늘리게 됩니다. (약 2배) 단순히 버킷의 크기를 늘리는 작업만 하는 것이 아니라 모든 데이터의 hashCode() % capacity 값을 다시 구하고 배치하는 작업을 다시 하게 됩니다. 그렇기 때문에 저장될 데이터의 수가 짐작된다면 HashMap을 생성할 때 그에 맞춰 capacity 값을 설정해 주는 것이 좋습니다.

버킷의 크기를 늘리게되는 시점은 (loadfactor == 저장된 데이터 수 / capacity)입니다. 로드 팩터는 한 공간에 데이터의 수 만약 로드 팩터의 값이 0.75라면 한 공간의 평균 데이터의 수가 0.75개 즉 1개도 안되어서 버킷의 크기를 늘려버린다라고 해석할 수 있습니다.

그렇기 때문에 로드팩터가 작다면 그만큼 capacity가 커져 메모리는 많이 차지하지만, 검색 속도가 빠릅니다. 반대로 로드 팩터가 크다면 그만큼 capacity가 작아져 메모리는 적게 차지하지만 검색 속도가 느리게 됩니다.

공식 문서를 확인해보면 가장 이상적인 로드 팩터는 0.75라고 나와있습니다.

from http://jinukix.tistory.com/68 by ccl(A) rewrite - 2021-10-21 18:26:35