7. 삽입은 재귀적으로 동작해야 하기 때문에 실제 삽입 구현 함수를 따로 만들겠습니다. 삽입 함수에서는 순환 여부를 검사해야 합니다. 그러나 방문한 위치의 모든 값을 기억하는 것은 부담이 클 수 있습니다. 그러므로 여기서는 단순히 재귀 호출 횟수가 몇 회 이상이 되면 순환으로 간주하겠습니다. 이때 최대 재귀 호출 횟수는 해시 테이블 크기와 같게 설정할 것이며, 이러한 방식의 구현은 좋은 성능을 보여줍니다.
void insert(int key)
{
insert_impl(key, 0, 1);
}
void insert_impl(int key, int cnt, int table)
{
if (cnt >= size)
{
std::cout << key << " 삽입 시 순환 발생! 재해싱이 필요합니다!" << std::endl;
return;
}
if (table == 1)
{
int hash = hash1(key);
if (data1[hash] == -1)
{
std::cout << table << "번 테이블에 " << key << " 삽입" << std::endl;
data1[hash] = key;
}
else
{
int old = data1[hash];
data1[hash] = key;
std::cout << table << "번 테이블에 " << key << " 삽입: 기존의 " << old << " 이동 -> ";
insert_impl(old, cnt + 1, 2);
}
}
else
{
int hash = hash2(key);
if (data2[hash] == -1)
{
std::cout << table << "번 테이블에 " << key << " 삽입" << std::endl;
data2[hash] = key;
}
else
{
int old = data2[hash];
data2[hash] = key;
std::cout << table << "번 테이블에 " << key << " 삽입: 기존의 " << old << " 이동 -> ";
insert_impl(old, cnt + 1, 1);
}
}
}
실제 삽입 구현 함수는 세 개의 인자를 받습니다. key는 키를 의미하고, cnt는 재귀 호출 횟수이며, table은 키를 삽입할 테이블 번호입니다.