6.1 List vs Set

List는 순서가 있으며 중복을 허용하고 인덱스 접근을 한다.

순서가 중요하거나 중복된 요소를 허용해야 하는 경우에 주로 사용된다.

Set

Set 은 유일한 요소들의 컬렉션이다.

특징

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

중복을 허용하지 않고, 요소의 유무만 중요한 경우에 사용된다.

6.2 해시 알고리즘 - index 사용

배열에 요소를 추가할 때, 중복 데이터가 있는지 전체 데이터를 항상 확인해야 한다. 따라서 O(n)으로 입력 성능이 나쁘다.

배열은 인덱스의 위치를 사용해서 데이터를 찾을 때 O(1)으로 매우 빠른 특징을 가지고 있다.

데이터의 값 자체를 배열의 인데스와 맞추어 저장한다.

즉, 데이터 1은 배열의 인덱스 [1] 위치에 저장된다.

6.3 해시 알고리즘 - 메모리 낭비

만약 입력 값의 범위가 int 숫자의 모든 범위를 입력할 수 있도록 하려면 메모리를 4byte * 42억 = 약 17기가바이트 를 사용하게 된다. 이는 심각한 메모리 낭비를 초래한다.

6.4 해시 알고리즘 - 나머지 연산