본문 바로가기
프로그래밍/자료구조

[자료구조] 코드로 알아보는 java의 HashSet

by 사바라다 2020. 2. 17.

안녕하세요. Java의 자료구조를 알아보는 시간을 가지고 있습니다. 지금까지 List, Map에 대해서는 한종류씩 알아보았지만 아직 Set에 대해서는 알아본적이 없습니다. 그래서 오늘은 Set의 구현체 중 하나인 HashSet을 코드로 한번 알아보는 시간을 가지도록 하겠습니다.

Set

Set은 List와 다르게 중복을 허용하지 않는 자료구조입니다. 어떻게 중복을 허용하지 않을 수 있는지 코드와 함께 살펴보도록 하겠습니다.

상속과 멤버변수

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

Hashset의 내부를 보니 HashMap을 이용해야한다는 것을 알 수 있었습니다. HashMap의 구조의 자세한 내용은 이전 포스팅을 참고해주시기바랍니다. HashMap을 이용한다는 것은 Object 클래스의 #equals 메서드와 #hashcode 메서드를 이용하여 중복값을 제거하겠다는 의도를 알 수 있었습니다.

PRESENT는 HashSet의 내부에 있는 HashMap의 Value에 들어가는 Dummy값입니다. HashMap의 Key는 사용되지만 Value는 HashSet에서는 사용되지 않으므로 Dummy 데이터로 채우는 것입니다.

생성자

/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
    map = new HashMap<>();
}

HashSet instance를 Set<String> set = new HashSet<>()으로 선언하여 가져온다면 위와같은 생성자가 실행됩니다. 즉, 우리가 HashSet의 Instance를 선언하면 내부에서는 Stirng을 Key로 가지며 Object를 Value로 가지는 HashMap이 새로 생성되는 것입니다.

add

/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element <tt>e</tt> to this set if
* this set contains no element <tt>e2</tt> such that
* <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns <tt>false</tt>.
*
* @param e element to be added to this set
* @return <tt>true</tt> if this set did not already contain the specified
* element
*/
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

hashSet의 add입니다. 단순하게 map에 put을 하고 마무리 합니다. 이렇게 map에 key를 넣게 되면 HashMap의 내부 알고리즘으로 #hashcode, #equals를 비교하여 값을 넣게 됩니다. 그리고 map.#put의 반환값은 key 중복이 존재한다면 예전값이 반환되며 존재하지 않는다면 반환되는 값은 없습니다. 따라서 HashSet의 #add 메서드는 중복값이 존재할 때 반환값은 false, 존재하지 않을 경우에는 true입니다.

remove

/**
* Removes the specified element from this set if it is present.
* More formally, removes an element <tt>e</tt> such that
* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
* if this set contains such an element.  Returns <tt>true</tt> if
* this set contained the element (or equivalently, if this set
* changed as a result of the call).  (This set will not contain the
* element once the call returns.)
*
* @param o object to be removed from this set, if present
* @return <tt>true</tt> if the set contained the specified element
*/
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

HashSet의 remove 역시 HashMasp의 remove를 호출한 후 결과값을 반환하며 마무리됩니다. HashSet의 remove는 Key, Value 기반이기 때문에 index를 이용하여 삭제할 수 는 없습니다. map.#remove를 보면 add와 동일하게 #hashcode, #equals를 비교하여 내부의 값을 제거합니다. 이 경우 값이 존재하면 true를 리턴하게되며 없다면 false를 return하게 됩니다.

마무리

오늘은 이렇게 HashSet에 대해서 알아보았습니다. 코드를 살펴 본 결과 HashSet은 HashMap을 내부에 구현하여 중복이 일어나지 않도록 한다는 사실을 알 수 있었습니다. 다른 Collection의 자료구조들과 다르게 HashSet은 대부분 HashMap을 이용하기 때문에 코드가 길지 않습니다. 흥미가 있으신 분들은 한번쯤 찾아보는것도 좋을 것 같습니다.

감사합니다.

참조

https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

댓글0