영암사는 승경이네

필자의 주관적인 생각과 이해를 바탕으로 작성된 글입니다. 잘못된 부분이 있거나 있다면 댓글로 피드백 부탁드립니다!

개요

HashMap은 Key, Value 데이터쌍을 저장하는 자료구조로 익히 알고있다. 속도면에서 장점을 갖고 있어 코딩테스트에서도 많이 활용된다. 도대체 어떻게 생겨먹은 녀석이길래 이렇게 빠른지 알아보자.

HashMap = Hash + Map

Map
Key, Value 쌍으로 이루어진 자료형.
순서를 보장하지 않음.
키는 중복이 허용되지 않음.

Hash
해시 함수를 사용하여 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값

즉, HashMap이란 Map은 Map인데 Hash를 활용한 Map인 것이다.

Map은 어떻게 Key, Value 쌍으로 관리할 수 있을까? 🤔

HashMap을 이해하기 위해선 Map과 Hash에 대해 이해해야한다. 먼저 Map이 어떻게 Key와 Value 쌍으로 관리할 수 있는 이유는 내부적으로 Key와 Value를 담을 수 있는 배열 타입으로 데이터를 관리하고 있기 때문이다.

 먼저 일반적인 배열의 형태를 생각해보자. 인덱스마다 하나의 값을 넣을 수 있는 자료구조인데 Key와 Value를 둘 다 넣는다는 건 말이 되지 않아보인다. 그런데 배열의 인덱스에 Key값을 넣는다면 얘기가 된다. 0이라는 Key에 대한 Value는 010-1111-1111, 1이라는 Key에 대한 Value는 010-2222-2222로 관리한다고 가정한다면 아래와 같이 배열의 인덱스에는 Key 값을 넣어 관리할 수 있다.

배열의 인덱스를 키로 활용한다고? 그럼 Key는 정수만 가능하잖아... 🤔

 그렇다. HashMap의 Key는 정수 뿐 아니라 모든 타입의 인스턴스가 들어올 수 있다. 그럼 인스턴스를 정수로 변환할 수 있다면 어떨까? 그럼 Key로 들어온 모든 인스턴스는 Key로 사용 가능하게 된다. HashMap의 Hash 의미를 여기서 알 수 있다. 키로 들어온 값을 해시함수를 통해 해시화 시키고, 이를 배열의 인덱스로 사용하는 것이다! 여기서 사용되는 해시함수는 들어온 인스턴스의 hashCode() 메서드이다.

그럼 HashMap 은 이렇게 생겼나요? (상상)

hashMap.put("Sim","010-1111-1111");
hashMap.put("Park","010-2222-2222");
hashMap.put("Hong","010-3333-3333");

String 타입의 Key와 Value를 저장하기 위해 String 타입의 HashMap을 생성하고 위 코드를 실행시킨다고 가정해보자. Sim, Park, Hong에 대한 해시 값이 아래와 같다.

지금까지의 설명을 토대로 HashMap의 구조를 상상해보면 다음과 같을것이다. 만약 새로운 Key, Value 쌍이 들어온다면 해시값과 Size 나머지 연산을 통해 구한 인덱스에 Value가 추가될것이다.

갑자기 % Size는 뭐야? 🤔

 Hash Func, 즉 해시함수를 통해 해시 코드를 구하고 이를 Size 로 나머지 연산(실제로는 시프트 연산)을 한다. 나머지 연산을 하는 이유는 배열의 인덱스 중 하나로 매핑시키기 위함이다.

 예를들어 Size가 10인 배열은 0~9까지의 인덱를 갖는다. 해시 값은 hashCode() 메서드 뿐 아니라 부가적인 연산도 함께 수행되어 구해지는데 아래와 같이 큰 숫자의 정수형이 리턴된다.

  만약 3288449라는 값을 배열의 인덱스로 사용한다면 최소 3288449 크기의 배열을 생성해야한다. 메모리를 많이 차지할것이다. 때문에 이 값을 배열의 Size로 나눈 나머지를 구하고 이를 Index로 사용하는 것이다. 만약 HashMap 내부 배열 Size가 10이라면 3288449 % 10 = 9. 즉 9라는 인덱스를 갖게 된다.

실제로는 이렇지 않아요. 배열은 배열인데 Node 타입의 배열이랍니다. 🤭

실제로 데이터가 저장되는 곳은 제네릭 타입, Object 타입의 배열일까? 모두 아니다 Node 타입의 배열에 저장된다. HashMap에 선언된 Node 타입 변수 및 클래스이다.

transient Node<K,V>[] table; // hashMap 클래스 내에 선언되어있어요

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    
    ...
    
}

 멤버필드로 hash, key, value, nextNode 가 존재한다. 사실 Index와 Value로만 Key, Value 쌍을 관리하면 문제가 많다. 해시가 충돌될 경우 처리도 못하고, 리사이징과 해시 재배치 시 문제가 된다. (문제가 되는 이유는 아래에서 설명하도록 하겠다!)

Index랑 value 만 관리하면 될 줄 알았는데 아니네요? 🤔

hash, key, value, nextNode 필드를 갖는 Node 타입의 인스턴스로 관리되는 이유를 HashMap의 리사이징과 재배치, 충돌 우회 전략과 함께 이해해보자.

리사이징

리사이징
새로운 길이의 배열을 생성한 후 데이터를 이관시킴으로써 결과적으로 배열의 사이즈를 변경시키는 작업

 배열의 사이즈는 초기화 시 정해진다. 기본 생성자를 통해 HashMap을 생성한 후 put 메서드를 실행하면 기본사이즈인 16 사이즈의 Node 배열이 생성되고 리사이징 임계 값으로 12(0.75*16)가 결정된다. 여기서 리사이징 임계값이란 배열을 리사이징하는 기준값을 뜻하며 현재 배열길이의 두 배로 리사이징한다. 12개를 초과할 경우 배열을 16의 2배인 32 사이즈로 리사이징 하는것이다.

  ArrayList도 내부적으로 배열을 사용하고, 배열에 더 이상 들어갈 공간이 없을 경우 현재 사이즈의 절반 사이즈를 추가한 새로운 배열로 리사이징하는데 이와 같은 이치이다.

재배치

재배치
배열의 사이즈가 변경될 때 기존 데이터들의 Index를 재배치하는 작업

 리사이징과 이어지는 내용이다. 리사이징을 할 경우 두 배 사이즈로 배열을 재생성하고 데이터를 이관시킨다고 했다. 이는 기존에 저장되어 있던 Node들의 Index가 재배치되어야 함을 의미한다. Index를 구하는 공식은 hashCode % Size 이므로  Size가 바뀐다면 Index도 바뀌어야하기 때문이다. 예를들어 사이즈가 10 일때 해시값 5755151를 통해 구한 Index는 1이지만, 사이즈가 20일 경우 Index는 11이 된다.

Node에서 hash 값이 관리되는 이유

 이 재배치 작업 때 해시 값을 가져와 연산을 해야하는데 해시 값을 hash에 저장해놨기 때문에 나머지 연산만 하면 된다. 만약 해시 값이 없다면 해시 값 추출을 위해 존재하는 데이터 수 만큼의 해시함수 연산을 해야할것이다.

충돌 우회 전략 - Separate Chaining

 지금 Index 기반으로 값을 넣고 있는데 과연 Index가 충돌할 확률은 대략적으로 어느정도일까? 사이즈에 대한 나머지를 Index로 사용하므로 배열 사이즈가 20이라면, Index가 중복될 확률은 최소 20분의 1이 된다.

어찌됐든 충돌이 일어날 수 있는 상황이다. HashMap은 이런 충돌에 대한 우회 전략으로 Separate Chaining 방식을 사용하며, 이 전략을 위해 nextNode를 사용한다.

Separate Chaning 
동일한 해시값이 이미 존재할경우 LinkedList로 관리한다. 즉, Node에 있는 필드 중 nextNode를 활용하여 중복된 해시 값에 대한 Value를 관리하는 것이다.

 그런데 만약 동일한 Key 값이 들어왔다면 어떨까? Sim이라는 Key값이 들어있는 HashMap에 Sim이라는 Key 값으로 다른 Value를 넣는 것은 전혀 문제되지 않는다. 이 경우 Index에 대한 Value가 덮어씌워져야한다. 즉, 동일한 Key가 들어왔는지를 확인하려면 Index 값만 비교하는 게 아니라 실제 Key 값도 비교해봐야한다.

Node에서 key, nextNode 값이 관리되는 이유

  동일한 Key가 들어왔는지 확인하고, Linked List 형태로 우회하는 Separate Chaining 전략을 사용하기 위해 key와 nextNode가 관리된다.

Separate Chaining 동작원리

 해시함수로 해시값을 구하고 나머지 연산으로 추출한 Index 가 충돌할 경우를 가정했다.

충돌이 일어나면 들어온 Kim에 대한 해시 값과 키 값을 충돌한 Node의 값과 비교한다. 다를 경우 Separate Chaining 전략에 따라 key, value, hash, nextNode를 갖는 Node 인스턴스를 생성하여 NextNode에 할당한다. 만약 비교한 Key와 Hash 값이 같았다면 중복된 Key가 들어온 것이므로 해당 Node의 Value 값을 새로 들어온 Value 값으로 수정한다.

그럼 NextNode에 추가된 Kim을 조회할 땐 어떻게 동작할까?🤔

NextNode에 추가된 Kim에 대한 Value 값 조회를 시도하면 다음 과정을 수행하게 된다.

1. Hash Func % Size 연산을 통해 Index를 구한다.

2. Index 에 매핑된 노드가 존재하는지 확인한다.

3. 매핑된 노드가 존재하므로(충돌) 해당 노드의 Key, Hash 값과 요청으로 들어온 Key, Hash 값을 비교한다.

4. Kim과 Sim의 Key와 Hash 값이 다르므로 해당 노드의 nextNode가 있는지 존재한다.

5. nextNode가 존재하므로 해당 Node를 참조한다.

6. nextNode에 저장된 Key와 Hash 값이 들어온 Key와 Hash 값과 일치하므로 이 노드에 대한 Value 값을 리턴한다.

내부 구조를 이해한 후 다시 생각해본 HashMap의 장점 

1. 조회가 빠르다.

조회 시 Key 값에 해시 및 나머지 연산만 하면 Index를 구할 수 있고, Index 기반으로 접근하니 당연히 조회 속도가 빠를수밖에 없다.

2. 저장, 삭제도 ArrayList보다 빠르다.

저장은 Key에 대한 Index를 구한 후 값을 넣기만 하면 되고, 삭제도 Key에 대한 Index를 구하고 삭제하면 된다. ArrayList의 경우 순서를 유지해야 하기 때문에 중간에 값을 삭제할 경우 빈자리를 채우기 위한 이동 연산이, 등록할 경우 빈자리를 만들기 위한 이동 연산이 수행되어야하는데 말이다.

내부 구조를 이해한 후 다시 생각해본 HashMap의 단점

1. 너무 많은 저장이 일어날 경우 오히려 속도가 느려진다.

 저장이 많아지면 그만큼 리사이징과 재배치작업이 많아지기 때문이다. 만약 저장해야할 데이터가 많다면 HashMap의 사이즈를 너프하게 잡는것도 좋은 방법이다.

1. 개요

 이전 포스팅에서 테스트 코드를 통해 두 클래스를 비교한 결과 다음과 같은 정보를 얻을 수 있었다.

오늘 알아볼 것은

첫째, 생성한 DefaultHttpClient에서 execute를 2번 이상 실행했을 때 즉, HTTP 통신을 2번 이상 요청했을 때 예외가 발생한 원인과 생명주기.

둘째, CloseableHttpClient의 ConnectionPool 설정 정보를 jar 파일을 통해 알아보겠다.

2. DefaultHttpClient

jar파일과 예외 로그를 기반으로 코드를 찾아가보니 다음과 같은 부분에서 예외가 발생함을 확인하였다.

conn이라는 값이 null이 아닐 때 위 에러가 발생한다. conn은 ManagedClientConnectionImpl 형의 멤버필드였으며, 어디선가 주입이 된것같은데... 결론은 찾을 수가 없었다. 멍청한자식.

서치를 통해 얻은 정보를 정리한 결과 예외 발생 원인은 다음과 같았다.

DefaultHttpClient 객체를 생성하면 내부적으로 basicClientConnectionManager 인스턴스가 주입된다. 이 인스턴스는  HTTP 통신에 대한 커넥션 정보를 저장하고 있다. 단, 하나의 최초 연결한 하나의 커넥션 정보만 저장한다.

두 개의 커넥션을 연결하려 했기때문에 예외가 발생했으며, 실제 에러 로그를 확인해보니 basicClientConnectionManager 클래스의 메서드 안에서 발생함을 확인할 수 있었다.

아래 로그의 Asserts.java:34가 위 코드 사진의 첫번째 빨간 블럭부분이었다. (기존 커넥션 정보가 있기때문에 발생)

정리하면 DefaultHttpClient 클래스는 하나의 HTTP 통신만을 처리할 수 있도록 내부적으로 구현되어져 있다.

만약 이 인스턴스를 사용해 두번의 통신을 처리하고싶다면 두개의 인스턴스를 생성해야한다.

3. CloseableHttpClient

생성자를 찾아가보니 다음과 같은 코드가 있었다. httpClientBuilder.create().build(). 요녀석을 파헤쳐보자

create().build() 메서드 확인 결과, PoolingHttpClientConnectionManager를 생성한 후 connectionManager로 사용하는 것이 보인다.

생성된 ConnectionPool의 Default maxTotal, maxConPerRoute는 다음과 같이 2, 20임을 확인할 수 있다.

커스텀을 하지 않고 사용할 경우 최대 커넥션 개수가 2개이기때문에 실제 서비스를 운영하기엔 문제가 있다.

PollingHttpClientConnectionManager 은 커스텀이 가능하다. 때문에 상황에 맞게 커스텀하여 CloseableHttpClient를 구현한다면 많은 HTTP 통신 요청을 필요로 하는 서비스에 적절하게 사용될 수 있다.

4. 마치며

DefaultHttpClient와 CloseableHttpClient에 대한 아~주 미세한 차이에 대해서도 몰랐었지만, 이번 스터디를 통해 차이점은 물론이며, 실제 서비스에 왜 저 클래스를 사용했는지도 이해하게 되었다.

DefaultHttpClient의 생명주기, 언제 connection이 끊어지는지에 대해서는 확인하지 못해 뭔가 깨림직한 기분이지만, 오늘하루도 잘 보냈음에 위안을 삼는다!

1. 개요

 예전에 서비스 내에서 HTTP을 사용해 HR 시스템에서 정보를 가져오는 로직에 문제가 발생한 적이 있었다.

 원인은 사용하는 HttpClient객체가 static으로 선언되어 있어 멀티 쓰레드 환경에서 통신이 꼬여버린 것이다.

 해결방안으로 HttpClientBuilder를 사용해 PoolingHttpClientconnectionManager, requestConfig 객체를 주입받은   CloseableHttpClient 객체를 싱글톤으로 등록 후 호출할때마다 재사용하는 방식을 사용했다.

 그런데 다른 프로젝트의 SM업무를 맡던 도중 HTTP 통신할때마다 DefaultHttpClient 객체를 생성하고 있었다. 또한 인스턴스를 통신할때마다 생성하는 부분은 있지만 close시키는 부분이 없어서 DefaultHttpClient가 어떤녀석인지, 그리고 CloseableHttpClient와 무슨 차이점이 있는지 궁금해졌다.

2. CloseableHttpClient와 DefaultHttpClient

  이 두 클래스 모두 HttpClient 인터페이스의 구현클래스이다. 하지만 이녀석들의 차이에 대해 상세하게 정리된 내용을 찾지못해 실제 테스트를 통해 알아보기로 했다.

2.1. DefaultHttpClient, CloseableHttpClient 테스트코드 1.

 각각의 클래스에 DefaultHttpClient, CloseableHttpClient 인스턴스 생성 후 HTTP GET 통신을 하는 코드를 작성하였다.

2.2. CloseableHttpClient

DefaultHttpClient를 사용하여 HTTP GET 통신을 하는 코드이다.

17번째 라인부터는 응답 데이터를 읽어오는 부분인데 네이버 홈페이지 코드가 방대하게 나와서 굳이 출력하진 않았다.

중요한건 DefaultHttpClient 인스턴스를 사용해 HTTP 통신을 한번 했다는 점이다.

2.2. CloseableHttpClient

 CloseableHttpClient를 사용하여 HTTP GET 통신을 하는 코드이다.

마찬가지로 16번째 라인부터는 응답 데이터를 읽어오는 부분이다.

여기서도 중요한건 CloseableHttpClient 인스턴스를 사용해 한번 통신했다는 점이다.

2.3. 첫번째 테스트로 인해 알게된 차이점

 첫번째 테스트로 인해 알게된 이 두 클래스의 차이점을 정리해보았다. 생성방식이 달랐고, CloseableHttpClient 클래스는 close 메서드가 있었다. 왜 있지?? 아직까지는 큰 차이를 느끼진 못해 다음 테스트를 진행하였다.

3.1. DefaultHttpClient, CloseableHttpClient 테스트코드 2.

 close라는 부분이 눈에 밟혀 각각의 인스턴스에서 HTTP 통신 메서드인 execute를 두번씩 호출해보았다.

3.2. DefaultHttpClient

13번 라인과 17번 라인에 호출 및 응답 코드를 출력하는 코드를 추가하였다.

실행 결과 다음과 같은 Exception이 발생하였다.

예외 메시지는 "연결이 여전히 할당되어 있습니다. 다른 연결을 할당하기 전에 연결을 해제해야 합니다." 라는 뜻이다.

12번 라인에서 수행된 연결이 아직 끊기지 않은 상태에서 13번 라인의 execute 코드가 실행되어 그런 것같다. 그렇다면 과연 언제 끊기는 걸까? 생명주기가 궁금해졌지만 이는 더 파고들어야 알수있을 것 같다. 일단 여기서 확인된 점은 DefaultHttpClient 클래스는 생명주기가 끝나기 전까지 한번의 HTTP 요청을 수행할 수 있다는 것이다.

3.3. CloseableHttpClient

마찬가지로 11, 15번 라인에 통신 및 응답코드를 출력하는 코드를 추가하였다.

실행 결과, 예외가 발생하지 않으며, 두 요청 모두 response Code 200을 응답받았다.

그렇다면 이 CloseableHttpClient의 생명주기는 어떻게 될지가 궁금해졌다. 마침 close 메서드도 있으니 추가 테스트를 진행해보았다. 그런데 예상치 못한 예외 코드가 출력되었다.

3.4. CloseableHttpClient close()

커넥션 풀이 종료됐다는 예외였다!

아. 생성한 CloseableHttpClient 인스턴스는 기본적으로 커넥션 풀을 지원한다는 것을 알게되었고, close 메서드는 이 인스턴스에 할당된 커넥션 풀을 close 시키는 것이었다.

3.2 테스트에서 2번을 연속으로 호출했을 때 예외가 발생하지 않았던 이유도 요청을 커넥션 풀을 통해 요청이 처리되기 때문이었다.

3.4. 두번째 테스트로 인해 알게된 차이점

이제 DefaultHttpClient에서 발생했던 예외의 원인과 생명주기는 무엇이고, CloseableHttpClient의 커넥션 풀이 어디서 설정되는지 확인해야한다. 이는 생성부분의 내부 코드를 확인해야한다.

이는 다음 포스팅에 정리하도록 하겠다.

- 혹, 글의 내용 중 맞지 않는 부분이나 수정할 사항이 있다면 꼭 댓글 부탁드립니다. 정말 감사히 받아드리겠습니다!