Java / 컬렉션 프레임워크 - Hash

Set

유일한 요소들의 컬렉션

중복을 허용하지 않고 요소의 유무만 중요한 경우 사용

 

유일성 : 중복된 요소 존재 x

순서 미보장 : 요소를 출력할 때 입력 순서와 다를 수 있음

빠른 검색 : 요소의 유무를 빠르게 확인할 수 있도록 최적화

 

Hash Algorithm

검색 속도를 높이기 위해 데이터의 값을 배열의 인덱스로 사용할 경우

>> O(1)의 매우 빠른 검색 속도, 하지만 낭비되는 메모리 공간이 너무 많음

>> 나머지 연산을 사용해서 해결

 

Hash Index

배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스

저장할 값에 나머지 연산자를 사용해서 해시 인덱스 구함

>> 배열의 인덱스를 사용하기 때문에 하나의 값을 저장하거나 조회하느데 O(1)로 빠른 성능

 

Hash 충돌

다른 값을 입력했지만 같은 해시 코드가 나오는 것

해시 충돌은 낮은 확률로 일어날 수 있다고 가정

>> 같은 해시 인덱스의 값을 같은 인덱스에 함께 저장

>> 배열 안에 배열을 만들어서 해결