반응형

 hashMap은 동기화가 된 클래스가 아닙니다. 그렇기 때문에, 두 Thread에서 같은 hashMap에 동시에 접근했을 때, 문제가 발생할 수 있습니다. 둘 다 write 연산을 수행할 때에도 문제가 발생할 겁니다. 그런데, 왜 문제가 될까요? 문제가 되는 시나리오가 없을까요? 그 시나리오는, 당황하면 쉽게 생각할 수 없습니다.

 

 두 Thread가 있습니다. 이 Thread들은, 서로 다른 값의 Integer인, 6개의 Key 값을 넣습니다. 그러면 put 메서드를 실행을 하게 될 건데요. 어떠한 일이 벌어질까요? 저는, 12보다 작아질 수 있다고 답변했습니다. 그 말이 맞을까요?

 


 먼저 hashmap을 간단하게 보도록 하겠습니다.

 

 

 3개의 static 변수만 봅시다. DEFAULT_INITIAL_CAPACITY랑, DEFAULT_LOAD_FACTOR 이 둘만 봅시다. 이 중 전자는, 초기 용량을 의미합니다. 초기 용량을 넣지 않고 생성을 하는 경우, 16의 초기용량이 잡힙니다. 그리고, Load_factor가 0.75인데요. capacity에 0.75를 곱한 값보다, size가 더 크다면 확장이 일어납니다.

 

 이는 putVal 메서드의 이 부분을 보시면 확인할 수 있습니다.

 

 

 이 부분입니다. 그러니, 2개의 Worker가 각각 6개의 서로 다른 Key를 넣는다고 생각해 봅시다. putVal 메서드의 일부분을 보도록 하겠습니다.

 

 

 이 중에서 630번째 줄을 보겠습니다. 무엇을 하나요? hash 값은, Key값의 hash 값을 의미합니다.

 

 

 그러면, Key값이 Integer로 1이였다면, Integer 객체 1의 hashCode 값은 1이 됩니다. tab[~]가 null이라는 것은 버킷 번호가 ~인 것에 어떠한 Key도 들어있지 않은 것을 의미합니다. 630번쨰 줄의 조건입니다. 그럴 때, tab[~]에 무엇을 넣나요? Key값 하나를 연결해 버립니다.

 

 버킷의 초기 갯수는 16개라고 합시다. resize가 일어나서 재분배가 일어나지 않았다면, 16k + 1꼴의 Key값들은 같은 버킷 내에 들어갈 겁니다. 그러면,  resize가 일어나지 않을 정도put 메서드를 조금 호출하고, 같은 버킷 내에만 들어갈 때 상황을 강제해 보도록 하겠습니다.

 

 

 Thread를 상속받은, Worker는 위와 같습니다. run 함수에서, 16000000x + 16i + 1을 넣습니다. x값에 따라서, i값에 따라서 값이 달라집니다만, 중요한 것은 16으로 나누었을 때 나머지가 1인 Key를 넣었다는 것입니다.

 

 

 다음에, 매 테스트 케이스마다, K가 Integer이고, V가 Integer인 HashMap 객체인 h를 선언합니다. 그리고, worker 2개를 생성하는데요. 2번째 인자인 1과 2는, Worker의 x값과 관련이 있습니다. 더 정확하게 말하면, Worker 1이 넣는 수와, Worker 2가 넣는 수를 다르게 하기 위해서 2번째 인자에 1과 2를 넣었습니다.

 

 그러면, 1번째 Worker는 1600만 + 17, 1600만 + 31, 1600만 + 49를 넣을 겁니다. 2번째 Worker는 3200만 + 17, 3200만 + 31, 3200만 + 49를 넣을 겁니다. 정상적으로 넣어졌다면, h.size() 값은 6이 나와야 합니다.

 

 

 그런데 6이 아닌 경우가 있습니다. 왜 그렇게 된 것일까요? HashMap은 동기화 처리되어 있지 않기 때문입니다. 그렇기 때문에, 동시에 write 연산이 들어온 경우에 문제가 생겼을 겁니다. 사실 write가 끼어 있는 경우 문제가 발생할 소지가 많습니다.

 


 동시에 write 연산이 생겼다. 그래서 문제가 되었다. 어떤 시나리오를 생각할 수 있을까요? HashMap의 putVal 메서드를 다시 보겠습니다. 이번에는 조금 더 단순 도식화 시켜 보도록 하겠습니다.

 

 

 if에 걸리는 절을 A, if문이 만족되었을 때, 수행하는 문장, 그러니까 631번째 줄을 B라고 합시다. 이 둘이 원자적인 연산은 아닙니다만,설명을 쉽게 하기 위해, A와 B로 묶도록 하겠습니다. 다시 말하면, A와 B는 원자적이지 않으나, 최선의 상황을 가정한 것입니다. 1번째는, 즉 문장 A는 쉽게 말해서, 어떠한 버킷이 비어있느냐를 검사하는 것입니다.

 

 

 당연하게도, HashMap에 어떠한 키값도 들어가 있지 않은 경우, 임의의 버킷에 달려있는 키는 없을 겁니다. 즉, 버킷은 모두 비어 있는 상태입니다. 스레드 1과 스레드 2가, 630번째 줄의 if문을 수행해야 한다고 해 봅시다. 그리고 현재 t1이 RUNNING 상태라고 합시다.

 

 

 t1이 A를 수행하였습니다. 버킷이 비어 있는 것을 확인했다면, B를 수행할 겁니다. 그런데 이 때, 뜬금없이 t2가 A를 수행합니다.

 

 

 그러면, 이 때도 hashMap에 키값은 없기 때문에 버킷이 비어 있을 겁니다. 그러면 t1과 t2 둘 다 631번째 줄, B를 수행합니다.

 

 

 이 때, 3200만 17이 들어갔다고 해 보겠습니다.

 

 

 그런데, 이 때, t1의 경우에도 B를 수행할 수 있습니다. 왜냐하면, t1이 630번째 줄의 if문을 검사한 시간에는 HashMap에 아무 키도 없었기 때문입니다. 버킷이 비었던 것은 당연할 겁니다. 1600만 17을 넣었다고 한다면, 아래와 같이 될 겁니다. 여기서 중요한 것은, B는, 단지 tab[i] = newNode(~)라는 것입니다. 버킷의 시작 객체만 바꾼다는 것입니다.

 

 

 그러면 이런 식으로 수행이 되었을 때, Bucket의 상태는 아래와 같을 겁니다.

 

 

 32000017은 가비지가 됩니다. 도달 가능하지 않기 때문입니다. 즉, t1이 630번째 if문을 수행해서 참이 되었고, t2가 630번째 if문을 수행해서 참이 된 상태에서, t2가 631번째 줄을 수행하고, t1이 631번째 줄을 수행했을 때, 이러한 일이 발생할 수 있습니다. 분명한 것은 2개의 서로 다른 Key를 추가했는데, 하나만 들어갔다는 것입니다. 당황하면 생각을 하기 어려운 질문 중 하나입니다.

 

 이제 질문을 드리겠습니다. ArrayList가 있습니다. 이것도 동기화된 클래스가 아닙니다. 두 Thread가 ArrayList객체 arr에 동시에 객체 Integer 10개를 add 한다고 해 봅시다. 두 Thread가 작업을 마쳤을 때, arr의 size값은 20이 될까요? 아니면 그것보다 더 작아질 수도 있을까요? 더 작아질 수도 있다면, 그러한 시나리오를 설명해 주세요.

반응형

댓글을 달아 주세요

  1. 상식체온

    문제가 어렵습니다.
    저의 짧은 지식으로는 각각 조건을 달아야할 것같습니다. ^^

    • 코딩강아지
      2020.03.25 20:56 신고

      사실 실행되는 순서가 강제가 되지 않으니..
      발생하는 문제긴 합니다..

      면접으로 나오면 어렵게 되어버리는 것 중 하나더라고요.

  2. dong97

    포스팅 잘 봤어요!!구독 누르고 갑니다ㅎ

  3. 곰곰지영

    여전히 무슨말인지 모르겠지만
    공감 꾹 하구 가용 :)