HashMap과 HashSet

HashMap

HashMap은 Map 인터페이스의 구현체로, hash 함수를 사용하여 데이터를 저장한다.

즉 HashMap은,

key에 대한 hash 값을 사용하여 Value를 저장하고 조회하며,

key-value 쌍의 개수에 따라 동적으로 크기가 증가하는 Associate Array 이다.

기존 map의 특징처럼 중복 key는 허용하지 않고, 데이터를 넣은 순서를 유지하지 않는다.

여기서 Map interface를 구현한 또 다른 구현체인 TreeMap은 데이터의 순서를 유지한다.

HashMap과 HashTable

HashTable은 Map 인터페이스를 구현하고 있기 때문에 위와 똑같은 기능을 한다.

하지만 HashMap에서는 HashTable과 다르게 **Additional Hash Function(보조 해시 함수)**를 사용하기 때문에 충돌이 덜 발생하므로 성능상 이점이 존재한다.

뿐만 아니라 HashTable와 달리 HashMap은 지속적으로 개선되고 있다.

 

---

 

해시 값 충돌 : hashCode() & equals()

hashCode

해시 함수를 갖고 있는 함수로, 임의의 길이의 데이터를 넣었을 때 고정된 길이의 데이터, 즉 해시 값을 리턴한다.

HashMap에서는 key로 삽입되는 데이터를 hashCode 메서드를 통해 해시 값(해시 버킷의 인덱스)를 생성한다.

equals()

HashMap에서는 새로 들어온 key의 해시값, 즉 해시 버킷의 인덱스에 이미 데이터가 존재할 때, 두 데이터의 key값을 비교해서 같으면 교체하고, 다르면 뒤에 연결하여 삽입한다.(Seperate Chaining + linked list) 방식일 경우

 

Hash 함수를 사용하는 부분 : hashCode : key 값의 결정

해시 함수는 임의의 데이터를 넣었을 때 일정한 길이의 데이터를 출력해주는 함수이다.

HashMap에서는 key값에 해시를 적용하여 데이터를 저장 및 조회하기 때문에, key-value 형태의 데이터를 넣는 과정(put())과 조회하는 과정(get())에서 key 값을 결정하기 위해 hashCode() 메서드를 사용하는데, 이 메서드에서 해시 함수를 사용한다.

그런데 임의의 값을 해시 함수에 넣었을 때, 같은 해시 값이 나올 가능성이 존재한다. HashMap의 key 값은 겹칠 수 없기 때문에, 이처럼 같은 해시 값이 나오는 경우 충돌이 발생하는 것이다.

 

일반적인 Hash 충돌 해결 방법

HashTable에서 해시 값 충돌 해결 방법은 다음과 같은 두 가지 방법이 존재한다. HashMap은 둘 중 Separate Chaining 방법을 사용하는데, 우선 두 가지 방식의 개념을 살펴보자.

Open Addressing

충돌이 발생하면 탐사를 통해 빈 공간을 찾아 데이터를 저장한다.

구현 방법은 간단하지만, 모든 데이터가 자신의 해시 값과 일치하는 주소에 저장된다는 보장이 없다.

Seperate Chaining

충돌이 발생하면 연결 리스트로 연결하는 방식이다. 해시 값에 해당하는 주소에 이미 존재하는 데이터 뒤에 연결 리스트 형식으로 이어 붙이는 것이다.

가장 전통적인 방식이며, 모든 데이터가 자신의 해시 값과 일치하는 주소에 저장된다.

 

JAVA 의 Hash 충돌 해결 방법- Seperate Chaining

JAVA의 HashMap에서는 해시 충돌이 발생하면 Seperate Chaining 방식을 사용한다.

java7까지의 HashMap 구현 알고리즘은 다음과 같다.

“만약 객체의 해시 함수 값이 균등 분포(uniform distribution) 상태라면, get() 메서드 호출에 대한 기댓값은 E(N/M)이다.”

하지만 Java8에서는 이보다 더 나은 **E(log N/M)**을 보장한다. 이유는 Seperate Chaining에서 기존에 사용하던 Linked List 대산 Tree를 사용하기 때문이다.

하나의 해시 버킷에 할당된 Key-Value 쌍의 개수를 기준으로 하여 자료구조를 변경한다. 처음에 링크드 리스트에서, 8개가 되면 트리로 바꾸고, 다시 삭제되어 6개가 되면 링크드 리스트로 바꾼다. 자료구조를 변경하는 이유는 다음과 같다.

• 트리가 링크드 리스트보다 메모리 사용량이 많다
• 데이터 개수가 적을 때는 worst case의 수행 시간 차이가 거의 없다.

왜 6개, 8개로 차이를 2 만큼 두었을까?

만약 차이가 1이라면, 어떤 특정 key-value 쌍이 반복되어 삽입, 삭제 되는 경우, 이때 트리와 링크드 리스트간 불필요한 변경이 반복되어 오히려 성능 저하가 발생할 수 있기 때문이다.

Red-Black Tree

체이닝에서 사용하는 Tree는 Red-Black Tree를 사용한다.

 

---

 

HashSet

내부적으로 Hash를 이용하는 Set 인터페이스의 구현체이다.

Set(집합)이라는 이름대로, 집합적인 개념의 데이터 구조이다. 즉, 데이터(원소) 중복을 허용하지 않으며 순서가 없다.

HashSet의 내부에는 HashMap이 있다?

사실 HashSet은 HashMap으로 구현되어 있다.

HashSet은 HashMap과 다르게 key-value 값이 아니라 객체를 저장하기 때문에 완전히 다른 구조라고 생각할 수 있지만, 이 객체를 “중복” 없이, “순서” 없이 저장하기 위해 HashMap을 사용한다.

즉, HashSet에 객체를 저장하면 해당 객체를 Key로 하고, Value 값은 HashSet 내부 구현 코드에서 선언해둔 dummy 객체를 해시를 적용하여 저장한다. 이러한 이유로 HashMap보다 HashSet이 더 느리다.

hashCode() & equals()

hashCode()

해시 함수를 갖고 있는 함수로, 임의의 길이의 데이터를 넣었을 때 고정된 길이의 데이터, 즉 해시 값을 리턴한다.

HashSet에서는 입력 객체를 넣어 객체에 대한 해시 값을 생성한다.

equals()

기존에 저장되어 있던 데이터들의 해시 값과 새로 삽입되는 객체의 해시 값을 비교하여 중복된 객체가 있는지 체크한다. 즉 두 객체가 같은 값을 갖고 있는지 판단한다.

<aside> 🤔 그러면 여기서 쓰는 hashcode, equals는.. HashMap의 hashcode, equals와 별도인가?

</aside>

 

---

 

HashMap과 HashSet의 차이점

표 형태로 정리해보자

 

	HashMap	HashSet
인터페이스	Map	Set
데이터 저장 형태	Key-Value	Object-dummy
중복 허용 여부	중복 Key 가능, 중복 Value 불가능	중복 Object 불가능
NULL 허용 여부	key는 하나까지, value는 무제한	단 하나의 NULL
데이터 삽입 방법	key-value : 단 하나의 객체	삽입 객체(key), dummy 객체(value값)
성능	비교적 빠름	비교적 느림

 

---

 

[Java] HashMap, HashSet 이란? - (3) HashMap이란?

 

[Java] HashMap, HashSet 이란? - (4) HashSet이란?

 

[Java] HashMap, HashSet 이란? - (5) HashMap과 HashSet의 차이