요새 이것 저것 코드를 보면서 궁금했던 점을 하나씩 채워나가고 있습니다. 그 중 하나는, LinkedHashMap입니다. 사용 방법은 많이 나와 있으니, 여기에서는 따로 언급하지 않겠습니다. 이 글에서는 HashMap과 다른 점이 무엇인지 보면서 어떤 자료구조가 어떤 연산에서 상대적으로 오버헤드가 많이 걸리는지 분석해 보도록 하겠습니다.
먼저 hashMap입니다.
간단하게 "AA", "AE", "BA", "BE", "DA"를 넣고, hashMap에 있는 모든 키를 순회하면서 출력하는 예제입니다. HashMap의 구조를 그려보면 아래와 같습니다.
삭제를 하기 위해서, 각 버킷에서 해당 Key를 찾아서 remove를 할 겁니다. 그리고 insert 연산을 수행하기 위해서 Key가 어느 번호의 버킷에 들어가는지를 찾은 다음에 순회해서 Key가 있는지를 알아낸 다음에, 없으면 해당 버킷의 맨 뒤에 추가할 겁니다.
이런 식으로요. 즉, 삽입, 삭제 등을 하는 데 걸리는 시간은 key가 있는 위치까지 찾아가는 데 걸리는 시간 + a가 되겠습니다.
이제, nextNode가 호출이 되면 어떻게 될까요?
Exception이 떨어지는 부분을 제외하고 봅시다. 1445번째 줄부터 1446번째 줄까지가 핵심입니다. table은 hashTable을 지칭합니다. 일단, 현재 1번 버킷의 Key1을 가리키고 있는데, 다음 원소가 Key3이라면, Key3을 리턴하면 됩니다. 문제는 그렇지 않은 경우인데요.
현재 k3 뒤에 걸려있는 노드가 없습니다. 따라서, 다음 버킷부터 탐색 합니다.
2번째 버킷에 걸려있는 것이 없네요. 그러면 3번 버킷으로 갑니다.
key5가 걸려있네요. 따라서 key5를 리턴합니다. 중요한 것은 전체 키를 탐색한다면, 최악의 경우에 버킷 갯수 + 키 갯수만큼 탐색을 한다는 것인데요. HashMap의 load factor는 0.75입니다. 이 말인 즉슨, 키 갯수/버킷 갯수가 0.75를 넘어가면 2배로 확장한다는 이야기입니다.
적당히 키/버킷수 = 0.75라고 하면 키 갯수가 n개 있을 때, 버킷은 1.33n개가 있습니다. 2.33n만큼 탐색을 하게 되겠군요. 즉, 순회를 할 때 비어 있는 버킷도 탐색하는 오버헤드가 있습니다. 그러면 실행 결과는 어떻게 나올까요? 넣은 순서대로 Key가 출력될까요? 당연하게도 아닙니다.
어떤 버킷에 들어가느냐에 따라 iter로 탐색할 때 상대적으로 불리한 위치에 갈 수도 있기 때문입니다.
이제 LinkedHashMap을 보겠습니다.
프로그램을 위와 같이 바꾸고 디버그를 돌려보겠습니다.
HashMap의 putVal은 내부적으로 newNode라는 메서드를 호출합니다. 쭉 따라가 보겠습니다.
LinkedHashMap 안에 들어왔는데요. 이는, LinkedHash~가 HashMap을 상속받았기 때문입니다.
LinkedHashMap 안에 있는 newNode를 호출합니다. 257번째 줄이 눈에 보입니다.
super 메소드가 있네요. 그리고 뭔가 더 있다는 것을 알 수 있습니다. before하고 after입니다.
이걸 그림으로 다시 그려보면 위와 같습니다. before하고 after가 있는데요. 이들은, Double Linked List를 구현하는 데 쓰입니다. List를 직접 구현할 때, 이 둘에 pointer를 집어 넣을 건데, Java에서는 참조 변수를 넣을 겁니다. 정말 그런지, linkNodeLast를 보겠습니다.
정말 그렇네요. 보시면, p의 before에 last를 넣고, last의 after에 p를 넣는데요.
연결은 요래 할 겁니다. 노란색은 새로 추가된 Node를 의미합니다. HM.entry에 들어있는 next와 역할이 다릅니다. HM.entry의 next는 버킷 내에 있는 원소들을 연결할 때 next를 의미합니다. before하고 after는 Double Linked List의 연결 고리들을 의미합니다.
이는 LHM안에 있는 head와 tail을 봐도 알 수 있습니다. 정리하면, 흔히 HashMap에서 Node를 추가하는 것처럼 노드를 추가한 다음에, LinkedList에 따로 데이터를 넣습니다. <K, V>를 저장하기 위해 필요한 공간도 커졌고, 처리해야 하는 작업도 많아졌습니다. 이는, 삭제, 삽입 처리를 해도 마찬가지일 겁니다.
그리고 space 자체가 커졌기 때문에, 안 그래도 안 좋은 locality가 더 좋아지지는 않을 겁니다.
그런데, next 메서드는 다릅니다. next 메서드를 보겠습니다.
내부에서 nextNode 메서드를 호출합니다.
e.after의 값을 next에 넣고, e를 리턴한다. LinkedList를 순회하기 때문에 간단합니다. HashMap은 어땠나요? 버킷도 돌아야 하고, 전체 키도 보아야 합니다. 그에 비하면 LHM은 순회할 때 그냥 있는 키들만 보면 됩니다.
LHM의 대략적인 구조를 보면 위와 같습니다. k1, k2, k3, k4는 추가된 키의 순서입니다. 그리고 순회할 때에는, LHM은 내부에 있는 리스트를 가지고 돕니다. 그리고 내부에 있는 이 '자료구조'는 들어온 순서를 유지하기 때문에..
AA, AE, BA, BE, DA 순으로 출력이 됩니다. 따라서 들어온 키들의 순서를 유지해야 할 때에는 LinkedHashMap을 고려해야 합니다.
'레퍼런스 > 분석' 카테고리의 다른 글
| 자바 arrayList addAll 메서드 : 어디서 오버헤드가 걸리는지 간단하게 분석해 봅시다. (4) | 2020.06.04 |
|---|---|
| 같은 것 같지만 다른 java map get vs containskey (4) | 2020.05.26 |
| java split 메소드 : stringtokenizer보다 항상 느릴까요? (2) | 2020.05.20 |
| java의 String은 이모지를 어떻게 저장할까요? (4) | 2020.04.20 |
| java synchronizedmap : 데이터가 포장된 잠금 객체 (2) | 2020.04.11 |
최근댓글