[JAVA] HashMap, HashTable, ConcurrentHashMap,LinkedHashMap 차이

HashMap, HashTable, ConcurrentHashMap,LinkedHashMap 차이

 

HashMap

• 데이터를 저장할 때 키-값 쌍으로 저장하며, 키는 중복되지 않으며 null을 허용합니다. 값은 중복되어도 상관없으며, null도 허용합니다. HashMap은 동기화가 되어있지 않기 때문에 멀티스레드 환경에서 사용할 때는 주의가 필요

 

HashMap은 여러 쓰레드가 동시접근할경우 생기는 문제점

HashMap은 여러 스레드가 동시에 접근할 경우, 데이터 일관성 문제가 발생할 수 있습니다. 이는 다음과 같은 상황에서 발생할 수 있습니다.

1. 해시 충돌이 발생하는 경우, 같은 인덱스에 여러 데이터가 중복되어 저장될 수 있습니다. 이 때는 링크드 리스트를 이용하여 데이터를 추가로 연결하는데, 데이터가 많이 쌓이면 검색 속도가 느려지게 됩니다.-> 이런 상황에서 HashMap은 일정 길이 이상의 링크드 리스트를 가지게 되면, 해당 인덱스에 대한 모든 데이터를 새로운 위치로 이동시켜야 하는 데이터의 재배치(rehashing)가 발생합니다.
2. 한 스레드가 HashMap의 값을 수정하는 도중에 다른 스레드가 같은 위치에 있는 값을 수정한다면, 값이 덮어써지는 문제가 발생할 수 있습니다.
3. 여러 스레드에서 동시에 HashMap에 데이터를 추가하면, 배열의 크기가 늘어나야 하는 상황에서도 여러 스레드가 동시에 배열의 크기를 조정하려고 할 수 있습니다. 이런 경우 서로 다른 스레드가 동시에 배열의 크기를 증가시키려고 할 수 있으며, 이로 인해 배열의 크기가 너무 작아져서 데이터의 재배치(rehashing)가 자주 발생하게 됩니다.

*재배치란?

HashMap은 내부적으로 배열과 링크드 리스트를 사용하여 데이터를 저장합니다. 이때 배열의 크기는 HashMap의 초기 크기와 로드 팩터(load factor)에 따라 결정됩니다. 만약 배열의 크기가 초기에 설정된 값보다 작아지면, 배열의 크기를 늘리고 모든 데이터를 새로운 배열에 다시 해싱해야 합니다. 이 작업이 바로 데이터의 재배치(rehashing)입니다

 

이러한 문제를 해결하기 위해서는 ConcurrentHashMap을 사용하거나, HashMap을 동기화하는 방법을 사용해야 합니다. ConcurrentHashMap은 동시에 여러 스레드가 접근해도 안전하게 데이터를 관리할 수 있도록 동기화를 제공합니다. 또한, HashMap을 동기화할 경우에는 동기화된 블록으로 HashMap의 접근을 제어하여 데이터의 일관성을 보장할 수 있습니다.

 

 

HashTable 

HashMap과 유사한 해시 테이블 구조를 사용하지만, HashMap과 달리 동기화(synchronization)를 제공합니다. 즉, 멀티스레드 환경에서 안전하게 사용할 수 있습니다. 하지만 동기화를 제공하므로 성능면에서는 HashMap보다 떨어지는 경우가 있습니다. 또한, null 값을 허용하지 않습니다.

HashTable이 어떤식으로 동기화를 제공하는가?

HashTable은 모든 메서드에 synchronized 키워드를 사용하여, 스레드 간에 동기화를 제공합니다. synchronized 키워드를 사용하면, 한 번에 하나의 스레드만 해당 메서드에 접근할 수 있도록 제한합니다. 따라서, 동기화를 제공함으로써 멀티스레드 환경에서 데이터 일관성 문제를 방지할 수 있습니다.

하지만, synchronized 키워드를 사용하면 성능이 저하될 수 있기 때문에, 자바 1.5부터는 ConcurrentHashMap이나 Collections.synchronizedMap 메서드를 사용하여 동시성을 보장하는 Map 자료구조를 사용하는 것이 권장됩니다. 이러한 자료구조들은 HashTable과 달리, 락(lock)을 더욱 세분화하여 성능을 향상시킬 수 있습니다.

 

ConcurrentHashMap 

ConcurrentHashMap은 멀티스레드 환경에서 안전하게 사용할 수 있는 해시 테이블 구조입니다. HashMap과 비슷하지만, 동기화를 적용하는 대신 세분화된 락(lock)을 사용하여 성능을 향상시켰습니다. 

 

ConcurrentHashMap은 어떤식으로 Lock을 사용하는가?

1.세그먼트(Segment) 락

ConcurrentHashMap은 내부적으로 여러 개의 세그먼트(Segment)로 나뉘어져 있습니다. 각 세그먼트는 자체적으로 락을 가지고 있으며, 서로 독립적으로 작동합니다. 이를 통해 여러 스레드가 동시에 접근해도 서로 다른 세그먼트에서 작업하므로, 락 충돌이 발생할 확률을 줄일 수 있습니다.

 

2.엔트리(Entry) 락

ConcurrentHashMap은 각 엔트리(Entry)에 대해 락을 가질 수 있습니다. 각 세그먼트는 엔트리 락을 사용하여, 해당 세그먼트 내에서 동시에 접근하려는 여러 스레드 간의 경쟁을 제어합니다. 엔트리 락은 세그먼트 락보다 작은 범위에서 락 충돌이 발생할 확률을 줄일 수 있습니다.

해시버켓과 세그먼트

 

ConcurrentHashMap은 여러 스레드에서 안전하게 사용할 수 있는 해시 맵입니다. 이를 가능하게 하는 방법 중 하나는, 내부적으로 여러 개의 해시 버킷을 여러 개의 세그먼트(segment)로 분할하여 관리합니다. 각 세그먼트는 자체적으로 동기화되어 있으므로, 여러 스레드에서 동시에 접근해도 안전하게 데이터를 처리할 수 있습니다.

해시버킷:
해시 테이블에서 데이터를 저장하는 공간입니다. 해시 버킷은 일반적으로 연결 리스트(linked list) 혹은 트리(tree) 구조로 구성되어 있습니다. 각각의 해시 버킷은 배열의 한 인덱스에 해당하며, 버킷 내부에는 키(key)와 값(value) 쌍을 저장하는 엔트리(Entry) 객체가 저장됩니다. 해시 함수에 의해 계산된 해시 값이 버킷의 인덱스로 사용됩니다.

여러 개의 세그먼트(segment)로 분할:
ConcurrentHashMap은 내부적으로 세그먼트(segment)라는 작은 해시 테이블을 여러 개 만들어 관리합니다. 전체 해시 테이블을 하나의 큰 해시 버킷으로 관리하는 것이 아니라, 작은 세그먼트 단위로 분할하여 병렬성(parallelism)을 높이는 것입니다.

각각의 세그먼트는 자신만의 해시 버킷 배열을 가지고 있으며, 세그먼트 내부의 각 버킷은 엔트리(entry) 객체로 구성됩니다.

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(16, 0.75f, 4);

map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
map.put("date", 4);
map.put("eggplant", 5);
map.put("fig", 6);
map.put("grape", 7);
map.put("honeydew", 8);

위의 코드에서 ConcurrentHashMap의 초기 크기는 16이며, 로드 팩터(load factor)는 0.75로 설정되어 있습니다. 이 때, 4개의 세그먼트를 가진 ConcurrentHashMap가 생성됩니다.

위의 코드에서 put 메서드를 사용하여 키-값 쌍을 추가하는데, 이때 키의 해시 값을 기준으로 어떤 세그먼트에 데이터를 추가할지 결정됩니다. 예를 들어, "apple"의 해시 값이 0이면, 0번 세그먼트에 저장되고, "banana"의 해시 값이 1이면, 1번 세그먼트에 저장됩니다.

각각의 세그먼트는 독립적으로 잠금을 가지고 있으므로, 여러 스레드에서 동시에 접근하더라도 세그먼트 간의 충돌이나 경합 없이 안전하게 작업을 처리할 수 있습니다.

 

LinkedHashMap 

LinkedHashMap은 데이터의 삽입 순서를 유지하는 해시 테이블과 연결 리스트를 결합한 자료구조입니다. 데이터를 저장할 때 순서대로 저장하기 때문에, 데이터의 순서가 중요한 상황에서 사용하기 적합합니다. LinkedHashMap은 동기화가 되어있지 않기 때문에 멀티스레드 환경에서 사용할 때는 주의가 필요합니다.

 

정리

HashMap	HashTable	ConcurrentHashMap	LinkedHashMap
멀티스레드 O,성능↓,안전성X null값 허용O 내부적으로 배열과 해시 함수를 사용하여 데이터를 저장	동기화 지원 null값 허용X 내부적으로 배열과 해시 함수를 사용하여 데이터를 저장	멀티스레드 O, 성능↑ 내부적으로 배열과 해시 함수를 사용하여 데이터를 저장	데이터의 순서가 중요한 상황에서 사용 내부적으로 해시 테이블과 링크드 리스트를 사용하여 데이터를 저장

내부적으로 배열, 해시 함수 사용 VS 링크드 리스트를 사용

배열은 순서대로 메모리 공간을 할당하는 것이 아니라, 각 데이터의 키(key)에 대한 해시 값을 계산하여 그 위치에 저장합니다. 이를 통해, 데이터를 빠르게 검색할 수 있습니다. 예를 들어, "apple"이라는 키(key)를 저장할 때 해당하는 해시 값이 123이라면, 123번째 위치에 데이터를 저장합니다. 이렇게 하면, "apple"이라는 키(key)를 검색할 때 123번째 위치에서 검색을 시작할 수 있으므로 검색 속도가 빨라집니다.

해시 함수는 키(key)를 입력으로 받아서, 고정된 길이의 값으로 변환합니다. 이 때, 같은 키(key)는 항상 같은 해시 값이 반환되도록 구현합니다. 이러한 해시 함수를 사용하여, 배열에서 데이터를 빠르게 검색할 수 있습니다.

ConcurrentHashMap과 HashMap은 같은 구조를 사용하지만, ConcurrentHashMap는 멀티스레드 환경에서 안전하도록 내부적으로 락(lock)을 사용합니다. 이를 통해, 여러 스레드가 동시에 ConcurrentHashMap에 접근해도 안전하게 데이터를 처리할 수 있습니다.

반면에, LinkedHashMap은 데이터를 입력한 순서대로 유지합니다. 내부적으로 배열과 링크드 리스트를 사용하여 데이터를 저장하는데, 배열은 해시 함수에 의해 인덱스가 결정되고, 링크드 리스트는 데이터의 입력 순서를 기억합니다. 이를 통해, 데이터의 입력 순서대로 데이터를 순회하거나 처리할 수 있습니다.

 

 

Map과 Hashmap의 차이

Map은 자바 컬렉션 프레임워크(Collection Framework)의 인터페이스 중 하나로, 키(key)와 값(value)을 쌍으로 저장하는 자료구조를 정의합니다. Map은 키(key)를 중복해서 저장할 수 없으며, 각 키(key)에 대응하는 값(value)을 쉽게 찾을 수 있습니다.

HashMap은 Map 인터페이스를 구현한 자료구조 중 하나입니다. HashMap은 내부적으로 배열과 해시 함수를 사용하여 데이터를 저장합니다. 데이터의 키(key)는 해시 값(hash value)에 따라 배열의 인덱스를 결정하고, 값(value)은 해당 인덱스에 저장됩니다.

 

 

해시 값(hash value)에 따라 배열의 인덱스를 결정하고, 값(value)은 해당 인덱스에 저장

hashmap에서 데이터 key로 해시값을 사용하는 이유

HashMap에서 데이터의 키(key)를 이용하여 해시 값을 사용하는 이유는 검색 속도를 빠르게 하기 위해서입니다.

HashMap은 데이터를 배열에 저장합니다.

예를 들어, "apple"이라는 키(key)를 저장할 때 해당하는 해시 값이 123이라면, 123번째 인덱스에 데이터가 저장됩니다. 이렇게 함으로써, "apple"이라는 키(key)를 검색할 때에는 데이터의 해시 값을 계산한 후, 해당하는 인덱스에 저장된 데이터를 찾아서 반환할 수 있습니다.

 

배열에서 데이터를 검색할 때는 인덱스를 이용하여 접근하므로, 검색 속도가 빠릅니다. 하지만, 데이터가 많아질수록 배열의 크기도 커지므로, 인덱스를 찾는 데 걸리는 시간도 늘어납니다. 이 문제를 해결하기 위해 데이터의 키(key)를 이용하여 해시 값을 계산하고, 이를 배열의 인덱스로 사용합니다.

 

1.서로 다른 키(key)에 대해 서로 다른 해시 값이 계산

해시 값은 고정된 크기의 값이므로, 배열의 크기와 관계 없이 인덱스를 계산할 수 있습니다. 또한, 해시 값은 고유한 값이므로, 서로 다른 키(key)에 대해 서로 다른 해시 값이 계산됩니다. 따라서, 해시 값을 이용하여 데이터를 저장하면, 데이터의 검색 속도를 배열의 크기에 관계 없이 일정한 속도로 유지할 수 있습니다.

(해당 데이터의 해시 값으로부터 바로 해당 배열 요소에 접근할 수 있기 때문)

 

2.O(1)의 시간 복잡도를 가지는 자료구조

또한, HashMap은 데이터의 추가, 삭제, 검색 작업에서 O(1)의 시간 복잡도를 가지는 자료구조입니다. 이러한 특징 때문에, 데이터 검색이 빈번하게 발생하는 경우에는 HashMap을 사용하여 데이터를 저장하는 것이 좋습니다.

 

Hashing이란 무엇인가?

해싱(Hashing)은 데이터를 고정된 크기의 해시 값(Hash value)으로 변환하는 것을 말합니다. 해시 값은 일반적으로 정수형이며, 데이터의 고유한 특성을 나타내는 값을 가지고 있습니다. 예를 들어, 문자열 데이터를 해싱하면 고정된 길이의 정수형 해시 값이 생성되며, 이 값을 인덱스로 사용하여 데이터를 빠르게 검색할 수 있습니다.

해시함수랑 Hashing 차이

해시함수 : 데이터를 해시 값으로 변환하는 함수

hashing : 해시 함수를 사용하여 데이터를 해시 값으로 변환하고, 해당 값에 대응하는 인덱스를 찾아서 데이터를 저장

hash값의 중복을 피할 수 없는 이유는?

해시 충돌은 서로 다른 데이터가 동일한 해시 값을 가지는 경우를 뜻합니다.

해시 함수는 일반적으로 데이터의 크기가 큰 값을 고정된 크기의 해시 값으로 변환합니다. 이때, 데이터의 크기가 매우 크거나 해시 값의 크기가 작은 경우에는 해시 충돌이 발생할 가능성이 높아집니다.

데이터의 크기가 매우 클경우 

해시 함수가 해시 값으로 변환하는 과정에서 데이터의 일부분만을 이용할 수 있기 때문입니다. 이 때문에, 서로 다른 데이터가 동일한 해시 값을 가지는 경우가 발생할 수 있습니다.

 

해시 값의 크기가 작을경우

(해시 값의 크기가 작다는 것은 해시 함수가 반환하는 비트 수가 적다는 것을 의미합니다. 예를 들어, 해시 함수가 16비트의 해시 값을 반환한다면, 이는 2^16 (65,536) 개의 가능한 해시 값 중 하나를 가리킵니다.)

해시 충돌이 발생할 확률이 높아집니다. 해시 값의 크기가 작으면, 서로 다른 데이터가 동일한 해시 값을 가질 가능성이 높아지기 때문입니다. 이때, 해시 충돌이 많이 발생하면 검색 성능이 떨어지게 되므로, 해시 함수의 선택은 중요합니다.

 

=> 데이터의 크기가 매우 크거나 해시 값의 크기가 작은 경우에는 해시 충돌이 발생할 가능성이 높아지므로, 해시 함수의 설계나 해시 값의 크기 등을 고려하여 충돌을 최소화해야 합니다.

 

해시테이블 구조란?

해시테이블은 내부적으로 배열과 해시 함수(hash function)를 사용하여 데이터를 저장합니다. 데이터의 키(key)를 해시 함수에 입력하여 나온 해시 값(hash value)을 배열의 인덱스로 사용하여 값을 저장합니다. 이를 통해, 데이터를 검색할 때는 데이터의 키(key)를 이용하여 해시 값을 계산하고, 해당하는 인덱스에 저장된 값을 찾아서 반환합니다.

하지만, 같은 해시 값이 여러 개의 데이터에 대해 발생할 수도 있습니다. 이를 해시 충돌(hash collision)이라고 부르며, 해시 충돌을 해결하기 위해서 링크드 리스트(linked list)나 트리(tree) 등을 사용하여 데이터를 저장합니다.

해시테이블은 데이터를 빠르게 검색할 수 있지만, 해시 충돌이 발생할 경우에는 검색 성능이 떨어질 수 있습니다. 따라서, 해시 함수의 성능이 중요하며, 좋은 해시 함수를 사용하는 것이 해시테이블의 성능을 향상시키는 방법 중 하나입니다.

해시테이블 VS 해시맵

해시테이블과 해시맵은 모두 해시 함수와 배열을 사용하여 데이터를 저장하는 자료구조입니다.

하지만, 해시테이블은 대부분의 언어에서 이용 가능한 기본 자료구조이며, 멀티스레드 환경에서 안전하게 사용할 수 있도록 동기화를 지원합니다. 따라서, 멀티스레드 환경에서 안전하게 사용할 수 있는 자료구조를 구현해야 할 때에는 보통 해시테이블을 사용합니다.

반면에, 해시맵은 자바에서 제공하는 자료구조 중 하나입니다. 해시맵은 해시테이블과 마찬가지로 배열과 해시 함수를 이용하여 데이터를 저장하지만, 멀티스레드 환경에서 동시 접근에 대한 안전성을 제공하지 않습니다. 따라서, 멀티스레드 환경에서 안전하게 사용할 수 있도록 ConcurrentHashMap 등의 동기화 기능이 추가된 자료구조를 사용해야 합니다.

또한, 해시맵은 일부 구현체에서 null 값을 허용하며, 일부 구현체에서는 순서를 보장하지 않을 수 있습니다. 해시테이블은 null 값을 허용하지 않으며, 일반적으로 순서를 보장하지 않습니다.

따라서, 자바에서 멀티스레드 환경에서 안전하게 사용하려면 ConcurrentHashMap을 사용하고, null 값을 허용하며 순서를 보장하지 않는 경우에는 HashMap을 사용하는 것이 일반적입니다. 해시테이블은 멀티스레드 환경에서 안전하게 사용할 수 있지만, 일반적으로 성능(해시충돌) 이 떨어지기 때문에 해시맵보다는 잘 사용되지 않습니다.

 

해시 분포와 해시 충돌이란?

해시테이블에서 데이터를 저장할 때, 각 데이터의 키에 대해 해시 함수를 적용하여 해시 값을 계산합니다. 이 해시 값은 배열의 인덱스로 사용되어 해당 인덱스에 데이터가 저장됩니다.
해시 함수는 데이터의 키를 입력으로 받아서 해시 값을 계산하는 함수입니다. 하지만, 서로 다른 데이터의 키가 같은 해시 값을 가지게 되면, 데이터는 같은 인덱스에 저장됩니다. 이를 해시 충돌이라고 합니다.
해시 충돌은 데이터 검색 속도를 느리게 만들 수 있으므로, 해시 함수를 잘 선택하는 것이 중요합니다. 이를 위해 해시 함수는 데이터의 분포를 고려하여 설계되어야 합니다. 즉, 서로 다른 데이터가 최대한 다른 해시 값을 가지도록 해야 합니다. 이를 해시 분포라고 합니다.

해시충돌 발생 시 해결하는 방법

1.링크드 리스트 사용(체이닝)

해시 함수를 설계할 때, 해시 충돌이 발생할 가능성이 있으므로, 충돌을 처리할 수 있는 방법도 고려해야 합니다. 일반적으로는 같은 인덱스에 여러 개의 데이터를 연결하는 링크드 리스트를 사용합니다. 하지만, 링크드 리스트의 길이가 너무 길어지면 검색 속도가 느려지기 때문에, 일정 길이 이상의 링크드 리스트를 가지게 되면, 해당 인덱스에 대한 모든 데이터를 새로운 위치로 이동시켜야 하는 데이터의 재배치(rehashing)가 발생합니다.

 

2.이중 해싱(Double Hashing)

해시 충돌이 발생하면, 다른 해시 함수를 이용하여 새로운 해시 값을 계산하는 방식입니다. 이중 해싱은 충돌을 최소화하는데 효과적이지만, 해시 함수를 여러 개 사용해야 하므로 계산 비용이 더 들어갑니다.

 

Enum이란 무엇인가?

Enum은 열거형(enumerated type)이라는 데이터 타입으로, 서로 관련있는 상수 값을 묶어서 정의할 수 있는 자바의 특별한 클래스입니다.

자바 5부터 추가된 열거형은 안정성과 가독성을 높이는 장점을 가지고 있으며, 상수 값을 묶어서 정의할 수 있어 코드의 가독성을 높이고 유지보수성을 높일 수 있습니다.

 

왜 equals를 정의할 때 hashcode도 같이 정의해야 하는가?

equals() 메서드와 hashCode() 메서드는 모두 자바의 객체 동등성 비교와 관련된 메서드입니다. equals() 메서드는 두 객체가 내용적으로 동일한지 비교하며, hashCode() 메서드는 두 객체가 같은 객체인지 여부를 결정하는 데 사용됩니다.
따라서, equals() 메서드를 오버라이딩할 때 hashCode() 메서드도 같이 오버라이딩해야 합니다. 그 이유는 hashCode() 메서드의 결과가 같은 두 객체는 equals() 메서드로 비교했을 때 같은 객체로 판단되어야 하기 때문입니다.
만약, hashCode() 메서드를 오버라이딩하지 않고 equals() 메서드만 오버라이딩하면, 같은 내용을 가진 두 객체라도 hashCode() 메서드의 결과가 다를 수 있습니다. 이 경우, 같은 내용을 가진 두 객체도 서로 다른 객체로 판단될 수 있습니다.
또한, hashCode() 메서드는 객체를 식별하는 해시 값으로 사용됩니다. 자바의 해시 기반 자료구조에서 객체를 저장하거나 검색할 때 hashCode() 메서드를 사용하여 해시 값으로 변환하므로, hashCode() 메서드를 제대로 구현하지 않으면 자료구조에서 예기치 않은 동작이 발생할 수 있습니다.
따라서, equals() 메서드를 정의할 때 hashCode() 메서드도 같이 정의해야 하며, 두 메서드는 일관된 방식으로 구현되어야 합니다.

 

HashCode와 해시함수의 차이

hashcode() 메서드는 Java의 Object 클래스에 정의된 메서드로, 객체의 해시 코드(hash code)를 반환합니다. 해시 코드는 객체의 메모리 주소를 사용하여 계산되며, 모든 객체가 유일한 해시 코드를 갖도록 보장됩니다.

해시 함수는 일반적으로 해시 테이블과 같은 자료구조에서 사용되는 함수로, 임의의 크기를 가진 데이터를 고정된 크기의 해시 값으로 매핑합니다. 해시 함수는 데이터의 내용에 따라 해시 값이 결정되며, 일반적으로 해시 값이 서로 다른 데이터들이 동일한 해시 값이 나오는 것을 최소화하기 위해 설계됩니다.

따라서, hashcode() 메서드와 해시 함수는 비슷한 개념이지만, 다른 용도로 사용됩니다. hashcode() 메서드는 객체의 해시 코드를 반환하여 객체가 해시 테이블 등에서 고유하게 식별될 수 있도록 합니다. 반면에 해시 함수는 임의의 데이터를 고정된 크기의 해시 값으로 매핑하여 검색 속도를 높이는 등의 목적으로 사용됩니다.

 

 

https://javabypatel.blogspot.com/2016/09/concurrenthashmap-interview-questions.html