[코딩테스트] Hash - 프로그래머스 포켓몬

문제 분석

• nums 배열에는 포켓몬의 종류 번호가 저장되어있음

• N 마리 중 절반인 N/2마리를 선택할 수 있고, 최대한 다양한 종류의 포켓몬을 가져야 한다.

• 둘 중 선택할 수 있는 포켓몬의 최대 종류개수를 구하면됨,
  ==> N마리중 절반인 값과 중복제거된 값을 비교해서 둘중 더 Min 값이 정답이된다 Math.min 사용

  import java.util.*;
  
  class Solution{  
  public int solution(int\[\] nums){  
  Set poketmons = new HashSet<>();
  
  for(int num : nums){
      poketmons.add(num);
      }
      int maxSelectable = num.length/2;
      return Math.min(poketmons.size(), maxSelectable);

HashSet을 생성하여 중복을 제거하면서 포켓몬을 저장하고,(HashSet은 중복을 허용하지 않으므로 자동으로 중복이 제거된다)
HashSet에 값을 삽입하는 연산의 시간복잡도는 평균적으로 O(1) 이다.
nums의 길이가 N일때 반복문을 돌면서 hashSet에 값을 추가하는 과정은 0(N)이다.

해시 란 ?

어떤 데이터를 찾는ㄴ다고 했을때 쉽게 떠올리는 방법은 처음부터 끝까지 찾아보는 순차탐색법입니다. 이 방법을 사용하여 찾는다면 찾을 수는 있겠지만,최악의 경우 탐색을 할때마다 모든 데이터를 살펴봐야 할 수 있으므로 효츌적이지 않다.
이런 방법을 개선하려면 찾아야 할 값이 어디에 있는지 알아낼 방법이 필요하다. 어떠한 값이 저장되는 윛치를 어떤 규칙으로 정할 수 있다면, 굳이 탐색을 할 필요 없이 바로 데이터를 찾아낼 수 있을 겁니다. 이런 구조를 생각해서 만든 것이 해시라고 한다.

해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색하는 자료구조를 말한다.
해시는 키 를 활용하여 데이터 탐색을 빠르게 할 수 있다.

해시 테이블은 키와 대응한 값이 저장되어 있는 공간이고, 해시 테이블의 각 데이터를 버킷(bucket)이라고 부른다.

해시는 단방향으로만 검색할 수 있는대신 빠르게 원하는 값을 검색할 수 있다. 이런 특진은 데이터를 저장하고 검색하거나, 보안이 필요ㅛ한 때에 활용된다.
예를 들어 비밀번호 관리(해싱한 비밀번호를 저장) , 데이터베이스 인덱싱 , 블록체인 등에 활용됩니다.
우리가 보통 스프링에서 비밀번호를 저장할때 BCrypPasswordEncoder를 사용하여 해싱처리 하여 사용하게 된다. 이런 것도 해시라고 할 수 이따.

해시 함수 사용시 고려사항

1. 해시값이 해시 테이블의 크기를 넘기면 안된다.

만약 해시 테이블의 크기가 N이라고 가정하면 index 값은 0~ (N-1)값을 가질 수 있다.

2. 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야한다.

해시 값 충돌이란, 서로 다른 두 키가 똑같은 해시 값을 바라고보고 있을때 충돌이 발생한다.

키 값인 홍길동과 홍길서를 해시 함수에 넣었을때, 같은 1의 값을 바라본다면 이것은 충돌이 발생했다고 한다.
하나의 키에는 하나의 값을 유니크하게 가질 수 있도록 해시함수를 구성해야한다.

자주사용하는 해시 함수

나눗셈법

키를 소수로 나누어, 그 소수로 나눈 나머지를 인덱스로 사용하는 것이다.
| 왜 소수로 나눌까?
-> 소수가 다른 수 보다 충돌이 적기 때문에, 나머지가 반복될 확률이 적기 때문이다.
만약 소수 구하기가 어렵다면, 해시테이블의 크기로 나누면 0~(k-1)값으로 가질 수 있게된다.

곱셈법

곱셈법 해시 함수의 공식

h(k)=⌊m(kAmod1)⌋

h(k)=⌊m(kAmod1)⌋
k: 해시로 변환할 키(입력값)
A: 0과 1 사이의 상수(일반적으로 무리수 사용)
m: 해시 테이블 크기(보통 2의 거듭제곱 사용)
mod 1: kA에서 정수 부분을 제거하여 소수 부분만 남김
floor(): 정수로 변환

곱셈법의 주요 개념
A 값으로 소수를 선택하면 충돌을 줄일 수 있음. 보통 A = (√5 - 1) / 2 ≈ 0.6180339887 사용.
m을 2의 거듭제곱으로 설정하면 연산 속도가 빨라짐(비트 연산 활용 가능).

문자열 해싱(String Hashing)

문자열을 해시 값으로 변환하는 방법입니다. 문자열 해싱은 주로 문자열 검색, 해시 테이블, 암호화 등에 사용됩니다.

문자열 해싱 방법
문자열 해싱은 일반적으로 다음과 같은 방법을 사용합니다:

다항식 해싱(Polynomial Hashing):

각 문자를 특정 기수(base, 보통 소수)를 사용하여 해시 값으로 변환
예시: H(s) = (s[0] * p^0 + s[1] * p^1 + ... + s[n-1] * p^(n-1)) mod m
보통 p = 31 또는 p = 37 사용 (소수)
m은 큰 소수로 설정하여 충돌을 줄임
롤링 해시(Rolling Hash):

다항식 해싱의 변형으로 슬라이딩 윈도우를 사용하여 빠르게 새로운 해시 값을 계산 (예: 라빈-카프 알고리즘)