해시 테이블
-
해시 테이블 구현 및 테스트프로그래밍 기초/알고리즘 2022. 1. 7. 17:51
해시 테이블 구현 STL의 vector를 이용하여 해시 테이블을 구현한다. 해시 테이블 기본 클래스 해시 테이블 처리 중 충돌 처리에 따라 함수를 나누기 위해 기본 기능을 가진 클래스를 구현한다. HashTable.h #pragma once #include "../Common.h" #include #include using std::string; /// /// 해시 테이블에서 사용할 해시 함수 /// enum class HashFunction { Division, Multiplication, }; /// /// 해시 테이블의 구성 요소 테스트를 위한 베이스 클래스 /// class HashTable { public: HashTable(HashFunction hashFunction = HashFunctio..
-
해시 테이블 알고리즘프로그래밍 기초/알고리즘 2021. 12. 22. 14:42
해시 테이블 해시 테이블은 원소의 위치가 값에 의해 계산되어 결정되는 자료구조로 해시 테이블의 값을 정하는 건 해시 함수인데, 이 함수를 통해 각각의 원소의 자리를 상수 시간에 계산할 수 있다. 해시 테이블에 원소가 차 있는 비율을 적재율이라 하며, 테이블의 크기가 m이고 테이블에 저장된 원소의 개수가 n이면 적재율은 n/m이 된다. ※ 테이블의 모든 영역에 값을 적절하게 분배하지 못하는 경우 성능이 떨어질 수 있다. 해시 함수 해시 함수는 해시 테이블에서 키 값을 테이블의 인덱스로 만들어 주는 함수로 다음의 성질을 가진다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 만약 데이터가 어느 한 인덱스에 몰려서 저장되게 된다면 충돌이 자주 발생하여 성능에 악영향을 미치기 때..