[자료구조/JAVA]HashMap이란?

HashMap

Map는 키와 값으로 구성된 객체를 저장하는 구조를 가지고있는 자료구조다.

HashMap은 Map 인터페이스를 구현한 대표적인 Map 컬렉션이다. Map 인터페이스를 상속하고 있기에 Map의 성질을 그대로 가지고 있다.

null 값과 null 키를 허용 ( HashMap 클래스는 동기화되지 않고 null을 허용한다는 점을 제외하면 Hashtable 과 거의 동일하다)

List 형태를 사용하지 않고 HashMap을 사용하는 이유는 성능 때문이다.

만약에 HashMap을 사용하지 않고 list를 사용했다면 원소를 검색하는데 시간복잡도는 O(n)일 것이다.

반면에 HashMap은 삽입, 검색에 시간복잡도 O(1)이라는 이점을 가지고 있다.

---

HashMap 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

Java 소스를 통해 HashMap객체를 생성해보자.

HashMap 객체를 생성하면 default 생성자로 loadFactor에 초기값 DEFAULT_LOAD_FACTOR(0.75/float) 가 주입되는것을 볼 수 있다.

loadFactor란?

• 테이블의 버킷이 얼마나 가득 찼는지 보여주는 수치다.

put

HashMap에 Key, Value 값을 넣어보자.

HashMap에 put 구현체를 확인해보면

hash 함수를통해 key를 고유한 index로 생성 하는거를 확인해 볼 수있다.

putVal(hash(key), key, value, false, true) 값으로 해당함수를 호출하고있다.

첫번째 if 문을 확인해보면 table 변수를 tab에 넣고 값이 null 이라면 resize() 함수를 실행시킨다.

resize() 메소드를 확인해보면 기본 생성자를 통해 객체를 생성하면 Node배열이 16사이즈로 default로 생성되는거를 확인 할 수 있다.

다시 putVal 함수로 돌아와 카 (n-1) & 키로 생성된 hash 값으로 해당 번지수가 null이면 해당번지에 newNode를 생성한다.

loadFactor의 데이터를 초과하게 되면 resize()를 통해 현재 크기의 두배로 배열을 재산정한다

16 -> 32

key 기반의 데이터를 저장하기 때문에 HashMap은 데이터의 순서를 보장하기 어렵다.

---

Hash의 충돌

위에서 설명한 Hash함수를 통해 나온 값이 동일하면 해쉬 값이 충돌이 일어난다.

해당 충돌 문제를 해결하기 위한 방법은 크게 2가지가 있다.

Java에서는 분리연결법을 통한 해결방안을 사용하고 있다.

-> 분리 연결법(Separate Chaining)

Java8의 Hash테이블은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현하였다.

해당 번지가 null 이 아니면 .next를 통해 동일한 버킷으로 접근을 하여 데이터들을 연결을 해서 관리해주고 있다.

-> 개방 주소법(Open Addressing)

해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.

Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.

Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.

Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

지금까지 분리연결법에서 중복된값을 저장할때 Linked List를 사용했다.
그러나 자바8에서부터 데이터의 수가 많아지면 연결리스트대신 트리를 사용하도록 바뀌었다
개수가 8개가 되면 링크드 리스트를 트리로 변경한다.

get

데이터를 get 할때도 key의 hash 값을 통해 값이 존재하거나 크기가 0이상 등 조건을 통해 해당 first(Value) 를 리턴한다

---

정리

• 각각의 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다.
  하지만 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.

• Java의 HashMap은 키-값 쌍 개수가 일정이상이 되면 해시버킷의 크기를 2배로 늘린다.
  해시버킷 개수의 기본값은 16이고 일정개수 이상이 되면 2배씩 증가시켜 최대 2^30개까지 증가시킨다.
  계속해서 배열의 크기가 커지면 성능저하 문제로 해시맵에 데이터 갯수를 안다면 초기에 크기를 적절히 설정하자.

• 자바8부터 데이터의 개수가 일정수준 이상이 되면 연결리스트에서 트리로 변경된다.

🤣 처음에 class 파일을 까보면서 혼돈의 카오스 그 자체였다. 그래도 보다 보니 소스를 전부 이해하는 것이 아닌 어느 정도 보고 흐름을 파악하는 능력이 조금씩 생긴 거 같다. 무작정 사용하는 것이 아니고 구조를 알고 해당하는 상황에 맞게 사용할 줄 알게 된다면, 한 단계 성장하는 개발자가 될 거라는 생각이 든다.

---

참고자료

• https://mangkyu.tistory.com/102
• https://sabarada.tistory.com/57
• java class 파일 뒤져보기