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

안녕하세요. 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