컬렉션 프레임워크 - 해시(Hash)

리스트(List) vs 셋(Set)

List (리스트)

• 정의: 리스트는 요소들의 순차적인 컬렉션이다. 요소들은 특정 순서를 가지며, 같은 요소가 여러번 나타날 수 있다.
• 특징:
  • 순서 유지: 리스트에 추가된 요소는 특정한 순서를 유지한다. 이 순서는 요소가 추가된 순서를 반영할 수 있다.
  • 중복 허용: 리스트는 동일한 값이나 객체의 중복을 허용한다.
  • 인덱스 접근: 리스트의 각 요소는 인덱스를 통해 접근할 수 있다. 
• 용도: 순서가 중요하거나 중복된 요소를 허용해야 하는 경우 주로 사용된다.

 

Set(셋)

• 정의: 셋은 유일한 요소들의 컬렉션이다.
• 특징:
  • 유일성: 셋에는 중복된 요소가 존재하지 않는다. 셋에 요소를 추가할 때, 이미 존재하는 요소면 무시된다.
  • 순서 미보장: 대부분의 셋 구현에서는 요소들의 순서를 보장하지 않는다. 즉, 요소를 출력할 때 입력 순서와 다를 수 있다.
  • 빠른 검색: 셋은 요소의 유무를 빠르게 확인할 수 있도록 최적화되어 있다. 이는 데이터의 중복을 방지하고 빠른 조회를 가능하게 한다.
• 용도: 중복을 허용하지 않고, 요소의 유무만 중요한 경우 사용된다.

예시:

• List: 장바구니 목록, 순서가 중요한 일련의 이벤트 목록
• Set: 회원 ID 집함, 고유한 항목의 집합

---

직접 구현하는 Set

 

---

해시 알고리즘

 

---

시작

 

---

index 사용

정리

데이터의 값 자체를 배열의 인덱스로 사용했다. 배열에서 인덱스로 데이터를 찾는 것은 매우 빠르다. 그 덕분에 O(n)의 검색 성능을 O(1)로 획기적으로 개선할 수 있었다

---

메모리 낭비

한계

데이터의 값을 인덱스로 사용한 덕분에 O(1)의 매우 빠른 검색 속도를 얻을 수 있다. 그리고 이 코드는 정상적으로 수행 된다. 하지만 낭비되는 메모리 공간이 너무 많다.

 

 

---

나머지 연산

해시 인덱스

배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스(hashIndex)라 한다.

---

해시 충돌 설명

 

 

---

해시 충돌 구현

 

 

정리

해시 인덱스를 사용하는 경우

• 데이터 저장
• 평균: O(1)
• 최악: O(n)
• 데이터 조회
• 평균: O(1)
• 최악: O(n)

 

해시 인덱스를 사용하는 방식은 사실 최악의 경우는 거의 발생하지 않는다. 배열의 크기만 적절하게 잡아주면 대부분 O(1)에 가까운 매우 빠른 성능을 보여준다.

 

 

 

 

 

 

 

 

 

 

출처 - 김영한의 실전 자바 중급 2편