- 충돌 해결 어떻게 하는지
- thread-safe 구현 방식
- HashSet의 중복 해결 방법
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
중복된 원소를 허용하지 않고 순서 역시 고려되지 않음.
객체를 저장하기 전에 먼저 객체의 hashCode() 메서드를 호출하여 해시코드를 얻고 이미 저장되어 있는 객체들의 해시코드와 비교한다.
만약 동일한 해시코드가 있다면 다시 equals()로 두 객체를 비교해 참이면 저장 안함.
이미 키에 매핑된 값이 있으면 그전의 값을 덮어씌운다고 명시되어 있다.
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} /**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
map에 E e를 저장할 때, e의 hashCode를 사용해서 버킷에 담는다. 이때 map의 인덱스는 해당 객체의 hashCode % 버킷의 수를 이용하게 된다.
버킷의 확장에 따른 인덱스 변화
자바의 HashMap은 디폴트로 적은 수의 버킷을 갖도록 하고 포함한 객체 개수가 늘어남에 따라 동적으로 버킷을 확장하도록 한다. 기본 버킷의 수는 16개에서 Entry의 개수가 기본 75%인 임계값(load factor)을 넘으면 버킷의 수를 2배로 늘려 Entry를 다시 정리하게 된다.
이를 HashSet에 적용하면 set에 추가되는 Entry가 많아져 임계값을 넘어가게 되면, 버킷의 수가 늘어나게 되고, 그럼 map에 추가될 인덱스가 바뀌게 된다. (인덱스 = hashCode % 버킷의 수 이므로)
따라서 버킷의 개수가 늘어남에 따라, 즉 Entry가 임계값을 넘김에 따라 map의 인덱스가 변하면서 출력 순서가 달라지는 것이다.
자바7까지 HashMap에 Separate Chaining을 사용한 것은 같지만, 자바8부터는 버킷 당 8개 이상의 데이터가 쌓이면 링크드 리스트에서 트리로 변경한다. (이때 트리 탐색 대소 판단 기준은 해시 함수 값이다.)
그리고 데이터가 삭제되어 6개에 이르면 트리에서 다시 링크드 리스트로 변경한다.
이는 노드가 많을 경우 탐색 성능을 위해서는 트리가 우수하지만, 노드가 적을 경우에 트리는 리스트보다 메모리 사용량이 많고, 탐색 성능에서도 크게 차이가 없기 때문이다.
또, 리스트->트리, 트리->리스트를 8/6으로 차이를 둔 것은 만약 차이가 1이라면 한 쌍이 추가, 삭제가 반복될 경우 자료 구조를 매번 변경해야하는 오버헤드를 낳을 수 있어 2개의 차이를 뒀다고 한다.
HashSet의중복 해결 방법 :
Set<CreateObject> set = new HashSet<CreateObject>();
CreateObject obj1 = new CreateObject(1, 2);
set.add(obj1);
CreateObject obj2 = new CreateObject(1, 2);
set.add(obj2);
위와 같은 코드에서 객체에 들어있는 값이 같음에도 불구하고 둘은 다르다고 판단하여 따로따로 들어갔다.
HashSet이 내부적으로 해당 객체의 hashCode, equlas()를 실행해본다.
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
} public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
HashSet에서 Custom class의 객체를 넣으면 중복값이 들어가는 경우가 있다.
해당 객체의 equals, hashcode를 실행하여 비교하기 때문이다.
두 함수를 오버라이드 해서
@Override
public int hashCode() {
return new HashCodeBuilder().append(a).append(b).toHashCode();
}
@Override
public boolean equals(Object obj) {
CreateObject rhs = (CreateObject) obj;
if (obj instanceof CreateObject) {
return new EqualsBuilder().append(a, rhs.a).append(b, rhs.b).isEquals();
}
return false;
}
}
위와 같이 재정의 해주면된다
hashCode는 객체에 들어가는 값을 해싱한 값을 리턴해주고
equals 메소드에서는 객체에 들어가는 모든 값이 같은지 판단해서 리턴한다.
