Set은 인덱스의 순서를 보장하지 않는다.
프리코스 1주차 야구게임을 리뷰하는 도중 Set으로 처음부터 중복을 제거하면 어떨까 생각했다.
public static Set<Integer> inputParsing(String input) {
Set<Integer> nums = new HashSet<>();
for (String num : input.split("")) {
nums.add(validateNumber(num));
}
return nums;
}위와 같은 코드를 작성하고, 같은 방식으로 랜덤 숫자를 뽑는 함수 또한
Set을 사용해서 작성했다.
private Set<Integer> randomNumber() {
Set<Integer> ranNums = new HashSet<>();
while (ranNums.size() != 3) {
ranNums.add(randomGenerator());
return ranNums;
}하지만 만들고 보니 이게 무슨 일인가... 숫자가 순서대로 나왔다...
중간에 테스트 없이 진행한 잘못도 있고, 나의 얕은 지식은
Set이 인덱스 순서를 보장하지 않는다는 것을 모르고 있었다.
그럼 Set은 왜 인덱스 순서가 보장이 안될까?
Set -> HashSet 동작 원리
HashSet은 Set 인터페이스를 구현한 클래스로 내부에서는 HashMap을 사용한다.
때문에 HashSet은 데이터의 순서를 유지하지 않는 대신에 데이터의 무결성을 보장한다.
HashSet에 요소를 추가할 때 요소의 해시코드를 계산한다.
해당 해시코드는 객체의 메모리 주소, 객체의 필드를 기반으로 계산된다.
계산된 해시코드를 기반으로, 요소는 내부적으로 배열의 특정 위치에 저장된다.
이러한 위치는 해시코드에 따라 달라질 수 있다.
두 개 이상의 요소가 동일한 버킷에 할당된 경우 HashSet은 이를 충돌로 처리하고
이러한 충돌들을 관리하는 방법을 사용한다.
순서가 보장되지 않는 이유는?
위에서 말했듯 요소가 저장되는 위치는 해시코드에 의해 결정된다
따라서 요소가 추가되는 순서와는 관계가 없다.
또한 크기가 커지면 내부적으로 재해싱이 발생해 모든 요소가 새로운 위치에 배치된다.
이러한 과정이 요소의 순서를 더 예측 불가능하게 만든다.
HashSet의 의도는 빠른 검색과 요소의 무결성에 중점을 두고 설계되었다.
순서 유지는 이런 목적에 부합하지 않으며, 성능 비용의 낭비를 불러온다.
순서가 중요한 경우
만약 순사가 중요하다면 LinkedHashSet, TreeSet 같은
다른 Set 구현체를 사용하는 것을 추천한다.
LinkedHashSet은 요소가 추가된 순서를 유지하며, TreeSet은 요소를
정렬된 순서로 유지한다.
간단 HashSet
위 과정들이 잘 이해되지 않아서 Set의 내부 구조를 바탕으로 분석했다.
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}HashSet에 add(E e) 요소를 추가할 때 hashCode()
메소드를 호출해 해시 코드를 계산한다.
@IntrinsicCandidate
public native int hashCode();
static final int hash(Object key) {
// 해시코드를 임시저장할 변수를 생성
int h;
// 키가 null인 경우 key의 해시코드는 0이 된다.
// null이 아닌 경우 h = key.hashCode()를 호출해 해시코드를 얻어낸다.
// 후에 h >>> 16 연산을 통해 h의 비트를 16비트 오른쪽으로 쉬프트하고 빈 자리를 0으로 채운다.
// 마지막으로 원래의 해시코드와 16비트 오른쪽 쉬프트한 해시코드를 XOR 연산을 한다.
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}이런 연산을 통해서 해시코드의 상위 비트, 하위 비트를 혼합해 균일한 해시 분포를 만든다.
위와 같은 연산을 진행하는 목적은 상,하위 비트를 혼합해 충돌을 줄이고,
저장 공간의 균일한 데이터의 분포를 통한 성능 향상이다.
최종적으로 HashSet이 add를 하는 과정은 이렇다.
public Class SelfMakeHashSet<E> {
// 해시맵 내부에서 사용
private transient HashMap<E,Object> map;
// 키에 공통적으로 할당되는 값
private static final Object PRESENT = new Object();
public setTestHashSet() {
map = new HashMap<>();
}
// HashMap에서 사용하는 put 함수 사용
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// HashMap에서 사용하는 size 함수 사용
public int size() {
return map.size();
}
}public class SetTest {
public static void main(String[] args) {
SelfMakeHashSet<Integer> selfMakeHashSet = new SelfMakeHashSet<>();
selfMakeHashSet.add(3);
selfMakeHashSet.add(2);
selfMakeHashSet.add(1);
System.out.println(selfMakeHashSet.size()); // 3
}
}