java의 hashtable 대신에 왜 다른 것을 권장할까요?

 안녕하세요. chogahui05입니다. Java에는 HashTable이 있습니다. hash 기반의 자료구조를 동기화 했다고 생각하시면 편합니다. HashMap과 다른 부분 중 하나입니다. 

 

 

---

 먼저, 주요 필드들을 보도록 하겠습니다.

 

 table입니다. 이는, 무엇을 의미할까요?

 

 

 putVal 함수의 일부분입니다. tab에 table을 넣고 있습니다. 그리고 hash는 key 객체의 hashCode를 의미합니다. 이것과 무엇인가를 연산해서, index라는 값을 만들었습니다. 466번째 줄까지 보았을 때, index는 버킷 번호와 관련이 깊어 보입니다. 그리고 entry 값을 하나 받는데요.

 

 hashtable이나, hashmap은 키의 중복을 허용하지 않는 구조입니다. 그렇다면, 해당 버킷에 key가 있는지를 확인하겠네요.

 

 

 469번째 줄부터 475번째 줄까지가 그러한 일을 수행합니다. 만약에 해당 버킷에 Key가 없으면, addEntry를 호출합니다.

 

 

 rehash가 일어나지 않는다면, 435번째 줄부터 수행하게 됩니다. tab[index]에, <K,V>쌍을 새로 넣습니다. 그리고, e도 같이 넣는데요. 이 e는 다음 객체와 관련된 것으로 보입니다.

 

 

 next가 받는군요. 그러면, put 메소드가 호출되었을 때, 어떠한 일이 발생하는지 그려보겠습니다.

 

 

 먼저, put 메서드가 호출되기 전에, 다음과 같이 HashTable 안에 Key가 있었다고 해 봅시다. 33이라는 키가 들어올 거에요. 그리고 초기 bucket size는 16이라고 가정해 보겠습니다. tab.length는 16이므로, 33은 33을 16으로 나눈 나머지 값인 1번 버킷에 들어갑니다.

 

 

 33이 1번 버킷에 있는지 확인해 보니까, 없습니다. 따라서 addEntry 함수가 호출이 됩니다. 그리고 이 함수는 33을 위한 새로운 Entry를 만듭니다.

 

 

 그리고, 새롭게 만든 노드가, 17을 가리키게 하고, 1번 버킷은 33을 가리키게 합니다. 이것만 보면, HashMap과는 차이가 없어 보이는데. 함수의 선언 부분에 붙어 있는 키워드만 봐도 이야기가 달라집니다.

 

 

---

 주요 메서드들만 보도록 하겠습니다.

 

 먼저 get 앞에 synchronized가 붙어 있습니다.

 

 

 다음에 put에도 synchronized가 붙어 있습니다.

 

 

 remove도 마찬가지입니다. 이 셋을 Thread1이 호출한 경우에, Thread1은 해당 객체, 여기에서는 t라고 하면, t에 대한 lock을 획득합니다. 이 때, Thread2가 t.get을 호출하려고 하면 어떻게 될까요?

 

 

 thread1이 이미 t의 동기화된 메소드에 들어갔고, t2가 동기화된 메소드를 부르려고 하기 때문에, block이 됩니다. 사실 한 스레드가 Write 연산을 수행하고 있는 경우에, 잠근다는 것은 이해가 갑니다. 그런데, 그 대상이 객체 전체라는 것이 문제입니다. 실생활 예제를 들어보도록 하겠습니다.

 

 

 회사에 1:1 회의를 할 수 있는 방이 101개 있다고 해 봅시다. 면접관이 101명 있고, 지원자가 101명 있다고 해 봅시다.

 

 

 1번째 지원자가 회사에 들어온 순간, 다른 지원자는 들어오지 못합니다. 그리고 1번째 지원자는 1번 방에서 면접을 봅니다. 당연하게도 1번이 나올 때까지 2번은 회사에 들어가지도 못할 겁니다.

 

 

 다음에 p2는 100번 방에 들어갑니다. p2가 회사에 들어온 순간, lock이 일어납니다. 여기서 비효율적인 부분을 찾으셨나요? 사실, 내부적으로 resize가 일어날 수도 있는 putXXX 계열은 조심해야 하는 것이 맞습니다. 예를 들어, resize가 일어날 때에는, table 자체의 변경이 일어납니다.

 

 

 그럼에도 불구하고, 비효율적이라는 것은 변하지 않습니다. 여러 개의 방이 있는데도, 한 번에 한 사람밖에 면접을 못 보는 격이기 때문입니다. 언제 회사가 확장 공사를 할 지 모르니, 면접자는 회사에 1명씩만 들어오게 하다니요. 회사가 확장되는 건 '상대적으로 꽤 뜸한 이벤트' 아니던가요? HashTable로 돌아와 보겠습니다. hash 계열 구조는, 보통 버킷을 이용해서 충돌 처리를 합니다.

 

 

---

 그러면 이 상황은 어떤가요?

 

 

 1번 버킷에 33을 추가하고, 5번 버킷에 5를 추가한다. 병렬적으로 수행이 될 수 있는 Task입니다. T1이 1번 버킷에 33을 추가하는 작업을 수행하고, T2가 1번 버킷에 49를 추가한다고 했을 때에는, 동기화를 걸어놓지 않으면 문제가 생길 거에요.

 

 

 T1이 33을 추가하고 있는 상황에서, [1]의 head가 17이라는 정보를 받았습니다. 연결을 하려고 했는데, T2가 끼어들기를 해서, 49를 추가를 했습니다. 그리고, [1]의 head를 49로 바꿨습니다.

 

 

 그러면 이렇게 그림이 그려질 겁니다. head가 49로 업데이트 되었지만, 33이 연결해야 할 정보는 17입니다.

 

 

 다시 T1이 연결작업을 하고 head를 다시 설정하면 이런 식으로 될 겁니다. 같은 버킷에 동시에 write 연산이 들어오는 경우 문제가 생길 수 있습니다. 하지만, 별개의 버킷에 write 연산이 들어오면, 별 상관이 없습니다. 연관 관계가 없기 때문입니다. rehash나 resize와 같이 테이블 전체를 재구축 해야 하는 경우에는 문제가 될 수 있겠지만요.

 

 이러한 연산이 언제 들어올지도 모르는 상황에서 버킷 단위로 lock을 거는 건 상당히 어려울 겁니다. 그럼에도 불구하고, 버킷 단위로 동시에 처리할 수 있다는 점은 생각보다 매력적입니다. 심지어, rehash나 resize는 꽤 적은 빈도로 호출이 되는 이벤트이기도 하고요. ConcurrentHashMap을 고려하는 이유도 이러한 점과 무관하지 않은데요. 나중에 ConcurrentHashMap이 올라온다면, 보실 때, 어떻게 resize나 rehash를 처리하는지를 중점적으로 보시는 것도 도움이 많이 되실 듯 싶습니다.