java hashset : 어떻게 구현이 되어 있을까요?

 java의 hashset은 어떻게 동작할까요? hashmap과 다른 점은 map은 Key로부터 Value를 뽑아올 수 있지만, set은 Key값만을 중요하게 여긴다는 것입니다. 그런데, 뭔가 이상하지 않나요? HashMap하고, Set은 그것 말고는 거의 동일한 기능을 수행합니다. 상식적으로 생각해 보았을 때, HashSet 기능들을 일일히 다 구현을 하는 게 효율적일까요? 아니면 이미 구현된 HashMap의 기능을 이용하는 게 효율적일까요?

 

 후자일 겁니다. 이 정도만 이해하셨다면, 이 글의 90%를 이해하신 겁니다.  나머지 10%는 밑에서 후술하도록 하겠습니다.

 

---

 

 예제 프로그램을 보겠습니다. 간단하게 HashSet hs를 선언했습니다. 이것은 Integer를 Key로 가지는 자료 구조입니다.

 

 

 안에 필드를 보니, HashMap 객체 참조 변수인 map이 있습니다. 그리고 PRESENT라는 뭔가 이상한 필드가 하나 있는데요. 이것이 어디에 쓰이는지는 밑에서 후술을 하겠습니다.

 

 

 생성자를 보면, 새로운 해시 맵 객체를 만들어서 map이라는 참조 변수에 넣는 것을 볼 수 있습니다. 정리를 해 보겠습니다. HashSet은 HashMap 참조 변수를 필드로 가졌습니다. 그리고, 생성자 안에서 HashMap 객체를 새로 만들어서, map 필드에 넘겨주었습니다.. 이것을 그림으로 표현하면 아래와 같습니다.

 

 

 즉, HashSet은 HashMap을 wrapping했다고 이해해도 될까요? 그렇게 이해해도 어느 정도는 맞아 보입니다. 그러면 present라는 것은 왜 있을까요? Map은 K와 V 둘 다 필요합니다. 그런데 셋이기 때문에, 외부에서는, K만 받습니다. 내부에서 맵을 쓰려면, V가 필요한데요. 그 V의 역할을 하는 게 present가 되지 않을까? 라는 추측을 할 수 있습니다.

 

 실제로 그런지 add 메소드를 보겠습니다.

 

 

 map에 Key값과, PRESENT를 넣습니다. 키 값이 들어올 때 마다, PRESENT를 value로 넣습니다. 이제 다시 PRESENT 선언 부분을 보겠습니다.

 

 

 새로운 Object 객체를 만들고 객체의 참조값을 PRESENT에 넣습니다. 이제, Key값 1과 2가 추가되는 상황을 생각해 보겠습니다.

 

 

 먼저 present는 객체 Object를 가리킵니다.

 

 

 1이 추가될 때, Key값이 1, Value값은 Object를 참조합니다.

 

 

 2가 추가될 때의 그림입니다. Key가 1일 때의 Value랑, Key가 2일 때 Value는 같은 Object를 참조합니다. 사실, 이것은 Set이 Key값만 중요하지, Value는 중요하지 않기 때문입니다. 더미 오브젝트를 하나 생성하고, Value 값이 더미를 가리키게 해도 HashSet이 동작을 하는 것에는 문제가 되지 않습니다.

 

 그런데, Set이 생성될 때 마다, 더미 객체를 별도로 생성할 필요가 있을까요?

 

---

 그림을 그려보면 위와 같은 상황입니다. K만 중요하고 V가 중요하지 않은 상황에서는 서로 다른 HashSet 객체가 다른 present, 즉, 다른 더미를 가리키게 할 필요가 전혀 없습니다.

 

 

 더미노드를 가리키는 역할을 하는 PRESENT가 같은 객체를 가리키게 해도 문제가 없음을 알 수 있습니다. 이 특성은 모든 해시셋 객체에 동일하게 적용되도 됩니다. 즉, PRESENT를 클래스 변수로 선언해도 문제가 없습니다. 따라서, PRESENT는 static으로 선언이 되었습니다.

 

 자. 정말 그렇게 설계가 되었는지, 예제 프로그램을 하나 만들어서 돌려보도록 하겠습니다.

 

---

 KIWOOM하고 GIANT 해시맵을 생성하였습니다.

 

  이 프로그램의 의도는 대충 눈치 채셨을 거라 생각하고 진행하도록 하겠습니다. 디버그 포인트를 걸어서 해시셋 2개의 PRESENT가 어떤 값을 가지는지 확인해 보겠습니다.

 

 

 11번째 줄에서 KIWOOM 해시셋에 52를 추가할 때 어떤 일이 일어났을까요?

 

 

 히어로즈의 PRESENT가 id 값이 33임을 알 수 있습니다. 52와 id값이 33인 Object가 들어갑니다.

 

 

 다음에 13번째 줄에서 또 add를 호출하였습니다. Giant에 6번을 추가했습니다. 이 때 PRESENT 값을 보도록 하겠습니다.

 

 

 id값이 33임을 알 수 있습니다. Dummy Value 객체는 모든 셋 객체가 동일하게 가져도 되니, static을 붙인 셈입니다.