Collection 인터페이스를 기반으로 구현한 클래스에는 List와 Set이 있다.
List 클래스는 선형 자료구조를 구현한 클래스
Set은 비선형 자료를 구현한 클래스이다.
Set은 빠른 검색이 필요할 때 사용하는 클래스, 같은 자료를 중복 보관할 수 없다.
선형 자료구조의 탐색 비용은 O(N) 이고, 이진 탐색 트리의 탐색 비용은 (logN),
해쉬 테이블의 탐색 비용은 O(1) 이다.
- HashSet
add, remove, clear, clone, ontains, isEmpty, iterator, size 메소드가 있다.
add메소드는 String 타입의 객체만 저장할 수 있다.
Map 구조와 달리 중복을 허용하지 않는 특징이 있다.
Set 클래스에는 HashSet, TreeSet, LinkedHashSet이 있는데 HashSet이 가장 성능이 좋다.
HashSet은 저장순서를 유지하지 않으므로 저장순서를 유지하려면 LinkedHashSet을 사용해야한다.
List와 비교했을 때 단지 중복자료를 보관할 수 없다는 점 밖에 보이지 않지만
검색 속도에 있어서 엄청난 차이를 보이기 때문에 많은 자료를 관리할 때는 HashSet 클래스를 사용해야 한다.
HashSet으로 작성된 데이터는 값을 저장할 때 인스턴스의 해시값을 기준으로 저장하기 때문에
순서대로 저장되지 않는다. 그래서 순서대로 꺼낼 수 없다.
Iterator를 활용해야 한다.
HashSet set = new HashSet();
set.add(new String("해쉬"));
set.add(new String("해쉬"));
set.add(new String("해쉬"));
Set은 객체를 저장할 때 그 객체에 대해 hashCode() 메소드를 호출한 후 그 리턴 값의 위치를 계산한다.
String 클래스는 같은 값을 갖는 경우 hash value를 리턴하도록 hashCode()를 오버라이딩 했다.
즉, 위의 해쉬라는 String 객체는 인스턴스는 다르지만 value값이 같기 때문에 hashCode()의 리턴값도 같다.
위치 계산 값이 같아서 같은 값으로 간주하기 때문에 중복 저장되지 않는다.
HashSet에서 두 인스턴스가 같게 인식하게 만들어주는 예제
public class equalHashSet{
public static void main(String[] args){
HashSet set = new HashSet();
set.add("abc");
set.add("abc");
set.add(new Person("test",10));
set.add(new Person("test",10));
sysout(set);
}
}
class Person{
String name;
int age;
Person(String name, int age){
this.name = name;
this.age= age;
}
//name과 age가 같으면 true 리턴
public boolean equals(Object obj){
if(obj instanceof Person){
Person temp = (Person) obj;
return name.equals(temp.name) && age == temp.age;
}
return false;
}
public int hashCode(){
return Objects.hash(name, age);
}
public String toString(){
return name + " : " + age;
}
}
HashSet의 add()는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은지 판별하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출하기 때문에 두 메소드를 목적에 맞게 오버라이딩 해야만 한다.
String 클래스에서 같은 내용의 문자열에 대한 equals()의 결과가 true인 것 처럼, Person 클래스에서도 두 인스턴스의 name과 age가 같으면 true를 반환하도록 equals()를 오버라이딩 했다.
오버라이딩을 통해 작성된 HashCode()는 아래와 같은 세가지 조건을 만족해야한다.
실행 중인 어플리케이션 내의 동일한 객체에 대해 여러번 hashCode를 호출해도 동일한 int값을 반환한다.
equals()를 사용해 true를 얻은 두 개체에 대해 각각 hashCode()를 호출해서 얻은 결과값은 반드시 같아야한다.
equals()를 호출했을 때 false를 반환하는 두 객체는 hashCode() 호출에 대해 같은 int값을 반환하는 경우가 있어도 괜찮지만, 해시을 사용하는 컬렉션의 성능을 향상시키기 위해 다른 int 값을 반환하는 것이 좋다.
- TreeSet
TreeSet은 이진탐색트리의 형태로 데이터를 저장하는 컬렉션이다.
이진탐색트리 중에서도 성능을 향상시킨 '레드-블랙 트리'로 구현되어 있다.
따라서 데이터의 추가, 삭제에는 시간이 걸리지만, 검색과 정렬이 뛰어나다는 장점이 있다.
마찬가지로 저장순서를 유지하지 않는다.
headSet 메소드는 지정된 객체보다 작은 값의 객체들을 반환한다.
위 예제에서 b보다 작은 a로 시작하는 객체들을 반환한다.
subSet은 범위 검색의 결과를 반환한다. a ~ al 사이 객체를 반환한다 (airplane)
tailSet은 지정된 객체보다 큰 값의 객체를 반환한다.
위 예제에서 c보다 큰 d로 시작하는 객체들을 반환한다.
HashSet과 TreeSet비교
HashSet, TreeSet 모두 중복을 허용하지 않고 순서가 없는 컬렉션이다.
1. 구현방식
- HashSet은 해싱을 이용해 구현
- TreeSet은 이진탐색트리를 이용해 구현
2. 속도
- HashSet > TreeSet
- 해싱이 이진탐색트리보다 빠름
3. 정렬 기능
- HashSet < TreeSet
- 이진탐색트리를 이용했기 때문에 데이터 정렬이 가능
- HashSet을 사용한 회원 명단 관리 예제
HashMap
hasing을 사용하기 때문에 성능이 뛰어남.
HashMap<키의 타입, 데이터의 타입> 객체명 = new HashMap<>(배열 수);
put() - 반드시 키값, 데이터 두개의 파라미터를 넘겨 주어야 한다. put("key","data")
remove() - 저장된 데이터를 삭제한다. 키 값을 넣어줘야한다. remove(key)
clear - 저장된 데이터를 전부 지운다. clear()
containsKey - 키 값을 넣어 값이 있는지 확인한다. 리턴 타입은 Boolean이다. containsKey("key")
해쉬 테이블의 키 값의 번호는 hashCode() 메소드를 활용한다. 리턴타입은 int다.
set과 달리 map은 중복을 허용한다.
하지만 key값은 중복이어선 안되고, value값의 중복만 허용한다.
만약 map.put("해쉬",10); 을 한 후
map.put("해쉬", 20);을 하게되면 마지막에 입력된 key의 value값으로 덮어 씌워진다.
key와 value 값을 묶어서 하나의 데이터(entry)라고 한다.
기능 | HashMap | HashTable |
---|---|---|
키 값에 null 저장 가능 여부 | O | X |
쓰레드 안전 여부 | X | O |
그래서 HashMap을 Thread Safe하게 이용하려면
Map m = Collections.synchronizedMap(new HashMap(…));
이런식으로 사용해야한다.
예제
HashMap map = new HashMap();
map.put("a", new Integer(10));
map.put("b", new Integer(20));
map.put("c", new Integer(30));
Set set = map.entrySet();
Iterator it = set.iterator();
while(it.hasNext()){
Map.Entry entry = (Map.Entry)it.next();
sysout(entry.getKey() + " " + entry.getValue());
}
set = map.keySet();
sysout("참가자 명단 : " + set);
Collection<Integer> values = map.values();
it = values.iterator();
int total = 0;
while(it.hasNext()){
Integer i = (Integer)it.next();; //next가 Object 형이라 형변환해야함
total += i.intValue();
}
예제를 자세히 보면
Set set = map.entrySet();
Iterator it = set.iterator();
entrySet() - map에 정의된 key값과 value값을 다 가져온다.
Map 인터페이스를 구현한 컬렉션 클래스는 key, value를 한 세트로 저장하기 때문에
iterator를 직접적으로 호출할 수 없다.
그래서 keySet이나 entrySet과 같은 메소드를 사용해 키와 값을 각각 따로 Set의 형태로 얻어온 후 iterator()를 호출해준다.
while(it.hasNext()){
Map.Entry entry = (Map.Entry)it.next();
sysout(entry.getKey() + " " + entry.getValue());
}
Map.Entry는 Map 인터페이스의 내부 인터페이스이다.
그 안에 getKey, getValue가 있다. 각각 Key, value 객체를 반환한다.
set = map.keySet();
keySet()은 HashMap에 저장된 모든 키를 말하고, 이 키를 set에 담아 전부를 반환하게 된다.
'자료구조' 카테고리의 다른 글
[자료구조] 자바 Map 총정리 (2) | 2018.09.28 |
---|---|
큐 (0) | 2018.07.17 |
ArrayList와 LinkedList 비교 + 제네릭 (0) | 2018.02.05 |
순차탐색 (0) | 2018.01.29 |
기수 정렬 (0) | 2018.01.29 |
댓글