HashSet

숫자는 해시 알고리즘을 이용해 저장한다

문자는 숫자로 변경하고 해시 알고리즘을 이용해 저장한다

객체는 Object.hashCode()를 이용해서 저장한다.

보통 객체에서 재정의해서 사용한다 재정의 하지 않으면 같은 값이 중복으로 들어간다 같은 객체 인스턴스를 여러개만들었을 때 같은 값이 입력되더라도 같은 해시값이 나오기 때문임

equals도 재정의 해야한다 해당 객체의 특정 값을 기준으로 동등성을 비교하도록 해야함

 

 

해시란?
https://jaeiktech.tistory.com/2

 

 

해시코드와 이퀄스 모두 재정의 하지 않으면 같은 값을 두번 넣었을 때

셋에 다른 곳에 같은 값이 저장된다 검색도 해시코드가 달라 되지 않는다

해시코드만 재정의 한 경우 같은 값을 두번 넣었을 때

셋에 같은 곳에 같은 값이 저장된다 해시코드는 맞지만 중복 데이터를 체크할 때 이퀄스를 사용하는데 Object의 equals()를 사용하게 되어 인스턴스가 다른 둘은 서로 다르다고 판단하고 중복 값이 들어가게 된다

 

자바해시셋의 기본배열값은 16이다

데이터의 양이 배열의 75%를 넘으면 배열을 2배널리고 가지고 있는 모든 데이터를 다시 리해싱하여 배치한다.

커진 배열에 맞추어 다시 계산해야하기때문임 인덱스 충돌 가능성이 줄어들고

데이터가 다시 75%를 차지하게 되면 2배커지고 리해싱하는 것을 계속 반복한다

 

해시알고리즘에서 한 인덱스에 자료가 많이 몰려있으면 내부 자료구조를 링크드어레이에서 해시트리로 바꿔버려서 최악시 O(N)을 O(logN)으로 바꾸는 것도 자바에서 최적화 했다