[알고리즘] HashSet
2024. 3. 10. 08:11ㆍ알고리즘 풀이/Java
특징: 내부적으로는 HashMap을 사용한다. add하는 값을 key로 사용한다.
중요: HashMap은 hashCode() method를 이용해서 key에 대한 해시코드를 구한다. 해시테이블은 이 코드를 해싱 함수를 이용해 버킷에 맵핑한다. Object 객체에서 구현되어 있는 hashCode()는 참조값을 사용한다.
Constructor
- HashSet(int initialCapacity): 초기 수용량을 줄 수 있다. 너무 크게 하면 iteration 시간이 비효율적이게 된다.
add(E e): O(1)
clear(): O(n)
contains(Object o): O(1)
isEmpty(): O(1)
iterator(): O(1)
remove(Object o): O(1)
size(): O(1)
spliterator(): O(1)
주의할 점: HashSet을 iteration할 때는 HashSet 객체의 사이즈(원소 개수)와 해시맵 객체의 수용량(버킷의 수)의 합에 비례하여 시간이 증가한다. 그러니까 모든 버킷을 다 돌기 때문에 비어 있는 버킷도 돌게 되어 비효율적이라는 것이다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] ArrayDeque (0) | 2024.03.10 |
---|---|
[알고리즘] HashMap (0) | 2024.03.10 |
[알고리즘] LinkedList (0) | 2024.03.10 |
[알고리즘] ArrayList 메서드별 시간 복잡도 (0) | 2024.03.09 |
[알고리즘] 프로세서 연결하기 (0) | 2024.02.29 |