출처
http://www.mungchung.com/xe/protip/3484
http://withwani.tistory.com/150
HashTable implements Map
자바 1.1버전부터 사용되왔던 자료구조 클래스로 Map 인터페이스를 확장한다.
-키값의 중복을 허용하지 않는다
-key와 value 쌍으로 데이터를 저장한다
-FILO의 스택과 같은 구조로 저장되어있다. 마지막 넣은 항목이 index 0
-입력 : put(키,값)
-값 가져오기 : get(키)
HashMap implements Map
1.5버전부터 도입된 자료구조로서 헤시테이블과 그 기능이 유사하나
무조건적으로 동기화 되는 헤시테이블과 비교되어 상황에 따라 더욱 가볍게 사용할 수 있다.
-해시테이블과 다르게 FIFO 의 구조로 데이터가 저장된다. 처음 넣은 항목이 index 0
-나머지는 동일
TreeMap implements Map, SortedMap
1.5버전 이후로 도입된 자료구조
-SortedMap을 확장하여 key값에 의한 정렬이 가능하다.
-key값에 의해 자동 정렬 된다.
AVA에서 기본적인 자료 구조를 제공하기 위한 환경을 JAVA Collection Framework라고 한다.
다음은 JAVA Collection Framework의 상속 기본 구조이다.
|
- Collection
Collection 인터페이스를 상속받아 List와 Set 인터페이스가 된다. List는 순서가 있는 Collection, 그리고 List는 Data 중복을 허락한다. 하지만 Set은 순서의 의미가 없으며 Data를 중복해서 포함할 수 없다.
- List 인터페이스의 특징
- 순서가 있는 Collection.(이 순서는 삽입된 순서를 의미한다.)
- Data를 중복해서 포함할 수 있다.
- Stack의 특징
- Data의 삽입과 추출이 후입선출(Last-In First-Out) 구조로 되어 있다.
- push() method : Data 삽입할 때 사용
- pop() method : Data 추출할 때 사용
- peek() method : 추출할 Data를 삭제하지 않고 Data만을 가져 올 때 사용
- search() method : Stack으로부터 Data를 검색할 때 사용
- Vector의 특징
- 자동으로 동기화를 보장해준다.
- ArrayList에 동기화가 보장되도록 최적화한 클래스이다.
- JAVA 5.0 이 후로는 AutoBoxing/AutoUnBoxing을 지원한다.
- AutoBoxing이란? 기본 Data 타입을 Wrapper 클래스형의 객체로 자동으로 변환해주는 기능. AutoUnBoxing은 AutoBoxing의 반대 개념
- JAVA 1.4까지
Vector v = new Vector(); |
- JAVA 5.0이후
Vector v = new Vector(); |
- addElement() method : Data를 삽입할 때 사용
- elementAt() method : Data를 추출할 때 사용, Index에 해당하는 객체를 얻어냄
- size() method : Vector 내에 존재하는 객체의 수를 얻어낼 대 사용
- insertElementAt() method : Vector 내에 중간 삽입할 때 사용
- setElementAt() method : Vector 내에 존재하는 Data를 수정할 때 사용
- indexOf() method : Vector 내에 Data를 검색할 때 사용, Index를 반환
- contains() method : Data의 존재 유무를 알기 위해 사용.
- ArrayList의 특징
- 동기화를 보장해주지 않는다.
- 배열에 동적 메모리 증가 기능을 구현한 클래스이다.
- 동기화 지원 방법 : List list = Collections.synchronizeList(new ArrayList(…));
- add() method : Data 삽입할 때 사용
- get(0 method : Data 추출할 때 사용
- toArray() method : ArrayList로부터 배열 얻어낼 때 사용
- contains() method : Data의 존재 유무를 알기 위해 사용
- size() method : ArrayList의 요소 개수를 얻어낼 때 사용
- Set 인터페이스의 특징
- 집합적인 개념의 Collection
- 순서의 의미가 없다.
- Data를 중복해서 포함할 수 없다.
- HashSet의 특징
- add() method : Data 삽입할 때 사용
- next() method : Data 추출할 때 사용
- HashSet의 Data 추출은 Iterator을 이용하면 된다. Iterator는 Collection내의 모든 Data에 접근할 수 있는 특징이 있다. 그리고 Data의 마지막에 상관하지 않고 검색하기 위한 인터페이스이다. Set의 Iterator() method로 Iterator를 얻어 낼 수 있으며, Iterator의 hasNext() method를 이용해서 Data 끝을 만날 때까지 next() method를 호출해서 Data를 추출할 수 있다.
Iterator<String iter = set.iterator(); System.out.print(temp + ", "); |
- remove() method : Data를 삭제할 때 사용
- contains() method : Data의 포함여부를 알기 위해 사용
- size() method : HashSet의 요소 개수를 얻어낼 때 사용
- Map
List와 Set이 순서나 집합적인 개념의 인터페이스라면 Map은 검색의 개념이 가미된 인터페이스이다. Map 인터페이스는 데이터를 삽입할 때 Key와 Value의 형태로 삽입되며, Key를 이용해서 Value를 얻을 수 있다.
- Hashtable, HashMap의 공통점
- 내부적으로 모두 Hash 기법을 이용한다.
- Map 인터페이스를 구현하고 있다.
- Key와 Value를 이용해서 Data를 관리한다.
- Hashtable, HashMap의 차이점
- Hashtable은 동기화가 보장된다.
- HashMap은 동기화가 보장되지 않는다.
- HashMap의 동기화 지원 방법 : Map m = Collections.synchronizedMap(New HashMap(…));
- Hashtable, HashMap과 HashSet과의 관계
- Hashtable과 HashMap은 둘 다 Map 인터페이스를 구현하고 있다.
- HashSet은 내부적으로 Hash기법을 사용하지만 Set인터페이스를 구현하고 있다.
- HashMap
- 객체 생성 : Map<String, Integer> map = new HashMap<String, Integer>();
- put() method : Data 삽입할 때 사용
- get() method : Data를 추출할 때 사용, argument값은 Key를 사용
- Hashtable
- 객체 생성 : Hashtable<String, Object> h = new Hashtable<String, Object>();
- put() method : Data 삽입할 때 사용
- get() method : Data를 추출할 때 사용, argument값은 Key를 사용
- Sorted
Set과 Map 인터페이스를 상속받아 정렬 기능이 추가된 SortedSet과 SortedMap 인터페이스가 된다. 그리고 이들은 각각 TreeSet 클래스와 TreeMap 클래스로 구성된다. TreeSet과 TreeMap은 Set과 Map의 기능을 가지고 있으면서 정렬 기능이 가미되었다는 것이 특징이다.
- Sorted를 지원하지 않는 클래스
- HashSet, HashMap
- Sorted를 지원하는 클래스
- TreeSet, TreeMap
- TreeMap
- Key와 Value로 Data를 관리
- Key를 기준으로 오름차순으로 정렬된다.
- Map 인터페이스를 상속한 SortedMap 인터페이스를 구현한 클래스
- TreeSet
- Set 인터페이스를 상속한 SortedSet 인터페이스를 구현한 클래스
- 데이터들이 자동으로 오름차순으로 정렬된다.
- Comparator
- TreeSet과 TreeMap은 사용자가 직접 정렬의 방식을 지정할 수 있다.
- TreeSet과 TreeMap은 정렬을 위한 Comparator 인터페이스를 구현하면 된다.
- TreeSet에 Data를 집어 넣으면 기본적으로 오름차순(Ascending) 정렬이 되지만 그것도 문자열이나 기본 데이터 타입과 같은 단순한 것에만 해당된다. 이에 사용자가 직접 비교법을 넣어주기 위해 사용하는 것이 Comparator 인터페이스이다.
- Comparator의 구현 방법 : Comparator 내부에 compare() method를 구현하면 된다.
class Mycomparator<T> implements Comparator<T> { |
- Comparator가 추가된 TreeSet의 생성
TreeSet<Score> tset = new TreeSet<Score>(new MyComparator<Score>()); |
- Comparator가 추가된 TreeMap의 생성
TreeMap<Score, String> tset = new TreeMap<Score, String>(new MyComparator<Score>()); |
- 일반적인 정렬기능의 사용
- HashSet이나 HashMap을 정렬 기능이 지원되는 TreeSet이나 TreeMap으로 변환해서 사용
- HashSet을 이용한 TreeSet 생성
Set<String> set = new HashSet<String>(); |
- HashMap을 이용한 TreeMap 생성
Map<String, Integer> map = new HashMap<String, Integer>(); |
'~ 2014 > 자료구조 & 알고리즘' 카테고리의 다른 글
| [알고리즘] B트리, B+트리 (1) | 2014.06.15 |
|---|---|
| [알고리즘] 이진탐색트리 (0) | 2014.06.15 |
| [알고리즘] 정렬알고리즘 (선택, 버블, 삽입 / 병합, 퀵, 힙) (0) | 2014.06.15 |
| [자료구조] 배열과 링크드 리스트 (0) | 2014.06.15 |