[Java] HashTable VS HashMap(Linked List / Red-Black Tree)

1️⃣ HashTable 자료구조에 대해 알아보자

(Key, Value) 구조로 데이터를 저장하는 자료구조로, 빠르게 데이터를 검색할 수 있다.

각각의 Key 값에 해시함수를 적용해 고유 index를 생성하고, 이 index를 활용해 값을 저장하고 검색한다.

 

평균 O(1)의 시간복잡도를 갖지만 충돌이 일어나 연속적으로 검색해야 되는 경우 O(n)까지 증가할 수 있다.

 

💥 해시값이 충돌하는 경우

서로 다른 Key 값에 해시함수를 적용한 값이 동일한 경우에는 어떻게 할까?

 

1. 분리연결법(Seperate Chaining)

동일한 버킷일 경우 추가 메모리를 사용해 데이터를 연결해 관리한다.

분리연결법의 경우 해시 테이블의 확장이 필요 없고, 구현이 간단하지만 데이터의 수가 많아지면 동일한 버킷에 연결되는 데이터가 많아져 캐시 효율이 감소하는 단점이 있다.

 

2. 개방주소법(Open Addressing)

데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입한다.

 

연속된 공간에 데이터를 저장해 분리연결법보다 캐시 효율이 높다.

하지만 배열의 크기가 커질수록 L1, L2 캐시 적중률(hit ratio)이 낮아지기 때문에 데이터 개수가 적을 때만 분리연결법보다 성능이 좋다.

 

• Linear Probing(선형 탐사)
  • 현재의 버킷 index로부터 고정폭만큼씩 이동하여 차례대로 검색해 비어있는 버킷에 데이터 저장
• Quadratic Probing(제곱 탐사)
  • 해시의 저장순서 폭을 제곱으로 저장
    ex) 처음 충돌 발생 경우 1 이동, 그다음 충돌 시 2^2, 3^2 칸씩 검색
• Double Hashing Probing(이중해싱)
  • 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없앰
  • 다른 방법들보다 많은 연산

 

---

 

2️⃣ HashTable VS HashMap

🙆‍♀️ 공통점

둘 다 Map 인터페이스를 구현하고 있어 제공 기능은 동일하다.

 

🙅‍♀️ 차이점

HashTable은Java의 API. 컬렉션 프레임워크가 만들어지기 전에 존재하던 것이지만 호환을 위해 남겨둔 것이다.

HashMap은 Java Collections Framework API이다.

 

👍 Thread - safe

HashTable은 syncronized 키워드가 있어 동기화를 진행하지만 HashMap의 경우 syncronized 키워드가 없다.

따라서 멀티스레드 환경에서 데이터 무결성을 보장하지 않는다. 

 

✌️null 값 허용

HashTable은 Key에 null이 들어오면 NullPointerError를 던지지만 HashMap은 Key에 null이 들어오면 0으로 해싱하여 저장한다.

 

🤟 Enumeration 여부

HashTable은 Enumeration을 제공하지만 HashMap은 Enumeration을 제공하지 않는다.

 

👊 보조해시함수

HashMap은 HashTable과는 달리 보조해시함수를 사용해 성능상 이점이 있다.

 

 

---

 

3️⃣ Java의 HashMap은 어떻게 구현되어 있을까?

🧐 항상 해시 결괏값이 다른 해시 함수를 적용하면 되지 않나?

Boolean같이 서로 구별되는 객체의 종류가 적거나, Number 객체는 객체가 나타내려는 값 자체를 해시 값으로 사용할 수 있기 때문에 완전한 해시 함수의 대상이 될 수 있다.

하지만 String이나 POJO(plain old java object)에 대하여 완전한 해시 함수를 제작하는 것은 사실상 불가능하다.

🧐 POJO 란?
오래된 방식의 자바 오브젝트

🧐 오래된 방식이면 새로운 방식도 있나?
예를 들어 ORM 기술을 지원하는 Hibernate 프레임워크를 사용하는 경우
자바 객체가 Hibernate 프레임워크를 직접 의존하면 '특정 기술'에 종속되었기 때문에 POJO라 할 수 없음

 

🫠 왜 불가능해?

HashMap은 기본적으로 각 객체의 hashCode() 메서드가 반환하는 값을 사용하는 데, 결과 반환값 타입이 int다.

 

int형의 데이터 크기인 32bit로는 아래의 이유로 완전한 자료 해시 함수를 만들 수 없다.

1) 생성 가능한 객체의 수가 2^32보다 많을 수 있음(너무나 당연함)

2) 모든 HashMap 객체에서 O(1)로 랜덤 접근하려면 모든 HashMap이 원소가 2^32인 배열을 갖고 있어야 함(메모리상 비효율적)

 

따라서 해시 함수를 이용하는 연관 배열(키 하나와 값 하나인 자료구조 ex. map, dictionary)에서는 메모리를 절약하기 위하여 실제 해시 함수의 표현 정수 범위보다 작은 M개의 원소가 있는 배열만을 사용한다.

int index = X.hashCode() % M;

이 방식을 사용하면 해시 함수가 아무리 충돌을 회피하게 잘 구현되어 있다 해도 서로 다른 객체가 1/M 의 확률로 같은 해시 버킷을 사용하는 것이다. 따라서 Java에서는 크게 세 가지 방법으로 충돌을 관리한다.

 

 

👍 threshold(임계점)

첫 번째 방법은 버킷 사이즈를 조절하는 것이다.

 

버킷을 생성할 때 버킷의 크기를 resize() 할 때의 임계점인 threshold를 지정한다.

DEFAULT_LOAD_FACTOR는 0.75

DEFAULT_INITIAL_CAPACITY는 16의 상수로 선언되어 있어 threshold는 12가 된다.

🧐 Load Factor가 뭔가요?

Load Factor = 데이터 개수 / 초기 용량
-> 버킷이 얼마나 찼을 때 resize 하는 것이 좋은지에 대한 값

 

만약 버킷에 저장되어 있는 데이터의 수가 12개를 넘어가면 버킷의 사이즈를 2배로 늘린다.

 

자바는 이렇게 버킷이 75% 찬 경우 버킷의 사이즈를 두배로 늘려 충돌이 일어나지 않도록 관리하지만 버킷 개수가 증가할 때마다 모든 키-값 데이터를 읽어 분리연결법을 새롭게 구성해야 하는 문제가 있다. 따라서 HashMap에 저장될 데이터의 개수를 예측할 수 있다면 이를 생성자의 인자로 지정하여 불필요한 재구성을 하지 않는 것이 좋다.

 

❗️근데.. 사이즈를 계속 두배로만 늘리면..!

해시 버킷 사이즈를 두 배로만 확장하면 결정적인 문제점이 있다. 해시 버킷의 개수 M이 2^a 형태가 되어 index = X.hashCode() % M 을 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 된다.

즉 해시 함수를 32비트 영역에 고르게 사용하도록 만들었어도 해시 값을 2의 제곱으로만 나누면 해시 충돌이 쉽게 발생할 수 있다.

 

때문에 보조 해시 함수가 필요하다.

 

 

✌️ 보조 해시 함수

index = X.hashCode() % M을 계산할 때 M 값이 소수일 때 index 값 분포가 가장 균등할 수 있지만 M 값이 소수가 아니기 때문에 별도의 보조 해시 함수를 이용하여 index 값 분포가 가급적 균등할 수 있게 해야 한다.

Java 8의 HashMap은 상위 16비트 값을 XOR 연산해 의 보조 해시 값을 구한다.

 

 

🤟 Seperate Chaining(분리연결법)

버킷의 사이즈를 조절해도 충돌은 여전히 일어난다.

분리연결법은 개방주소법에 비해 데이터 삭제의 성능이 좋고, HashMap에 저장된 키-값 개수가 많아졌을 때 개방주소법보다 성능이 좋기 때문에 Java에서는 충돌에 대응해 분리연결법을 사용한다.

 

🥺 자바는 충돌 횟수에 따라 충돌 데이터를 저장하는 방식이 다르다고?

자바는 충돌이 발생할 경우 Seperate Chaining을 연결 리스트로 구현해 충돌에 대응하였다.

그러나 Java 8 부터 데이터의 개수가 일정 이상일 때에는 기존에 사용하던 연결 리스트 대신 트리를 사용한다

 

🧐 그래서 언제, 그리고 왜 연결 리스트 대신 트리를 사용하는데?

 

그 이유는 연결리스트를 탐색할 때의 시간복잡도를 생각하면 간단하다.

 

데이터가 n번 충돌해 연결 리스트의 n번째 노드에 저장된다면 해당 노드 탐색을 위한 시간복잡도는 O(n)이 된다.

따라서 충돌이 많아질수록 효율이 점점 떨어진다. 따라서 일정 충돌 수가 넘어가면 트리 방식을 사용해 성능을 O(log n)으로 개선한다.

 

Java 8 HashMap

Java 8 의 HashMap에 들어가 보니 상수로 기준이 정해져 있다.

 

즉 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 연결 리스트를 트리로 변경하고, 데이터를 삭제해 개수가 6개가 되면 다시 연결 리스트로 변경한다.

 

차이가 1이 아닌 2인 이유는 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 연결 리스트를 반복적으로 변경해 성능 저하가 발생할 수 있기 때문이다.

또, 데이터 개수가 6 이하일 때 연결 리스트로 다시 변경하는 이유는 데이터 개수가 적을 때 트리와 연결 리스트의 최악의 경우 수행 시간 차이가 많지 않고 트리는 연결 리스트보다 메모리 사용량이 많기 때문이다.

 

🤔 그 트리는 어떻게 구현되어 있는데?

자바는 데이터의 일정 충돌 수가 넘어가면 Red-Black Tree로 데이터를 저장한다.

우선 데이터 개수가 많기 전에는 Node 객체로 연결 리스트를 구현했지만 레드블랙트리는 단순 Node 객체로 구현할 수 없기 때문에

1. Node 객체를 treeifyBin 메서드를 통해 TreeNode 객체로 바꾸어준다.

 

2. treeify 메서드를 통해 parent, left, right 필드와 Red-Black Tree 로직을 위한 적절한 값을 넣어준다.

 

 

 

 

 

 

 

 

 

 

 

 

https://esoongan.tistory.com/193

https://d2.naver.com/helloworld/831311

https://javaconceptoftheday.com/initial-capacity-and-load-factor-of-hashmap-in-java/