[인프런 김영한 실전 자바 - 중급편] 컬렉션 프레임워크 - Hash

Set

• List vs Set
  
  • List : 요소들의 순차적인 컬렉션으로 순서가 중요하거나 중복을 허용하는 경우 사용된다.
    • 순서 유지 - 순서를 가진다.
    • 중복 허용
    • 인덱스 접근 - 리스트의 각 요소는 인덱스를 통해 접근할 수 있다.
  • Set : 유일한 요소들의 컬렉션으로 중복을 허용하지 않고 요소의 유무만 중요한 경우 사용된다.
    • 유일성 - 중복을 허용하지 않는다.
    • 순서 미보장 - 순서가 없다.
    • 빠른 검색 - 요소의 유무를 빠르게 확인할 수 있도록 최적화되어 있다.

 

• Set은 중복된 데이터를 허용하지 않는다. (Set을 효율적으로 만들기 위한 흐름)
  
  1. 데이터를 추가할 때마다 중복을 체크해야한다.
     => 모든 요소를 다 확인하면서 데이터 중복을 체크하면 O(n)으로 성능이 나쁘다.
  2. 일일이 중복 체크하는 것이 아닌 입력 데이터 값과 배열 인덱스를 같게 지정한다.
     => 인덱스를 통해 데이터 조회 성능은 O(1)로 좋지만 낭비하는 메모리 공간이 너무 많아진다.
  3. 메모리 공간 낭비를 줄이기 위해서 해시 인덱스를 사용한다.
     => 낭비되는 메모리 공간은 줄었지만 동일한 해시 인덱스에 의해서 해시 충돌이 발생할 수 있다.
  4. 해시 충돌을 인정하고 해시 충돌이 일어났을 때 같은 해시 인덱스의 값을 같은 인덱스에 저장한다.
     배열 안에 배열(리스트)을 만들어서 같은 해시 인덱스의 값들끼리 저장한다.
     => 많은 숫자들이 겹치는 최악의 경우 O(n)의 성능을 보이지만 확률적으로 평균으로 보면 가끔 해시 충돌이 발생해도 O(1)의 성능을 보인다. 
  5. 통계적으로 입력한 데이터의 수가 배열의 크기의 75%를 넘지 않으면 해시 인덱스는 자주 충돌하지 않는다.

해시 인덱스 : 배열의 인덱스로 사용할 수 있게 알고리즘을 통해 원래의 값을 계산해서 인덱스로 표현한 것.

예를 들어서 배열의 크기(10)로 나머지 연산을 사용해서 해시 인덱스를 구하는 경우
ex) 입력값(5) % 배열의 크기(10) = 해시 인덱스(5), 입력값(13) % 배열의 크기(10) = 해시 인덱스(3)
arr[0] = null ... arr[3] = 13, arr[4] = null, arr[5] = 5 ... arr[9] = null
이 경우 입력값 9와 19는 해시 인덱스가 같기에 충돌이 발생한다.

 

• 문자열의 경우 어떻게 해시 인덱스로 표현할 수 있을까?
  • 모든 문자는 본인만의 고유한 숫자로 표현할 수 있다.
  • 컴퓨터는 문자를 직접 이해하지 못하고 각 문자에 고유한 숫자를 할당해서 인식한다. (ASCII 코드)
  • 문자를 저장할 때 숫자로 변환해서 저장한다.
  • 결국 문자도 숫자로 표현할 수 있기 때문에 알고리즘을 사용해서 해시 인덱스로 표현이 가능하다.

---

출처: [인프런 김영한 실전 자바 - 중급편]

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2/dashboard

김영한의 실전 자바 - 중급 2편 강의 | 김영한 - 인프런