해쉬 셋(Hash Set)

Life is ninanino·2022년 9월 15일
0

자료구조

목록 보기
1/9
post-thumbnail

[Hash 란]
임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환(매핑)하는 것
그리고 위와 같은 기능을 하는 함수를 해시 함수(Hash Function)이라고 한다

ArrayList,LinkedList 등 수많은 자료구조에서 '특정 값'이 있는지 찾아내기 위해선
배열 혹은 노드를 순회해보면서 특정값이 있는지 찾아내야 한다
해시함수를 이용하면 굳이 순회할 필요가 없다.
동일한 메세지(값)에 대해서는 동일한 다이제스트(해시함수에서 얻어진 값)를 갖기 때문이다
특정 값에 대한 다이제스트는 변하지 않기 때문에 이 다이제스트의 값을 배열의 위치(index)로 활요한다. 특정 값에 대해 배열의 특정 위치로 지정해두는 것과 같다

Set은 '중복원소'를 허용하지 않는다.
우리가 원소를 추가할 때마다 해당 원소가 중복되는 원소인지 아닌지를 검사해야한다
모든 원소를 검사한다는 것은 비효율 적이다.

그래서 hash함수를 통해 특정 값에 대한 고유의 다이제스트를 얻고 그 값에 대응하는 index를 찾아서 해당 인덱스에 있는 요소만 검사하면 되는 것이 HashSet의 기본 개념이다

HashSet은 자바 Collection 중 Set의 파생클래스이다
set을 집합이라고 생각하면 되는데 HashSet의 경우 몇 가지 특징이 있다.
1. 중복되는 원소를 넣을 경우 하나만 저장한다. 즉, 중복원소를 허용하지 않는다
2. HashSet은 순서 개념이 없다. 따라서 Collections.sort() 메소드를 사용할 수 없다.
만약 정렬을 하고 싶다면 리스트로 변환후 정렬해야한다

hashCode()는 객체의 주소값을 이용해서 해시 알고리즘에 의해 생선된 고유의 정수값을 반환한다.
객체가 같은 메무리 주소를 가리키고 있다면 같은 정수값을 얻는다
주의할 점은 객체가 같은 내용을 지니더라도 가리키는 주소가 다르면 다른 값을 지닌다.

key : hashSet에서는 data(value)자체가 key값이 된다
hash : 해싱 된 key의 고유 값

HashSet.size()는 HashSet의 크기(=저장되어 있는 원소의 개수)를 반환한다

profile
백엔드 프로그래밍을 공부하고 있습니다. AWS, 클라우드 환경에 대해 관심이 많습니다.

0개의 댓글