HashSet에 리스트를 넣어도 중복으로 체크된다는 걸 알게 되어서 기록한다!
내 생각엔,
당연히 리스트 = 객체 => 그니까 Set에 [1, 2, 3]을 갖고 있는 다른 리스트 list1, list2 두 개를 넣는다고 하면 => Set의 사이즈는 2
하지만 실제로 넣어보면 Set의 사이즈가 1이 된다.
Set을 잘 안 쓴 탓인지 이유를 모르겠어서 정리해보려고 한다!
1. Set 이란?
https://www.geeksforgeeks.org/set-in-java/
정리가 잘 된 포스팅이 있어서 가져왔다!
한마디로 중복을 허용하지 않는 자료구조이다.
2. Set의 add
문제 상황(Set에 리스트를 넣을 때 객체임에도 중복 체크가 되는 상황)을 확인하기 위해 사용한 Set의 add 메소드를 알아보겠다.
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}더 들어가면,
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
일단 여기까지 알게된 것은, HashSet은 내부적으로 HashMap와 hasA 포함관계라는 것이다.
그래서 HashMap의 putVal을 마저 확인하면,
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;
}코드가 매우 복잡한데,
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;주로 봐야할 건 이 코드이다.
해시값이 같으면 같은 데이터라고 인식한다는 것이다.
그럼 [1, 2, 3] 과 [1, 2, 3] 두 리스트가 같은 해시 값을 갖는다는 것을 자연스럽게 알 수 있다!
3. List의 hashCode
hashCode
public int hashCode() {
int expectedModCount = modCount;
int hash = hashCodeRange(0, size);
checkForComodification(expectedModCount);
return hash;
}
int hashCodeRange(int from, int to) {
final Object[] es = elementData;
if (to > es.length) {
throw new ConcurrentModificationException();
}
int hashCode = 1;
for (int i = from; i < to; i++) {
Object e = es[i];
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}간단히 분석하면, 요소의 해시코드 값을 더해주는 것이다. (소수 곱셈 연산을 통해 고유한 hashcode 값이 나오도록 한다.)
현재 요소가 1, 2, 3과 같은 Integer 값이기 때문에 Integer의 hashcode를 확인해보겠다.
Integer의 hashcode
public static int hashCode(int value) {
return value;
}
wrapper 클래스로 싸고 있는 int 값을 반환한다.
4. 결론
결과적으로 같은 1, 2, 3이라는 요소들을 차례차례 더하는 것이기 때문에 같은 값이 나오게 된다!
hashcode에 대한 이해도를 높일 수 있었고 라이브러리 내부 동작도 알 수 있어서 좀 더 명확해진 것 같다. 하지만 소수 연산과 같은 부분에서 이산 수학에 대한 이해도가 떨어진다는 것을 알게 되었다 ㅠ.ㅠ.. 이 부분을 더 공부해야겠다!
