[알고리즘] 해시 테이블 구현해보기 - 해시 테이블 크기와 해시 함수

해시테이블을 구현할 때 고민되는 부분이 몇 가지 있다. 해시 테이블 크기와 해시 함수이다. 먼저 해시 테이블 크기를 정해보자.

---

해시 테이블의 크기

해시 테이블에서 원소의 개수 / 테이블의 크기를 load factor라고 하고, 원소의 최대 개수는 곧 삽입의 최대 횟수이다. load factor를 작게 유지하면 충돌이 덜 생겨 연산들이 O(1)에 동작하겠지만 cache hit rate가 줄고 메모리를 많이 차지한다. 반대로 load factor를 크게 유지하면 충돌이 많이 생겨 성능에 악영향을 줄 수 있다. load factor를 정하는 방식은 체이닝 기법이냐 개방 주소화 기법이냐에따라 나뉜다.

 

먼저 체이닝 기법은 충돌이 어느 정도 발생하더라도 load factor를 1 이하로 둔다. 반면 개방 주소화 기법에서는 0.75 정도로 둔다고 한다. 테이블의 크기는 그렇게 성능에 큰 영향을 미치지는 않는다고 하니 적당히 잡으면 된다. 또, 테이블의 크기를 소수로 두면 좋다고 하는데, 인터넷 검색이 가능한 경우 그렇게 하면 좋겠지만 꼭 쓸 필요는 없다. 실무에서 많이 사용하는 경우와 테이블의 크기가 소수인 이유는 챗GPT에게 물어보았지만 생각보다 내용이 딥해서 패스했다.

---

해시 함수 정하기

테이블의 크기를 M이라고 하면 정수에 대한 해시 함수는 M으로 나눈 나머지로 사용하면 딱 좋다. 문자열에 대한 해시 함수가 문제인데, 간단히 각 문자별로 아스키코드를 더하고 M으로 나눈 나머지로 정한다면 충돌이 굉장히 많이난다. 아스키코드 값이 최대 127로 정해져있기 때문이다. 따라서 아래와 같은 방법을 많이 사용한다.

std::size_t customHash(const std::string& str) {
    std::size_t hash = 0;
    
    for (char ch : str) {
        hash = hash * 31 + static_cast<std::size_t>(ch);
    }
    
    return hash;
}

size_t는 unsigned_int이고 static_cast<>() 함수는 <>안의 자료형으로 캐스팅해주는 함수이다. 31을 곱해주는 이유는  해시 테이블에 데이터를 균일하게 분산시키려면 소수가 아닌 숫자보다 소수를 곱해주는 편이 더 좋고 비트-시프트 연산을 사용하여 효율적으로 연산할 수 있기 때문이다. 실무에서는 단순히 소수가 아니라 철저한 분석과 고려 하에 정한다고 한다.