본문 바로가기
Back-end

Hash, HashTable, HashMap, CuncurrentHashMap

by 신재권 2023. 8. 16.

Hash란 무엇인가

Hash는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 것을 말합니다.

해시 함수를 사용하여 데이터를 해싱하면 데이터가 저장되거나 검색될 때 효율적으로 사용할 수 있는 고유한 값이 생성됩니다.

해시 함수에 의해 생성된 값을 해시 코드 또는 해시 값 이라고 합니다.

그래서 Hash가 왜필요하고, 언제 사용하고, 어떻게 활용하는데?

해시는 데이터를 고정된 크기의 값으로 변환하여 빠른 검색 및 비교를 가능하게 해줍니다.

해시를 사용하면 DB에서 특정 값을 빠르게 찾거나, 중복을 확인하는 등 다양한 작업에 활용할 수 있습니다.

해시는 암호학에서도 사용되어 비밀번호와 같은 민감한 정보를 안전하게 저장할 수 있도록 해줍니다.

Hash의 동작 원리

해시 함수는 데이터의 내용을 기반으로 해시 코드를 생성합니다.

이 때 데이터의 내용이 조금이라도 변경되면, 해시 코드도 다른 값이 됩니다.

즉, 데이터의 무결성을 검증하거나, 데이터 검색을 빠르게 할 수 있습니다.

Hash 충돌이란?

해시 충돌은 서로 다른 데이터가 같은 해시코드를 가지는 상황을 의미합니다.

해시 함수는 원래 데이터를 고정된 길이의 해시코드로 변환하는데, 데이터가 매우 다양하더라도 해시 코드의 길이는 유한하기 때문에, 두 데이터가 다른 값이여도 해시 함수에 의해 같은 해시 코드로 변환되는 해시 충돌이 발생할 수 있습니다.

Hash 충돌이 일어나면 뭐가 안좋을까?

  1. 검색 성능 저하 : 해시 충돌이 발생하면, 서로 다른 데이터가 같은 해시 코드로 매핑되므로, 의도했던 검색 성능을 얻을 수 없습니다. 즉, 해시 테이블에서 데이터를 검색할 때 추가 연산이 필요합니다.
  2. 시간 복잡도 증가 : 충돌이 발생하면 모든 핸들링에 추가 작업이 필요하기 때문에 시간 복잡도가 증가하고, 성능이 저하됩니다.

자바에서 기본으로 제공되는 해시 기반 자료구조들은 충돌을 내부적으로 해결하기 위해 개별 체이닝이나 개방 주소법과 같은 방식을 사용합니다.

Hash 충돌 해결법

  1. 개별 체이닝(Separate Chaining) : 각 해시 버킷에 연결 리스트나 다른 자료구조를 사용하여 충돌된 데이터를 저장하는 방식입니다. 충돌이 발생하면, 해당 버킷에 다른 데이터가 있을 텐데, 연결 리스트 등을 이용하여 그 뒤에 데이터를 추가로 저장합니다.
  2. 개방 주소법(Open Addressing) : 충돌이 발생했을 때 다른 빈 버킷에 데이터를 저장하는 방식입니다. 다른 빈 버킷을 찾아가며 데이터를 저장하거나 검색합니다. 선형 탐색, 이중 해싱 등의 방법을 사용할 수 있습니다.

Java에서는 기본적으로 개별 체이닝 방식을 통해 Hash 충돌을 해결합니다.


HashTable란 무엇인가?

HashTable은 Key, Value의 쌍으로 데이터를 저장하는 자료구조 입니다.

특정 키에 대한 값을 저장하고 검색할 때 사용됩니다.

내부적으로 배열을 사용하여 버킷들을 관리하며, 각 버킷은 연결 리스트로 구성되어 해시 충돌이 발생한 데이터들을 저장합니다.

HashTable은 키를 해시 함수를 통해 해시 코드로 변환하여 배열의 인덱스로 사용하고, 해당 인덱스에 값을 저장하거나 검색합니다.

그래서 왜 HashTable이 좋은건데?

특정 키에 대한 값을 빠르게 찾을 수 있습니다.

해시 함수를 사용함으로 검색 속도가 상수 시간에 근접합니다. 또한 중복된 키를 허용하지 않으므로 고유한 키를 가진 데이터를 저장할 수 있습니다.

또한 HashMap과 다르게 동기화가 지원되어 Thread-Safe 합니다.

키와 값에 null을 사용할 수 없습니다.

HashTable은 언제 사용되는가?

HashTable은 특정 키에 대한 값을 빠르게 찾아야 할 때 사용합니다.

예시로 DB에서 고유한 ID에 해당하는 값을 검색하거나, 캐시(cache)를 구현하는데 사용될 수 있습니다.

HashTable의 장단점

장점

  • 빠른 검색과 삽입이 가능합니다.
  • 중복된 키를허용하지 않아 고유한 데이터를 관리할 수 있습니다.
  • 동기화가 지원되어 thread-safe 합니다.

단점

  • 해시 함수 충돌 문제가 발생할 수 있습니다.
  • 메모리 사용이 비효율적일 수 있습니다.

HashTable의 성능 향상법

해시 함수 충돌을 최소화 하는 해시 함수 설계와 충돌이 발생했을 때 대응하는 방법을 통해 성능을 향상 시킬 수 있습니다.


HashMap이 뭔가?

HashMap은 HashTable과 비슷한 역할을 합니다.

키와 값의 쌍으로 데이터를 저장하며, 해시 함수를 사용하여 키를 해시 코드로 변환하여 데이터를 저장하거나 검색합니다.

null값을 허용하고, 동기화를 지원하지 않아 스레드 안전하지 않습니다.

내부적으로 배열을 기반으로 해시 테이블을 구현합니다. 버킷 배열을 사용하여 해시 키를 해시 코드로 변환하고, 변환된 해시 코드를 인덱스로 사용합니다.

해당 버킷에 연결된 연결리스트의 크기가 8이 되면, 내부적으로 resize()를 호출합니다.

resize() 메서드는 다른 버킷으로 데이터를 옮기는 작업을 합니다.

지속적으로 resize()가 되면서 해시맵의 크기가 64개가 되고, 버킷에 담긴 노드의 개수가 8개가 되어서야 비로소 트리로 변환되어 관리되어 성능이 최적화 됩니다.

버킷의크기가 6보다 작아지면 다시 Tree 대신 연결리스트로 운용됩니다.

연결 리스트로 구성된 버킷은 해시 충돌이 발생한 데이터를 저장하며, Java 8부터 버킷 내의 데이터 개수가 일정 수 이상이 되면 연결 리스트 대신 트리를 사용하여 성능을 최적화 합니다.

내부적으로 비어있는 버킷의 수와 데이터 개수를 기반으로 로드팩터(데이터 갯수/버킷수)를 계산하여, 로드 팩터가 일정 값을 초과하면 버킷 배열의 크기를 조절하는 리해싱(rehashing) 작업을 수행합니다.

HashMap은 언제 사용하는가?

HashMap은 HashTable 과 비슷한 기능을 제공하지만, 더 나은 성능과 확장성을 제공합니다.


ConcurrentHashMap의 등장 배경

ConcurrentHashMap은 HashTable과 HashMap의 한계점을 극복하기 위해 등장한 클래스 입니다.

기존 HashTable은 동기화를 지원하지만, 성능이 제한되었고, HashMap은 높은 성능을 제공하지만, 동기화를 지원하지 않았습니다.

위 문제를 해결하기 위해 ConcurrentHashMap이 개발되었습니다.

ConcurrentHashMap은 내부적으로 분할된 세그먼트를 사용하여 동시성을 제공합니다. 이로 인해 여러 스레드가 동시에 맵의 다른 부분에 접근할 수 있고, 성능이 향상됩니다.

즉, ConcurrentHashMap은 내부의 버킷 하나하나가 동기화되지만, HashTable은 전체 테이블에 대해 동기화가 수행되어 성능이 제한될 수 있습니다.

분할된 세그먼트를 사용하여 동시성을 제공하기 때문에 멀티스레드 환경에서도 HashTable에 비해 높은 성능을 유지합니다.

ConcurrentHashMap은 내부적으로 volatile 키워드를 사용하여, 변경 사항 발생시 모든 스레드에게 즉시 반영되게 합니다.

즉, 동기화 방식이 다릅니다.

'Back-end' 카테고리의 다른 글

클래스 로더  (0) 2023.08.18
static  (0) 2023.08.16
ArrayList vs LinkedList vs Array  (0) 2023.08.16
hashCode()  (0) 2023.08.16
왜 float과 double은 == 연산을 사용하면 안될까?  (0) 2023.08.16