19. Creating a Search Function Using String Hashing

Problem solving

1. Hash를 이용하여 풀기

🧐 Q. 해시값으로 변환하면 비교횟수를 크게 줄일 수 있나요?

Answer)

1. 문자열 비교와 해싱 비교의 차이

• 문자열 비교는 문자 하나씩 순차적으로 비교해야 하므로 시간 복잡도는 O(L)O(L)O(L)입니다. (여기서 LLL은 문자열의 길이)
• 해시 비교는 두 정수(해시값)를 비교하는 작업이므로 시간 복잡도는 O(1)O(1)O(1)입니다.

예시:

• 문자열 리스트: ['apple', 'banana', 'cherry']
• 쿼리 문자열: 'banana'

문자열 비교의 경우:

• 첫 번째 문자열 'apple'과 비교: 모든 문자를 비교 → O(L)
• 두 번째 문자열 'banana'와 비교: 모든 문자를 비교 → O(L)
• 총 비교 횟수: O(N×L), N은 리스트의 크기.

해시 비교의 경우:

• 해시값을 미리 계산한 후 쿼리의 해시값과 비교:
  • 해시값 비교는 숫자 비교로 O(1)
• 총 비교 횟수: O(N)

결론적으로, 해싱은 문자열이 길어질수록 효율적입니다.

🧐 Q. 해시비교도 문자열비교와 마찬가지로 각각 개별로 모두 비교할텐데, 상수시간 복잡도가 O(1) 이죠?

Answer)

해싱의 핵심 이점은 다음 두 가지로 나뉩니다:

1. 정수 비교는 문자열 비교보다 빠르다.
   • 정수(해시값)를 비교하는 비용은 상수 시간 O(1)입니다.
   • 반면 문자열 비교는 문자열 길이에 따라 시간이 달라집니다.
2. 사전 계산(Pre-computation)
   • 해시값은 문자열을 사전에 정수로 변환해 두기 때문에, 비교할 때는 이미 계산된 정수만 비교합니다.
   • 이 과정에서 문자열 길이에 비례하는 비용 O(L)은 한 번만 발생하며, 이후의 비교는 항상 O(1)입니다.

예시:

• 문자열 비교:

  • 두 문자열 apple과 apple을 비교 → 각 문자를 비교: a == a, p == p → O(L)

• 해시 비교:

  • apple의 해시값 h₁=123456 비교 대상 해시값 h₂=123456

  • 정수 h₁과 h₂를 비교 → O(1)

    여기서 상수시간 복잡도란? 해시값이 미리 계산된 상태에서, 단순히 두 정수(해시값)를 비교하는 작업을 의미

function polynomialHash(str) {
  const p = 31; // 해시 계산에 사용할 소수
  const m = 1_000_000_007; // 큰 소수 모듈러 값
  let hashValue = 0;

  for (let i = 0; i < str.length; i++) {
    hashValue = (hashValue * p + str.charCodeAt(i)) % m; // 올바른 모듈로 연산 적용
  }
  return hashValue;
}

function solution(stringList, queryList) {
  const hashList = stringList.map((str) => polynomialHash(str)); // stringList의 해시값 계산

  const result = [];
  for (const query of queryList) {
    // queryList를 순회하며 검사
    const queryHash = polynomialHash(query); // query의 해시값 계산
    if (hashList.includes(queryHash)) {
      // 해시값이 존재하는지 확인
      result.push(true);
    } else {
      result.push(false);
    }
  }
  return result; // 결과 배열 반환
}

// 테스트 실행
console.log(
  solution(["apple", "banana", "cherry"], ["banana", "kiwi", "melon", "apple"])
);

🧐 Q. hashValue = (hashValue * p + str.charCodeAt(i)) % m;를 반복문에서 사용하는 것은 왜 그런것일까?

Answer) 모든 문자를 포함하고, 순서를 반영하며, 효율적으로 해시값을 계산하기 위해 필수적입니다. 초기값이 0이라도, 반복문을 통해 각 문자를 차례로 처리하여 최종 해시값을 얻는 과정이 필요합니다.