컬렉션 프레임워크(컬렉션 API)_Map 계열 [2/4]

List 계열은 이해하기 어렵지 않으니 따로 정리하지 않겠습니다. 컬렉션 프레임워크 및 각 계열의 특징은 이전 글을 참조 부탁드립니다.

 

2019/12/10 - [JAVA/기본 문법] - 컬렉션 프레임워크(컬렉션 API)_기본 개념 [1/3]

2019/12/11 - [JAVA/라이브러리(API)] - java.util.HashMap 클래스의 주요 메소드 [1/1]

2019/12/11 - [JAVA/라이브러리(API)] - java.util.TreeMap 클래스의 주요 메소드 [1/1]

 

---

 

[ HashMap / HashTable ]

• 해시 테이블(Hash Table)을 이용한 검색 구조 사용
• HashMap은 HashTable의 신버전 클래스라고 볼 수 있음
• 차이점은 HashMap은 동기화 처리가 불가능하고 HashTable은 동기화 처리가 가능함
• 또한 HashMap은 null값을 저장할 수 있지만 HashTable은 null값 저장 시 오류 발생

해시 테이블이란 일종의 카테고리와 같다고 할 수 있습니다. 무작위의 데이터가 입력될 때, 검색 효율성을 높이기 위해서는 체계적으로 분류를 해서 구역을 나눠두는 것이 좋습니다. 해싱(Hashing) 기법을 통해 일정한 구획을 나눠둔 것을 해시 테이블이라고 합니다. 

 

아래와 같이 키 값을 해싱하는 규칙이 아스키코드라고 가정해보겠습니다. 그럼 일단 해싱된 값을 가지고 해시 테이블에 지정된 카테고리에 저장을 합니다. 그럼 나중에 "a : 사과" 라는 값을 찾을 때는 배열처럼 순서대로 모두 검색하는 것이 아닌, 해시테이블의 90번 카테고리 안에서만 검색하면 됩니다. 무작위로 입력된 데이터들을 해싱 기법을 통해 분류해서 저장한 후 검색 시에도 이를 활용하는 것입니다.

 

이러한 해시 테이블을 이용한 검색 효율을 높이는 방법은 지금까지도 꾸준히 연구되어 개선되고 있다고 합니다.

 

 

---

 

[ TreeMap ]

• 이진 트리 구조로 정렬해나가며 데이터를 저장
• 정렬된 트리구조이기 때문에 검색 속도가 빠름

C언어에서 다뤘던 이진트리 또는 힙트리와 같이, 트리 구조를 통한 정렬로 검색 효율을 높이는 방식입니다. 

 

아래와 같이 루트(root) 노드부터 시작해서 키를 기준으로 해당 노드보다 작으면 왼쪽, 크면 오른쪽에 저장해 나갑니다. 검색할 때는 키값을 기준으로 크고 작음을 비교해가며 검색해나갈 수 있기 때문에 전체를 모두 검색하는 방식에 비해 빠른 속도를 가질 수 있습니다.

 

만약 "o : 오렌지"를 검색하게 되면 처음 "g : root"보다 크므로 오른쪽 노드로 가고, 다음 노드인 "p : 파인애플"보다 크므로 다시 오른쪽 노드로 가서 찾습니다. 6개의 데이터가 있지만 2번의 연산만으로 찾을 수가 있게 됩니다.

 

 

---

 

C언어 알고리즘에서 힙트리나 이진트리를 구현했듯이 컬렉션 프레임워크 자료구조 또한 직접 구현하지 못할 이유는 없습니다. 다만 만들어져 있는 자료구조와 알고리즘을 편리하게 가져다 사용하자는 객체지향언어의 사상이 잘 반영돼 있는 것 같습니다.