1.11.1 Collection-Set

yeonseong Jo·2023년 5월 2일
0

SEB_BE_45

목록 보기
18/47
post-thumbnail

이전에도 collections 중
List 자료형에 대해 설명한 적이 있다.
이 List에는 이전에 말했듯이 하위에는
ArrayList, LinkedList가 있다.

상위도 존재하는데, 이게 Collection이다.
Collection 하위인 List와 같은 위치에
Set가 하나 더 있는데,
오늘은 이 Set에 대해 파보려 한다.


Set

Set은 "집합"을 의미한다.
고등학생 때 수학에서 집합을 배울 때,
집합에는 중복을 허용하지 않는다.
이 특징이 java의 자료형인 set에서도 적용이된다.

한가지 더 특징이 있는데,
바로 순서가 없다는 것이다.

Set의 하위에는 HashSet, TreeSet이 존재한다.


HashSet

HashSet에는 값을 추가 하는 방법을
코드로 한번 짜 보았다.


class HashSet implements Set {
	...
    
	@Override
    public boolean add(Object O){
        Iterator<Object> iterator = this.iterator();

        while(iterator.hasNext()){
            Object next = iterator.next();
            if (next.hashCode() == O.hashCode()){
                if (next.equals(O){
                    return false;
                }
            }
        }
        super.add(O);
        return true;
    }
}

(배운 방식을 토대로 짠 것인데, 실제로 맞는건지는 모르겠다)

추가하고자 하는 값의 hashCode를
HashSet에 있는 모든 객체의 hashCode와
1:1 비교를 통해 hashCode를 비교하고,
같은 Code를 가진 객체가 HashSet에 존재하지 않으면
그대로 추가하고,
같은 Code를 가진 객체가 있으면,
equals를 통해 직접 비교 하여
false면 추가하는 방식이다.


TreeSet

TreeSet은 내부적으로
이진 검색 트리(binary search tree)를 사용하여
원소를 저장한다고 한다.

이진 검색 트리는 어느 한 기준 값(루트 노드)를 시작으로,
왼쪽에는 루트 노드보다 작은 값을, 오른쪽에는 큰 값을 저장한다.
Tree 관련 자료형은 red & black tree를 베이스로 하는데,
이 베이스는 다음에 좀 더 공부해 보자...

이 때문에 TreeSet은 항상 오름차순으로 정렬되어 있다.

HashSet보다 데이터의 추가와 삭제는 시간이 더 걸리지만,
검색과 정렬은 HashSet보다 빠르다.

profile
뒤(back)끝(end)있는 개발자

0개의 댓글

Powered by GraphCDN, the GraphQL CDN