해시

in csStudy

[2023.06.09 ~ 2023.06.15 동안 공부한 해시이다.
해당 포스트는 누구나 자료구조와 알고리즘 개정 2판을 참고하여 작성되었다.

📌 해시(hash)

해시(hash)

해시테이블을 데이터를 키와 값 쌍으로 묶을 수 있을 때, O(1)만에 데이터를 검색할 수 있게 해준다.❗

배열에서 선형검색시 O(N), 정렬된 배열에서는 O(logN)이 걸린다면 해시테이블을 사용했을 때는 O(1)단계안에 검색을 완료 할 수 있다.

해시(hash) 예

식당 음식 메뉴판을 해시 테이블로 작성할 수 있다. menu = {“떡볶이” => 6,500,”김밥” => 3,500,”라면” => 5,000} 해시테이블은 키와 값으로 이루어진 쌍이 여러개 있는 테이블 형식으로 구성되어있다.

해시를 사용할 때 유의할 점

해시테이블에서 O(1)만에 값을 찾으려면 그 값에 해당하는 키를 알때에만 가능하다. 만약 키의 값을 전혀 모르는 상태에서 검색을 한다면 O(N)이 걸린다. 만약에 메뉴 해시테이블에 배달의 민족 이용자일때, 떡볶이 값이 반값으로 할인된다고 한다면 “떡복이” => [6500,3250] 이렇게 배열로 값을 저장함으로써 충돌을 막을 수 있다. 하지만, 많은 데이터가 셀에 배열로 저장되게 된다면 사실상 배열과 마찬가지로 O(N)의 시간복잡도가 걸릴 수 밖에 없다. 그러므로 해시 테이블을 O(N) 시간이 아닌 O(1) 시간에 검색가능하도록 구현해야 한다.

충돌을 피하기 위해서는 모든 셀에 값이 배열 형식이 아니게 들어갈 수 있게끔 데이터를 넓게 분산시킬 수도 있다. 하지만, 💥 데이터를 넓게 퍼뜨리면 그만큼 많은 메모리를 소비하므로 어느정도 균형을 맞추어야 한다.

부하율 : 데이터와 셀간의 이상적인 비율은 0.7(원소 7개 당 셀 10개) 이다.

해시테이블은 어떤 상황에서 효율적일까?

해시테이블은 키와 값으로 저장할 수 있는 데이터를 다룰 때, 유용하다.

예를 들면, array =[61,30,11,91,54,38,72];

배열로 선형검색을 한다면 O(N)의 시간 복잡도가 걸린다… 하지만 해시테이블로 변환한다면 O(1)단계만에 해결할 수 있다.

array_hash ={ 61 => true,30 => true,11 => true,91 => true,54 => true,38 => true,72 => true }

이렇게 해시 테이블을 사용하는 것을 “해시테이블을 인덱스로 사용하기”라고 부른다.

문제 1

한 배열이 다른 배열의 부분집합인지 알아내보자 arr1 = [“a”,”b”,”c”,”d”,”e”,”f”] arr2 = [“a”,”b”,”c”,”h”]

let largeArr, smallArr;
let isMatch = true;
if (arr1.length > arr2.length) {
  largeArr = [...arr1];
  smallArr = [...arr2];
} else {
  largeArr = [...arr2];
  smallArr = [...arr1];
}

let hash = {};
for (let x of largeArr) {
  hash[x] = true;
}
for (let x of smallArr) {
  if (!hash[x]) {
    isMatch = false;
    break;
  }
}
console.log("isMath", isMatch);
// 답: 'false'

길이가 작은 배열의 원소들이 길이가 큰 배열에 포함되면 부분집합이므로 길이가 큰 배열을 해시테이블로 생성하여 길이가 작은 배열을 루프를 돌면서 해시테이블에 있는 값인지 체크한다.