.png&blockId=3197e115-ee0d-4d9c-9f5d-4b57cb28634e)
핵심MAP은 키와 값 을 쌍으로하여 데이터를 보관하는 자료구조이다.
그 중 HashMap은 이 map 인터페이스를 구현한 map 컬렉션으로, 해싱과정이 포함되어 있다.
해시맵은 평균적으로 탐색,삽입,삭제에 O(1)의 시간복잡도를 가져 널리 사용되는 자료구조이다.
해시충돌은 데이터의 고유한 값인 버킷 값이 다른 데이터와 같은 값을 갖게 되는 경우를 말하며
결과가 고르게 분포되는 좋은 해시함수를 이용하거나, 체이닝, 개방주소법 등 다양한 기술을 이용해서 해시충돌을 줄일 수 있다.
자바8 이후의 HashMap에서는 해시 충돌을 줄이기 위해 보조 해시 함수, Tree 구조를 이용한 separate 체이닝 기법, 해시 버킷 동적 확장 방법을 사용한다.
용어정리
•
HashTable - 해시의 데이터 저장공간
•
HashMethod - 해시테이블의 인덱스로 사용하는 고유한 숫자값을 만들게 사용되는 메서드
•
HashCode - 해쉬메서드에 의해 반환된 데이터의 고유 숫자 값. Java에서는 Object 클래스의 hashCode() 라는 메소드를 이용하여 모든 객체의 HashCode(Heap 영역의 인스턴스에 대한 참조값)를 찾을 수 있음
참고) HashMap(class) vs HashTable(class)
•
hashtable은 컬렉션 프레임웍이 만들어지기 전부터 존재하던 것.
이제는 개선되지 않아, 계속 개선되는 hashmap을 주로 사용
•
같은 환경에서라면 보조 해시 함수를 사용하는 HashMap이 성능상 이점이 있는 것은 맞지만 상황에 따라 HashTable을 사용하는 것이 옳을 수도 있다
HashMap | HashTable | |
Tread-safe | X | O |
Null 값 허용 여부 | O | X |
Enumeration 여부 | X | O (not fail-fast Enumeration) |
보조 해시 함수 여부 | O | X |
HashMap
•
map 인터페이스를 구현한 대표적 Map 컬렉션
•
해싱을 사용함으로써 빠른 탐색과 삽입, 삭제속도를 가짐
리소스 < 속도 : key값이라는 것을 기억할 새로운 메모리 공간이 필요하기 때문에 기존 방법보다 리소스가 많이 든다. 하지만 빠르다.
◦
해싱: key와 value를 매핑 시키는 과정
•
저장공간보다 값이 추가로 들어오면 List처럼 저장공간을 늘리는데, 두배씩 늘림 -> 과부하 문제 잦음 -> Map의 초기 용량을 지정해 주는것이 좋음
•
충돌(collision) 이 일어나면 O(1)이 아닌 O(n)의 굴레에 빠진다.
•
sorting 과 ordering이 힘듬
코드// 선언
HashMap<String,String> map1 = new HashMap<String,String>();//HashMap생성
HashMap<String,String> map2 = new HashMap<>();//new에서 타입 파라미터 생략가능
HashMap<String,String> map3 = new HashMap<>(map1);//map1의 모든 값을 가진 HashMap생성
HashMap<String,String> map4 = new HashMap<>(10);//초기 용량(capacity)지정
HashMap<String,String> map5 = new HashMap<>(10, 0.7f);//초기 capacity,load factor지정
HashMap<String,String> map6 = new HashMap<String,String>(){{//초기값 지정
put("a","b");
}};
// 값 수정
map.put(1,"최수정"); // 추가
map.remove(1); // 값 삭제
map.clear(); // 값 다 삭제
// 출력
System.out.println(map.get(1));
for (Entry<Integer, String> entry : map.entrySet()) { //entrySet() 활용
System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
Iterator<Integer> keys = map.keySet().iterator(); //keySet().iterator() 활용
while(keys.hasNext()){
int key = keys.next();
System.out.println("[Key]:" + key + " [Value]:" + map.get(key));
Java
복사
JAVA와 HashCollision
자바에서 말하는 해시충돌은 실제 해시 범위보다 적은 M만큼의 배열을 선언하여 메모리의 효율을 높였고 해시 값 % M 값을 버킷 값으로 삼아 이것이 충돌하는 것을 뜻한다.
버킷 값이 충돌하면, JAVA 8 버전 이후의 HashMap에서 아래와 같은 방법으로 해결한다.
보조 해시 함수•
key의 해시값을 변경해 해시 충돌 가능성을 줄이는 방법
//java 8 보조 해시 함수
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
Java
복사
LinkedList 를 이용한 체이닝 기법체이닝 기법은
해시 테이블에 연결리스트에서 사용하는 Node 객체를 저장하여, 충돌이 일어나면 이 연결리스트를 이용해 데이터들을 연결하는 방식이다.
•
장점 : 같은 주소 값을 그대로 사용하여 충돌 해결
•
단점 : 특정 주소에 계속 쌓이는 경우 성능이 현저하게 낮아지고 많은 메모리 공간을 잡아먹음
개방주소법 (open Addressing)
해시 충돌이 발생하면 다른 해시 버킷에 해당 자료를 삽입하는 방식
•
장점 : 추가적인 메모리를 요하지 않음. (체이닝이 연결리스트를 추가로 이용하는 것에 비해)
•
단점 : 다른 버킷으로 삽입할 때, 일정한 규칙이 적용되는데 이 규칙을 따르고서 또 충돌이 일어나면 또 이동을 하게 되어, 충돌 데이터가 많이 발생하면 성능에 심각한 문제 발생
•
자바 HashMap에선 체이닝기법을 채택하여 충돌 방지에 사용한다.
트리(Red-Black tree) 를 이용한 체이닝 기법•
기존의 체이닝 기법에서, 링크드 리스트 대신 탐색에 있어 더 높은 효율을 보이는 트리를 접목
•
충돌된 키-값 쌍의 데이터가 8개가 모이면 링크드 리스트를 트리로 변경하고, 6개로 줄면 다시 링크드 리스트로 변경한다.
•
separate Chaining을 활용하여 O(N)의 시간복잡도를 발생시켰지만.
red-black-tree를 활용하여 O(logN)의 시간을 가지고 해결하도록 성능을 향상
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
if (binCount >= TREEIFY_THRESHOLD - 1) // 임계값이 초과할 경우 트리화
treeifyBin(tab, hash);
break;
Java
복사
static
final
int
TREEIFY_THRESHOLD = 8;
static
final
int
UNTREEIFY_THRESHOLD = 6;
if
(binCount >= TREEIFY_THRESHOLD - 1)
// 임계값이 초과할 경우 트리화
treeifyBin(tab, hash);
break
;
해시 버킷 동적 확장•
데이터의 크기에 비해 해시 테이블의 크기가 넉넉치 않으면 해시 충동 가능성이 높아져 성능 손실을 일으킨다.
따라서, 성능 상승을 위해 JAVA HashMap은 Key-value 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 수를 두배로 늘린다.
참고
