테이블과 해쉬 개념

테이블은 사전과 같이 단어를 통해 의미를 찾는 행위와 비슷하다. 내가 가진 단어를 검색해 의미를 알수 있듯, 테이블 자료구조는 내가 가진 키를 활용해 값을 넣고 찾을 수 있다.

“저장 되는 데이터는 키와 값이 하나의 쌍을 이룬다”

이렇듯 테이블에 저장되는 모든 데이터들은 키가 있어야 하며 키는 고유한 값을 가져야한다.

StuInfo stuInfoArr[1000];
    StuInfo student;
    int stuNum;

    printf("학번과 나이 입력: ");
    scanf("%d %d", &(student.stuEmp), &(student.age));
    stuInfoArr[student.stuEmp] = student;

위의 예시에서는 고유한 학생번호를 이용하여 배열에 값을 넣었다. 이렇게 코드를 구성하면 학생의 수가 1000명을 넘었을 때 문제가 발생한다. 이러한 문제를 해결 하기 위한 해결책으로 hash함수를 사용 할 수 있다.

예를 들어

int Hash(int stuNum)
{
    return stuNum % 100;
}

위의 예시와 같이 사용하면 학번의 끝 2자리를 바탕으로 값을 저장 할 수 있기때문에 , 상대적으로 적은 저장공간을 사용 할 수 있다.

하지만 위의 방식에는 충돌이라는 문제가 있다. 예를 들어 1301 과 1401이라는 학번을 갖는 학생들은 같은 공간에 데이터가 저장되어야 한다.

충돌 문제를 해결하기 위한 방법으로 선형 조사법과 이차 조사법이 있다.

• 해쉬함수 key % 7

해쉬함수가 key % 7 이라고 할때 2와 9 가 같은 공간에 저장된다. 선형 조사법은 저장할 공간에 이미 값이 있을 때 바로 옆 f(x) + 1위치에 값을 저장하는 것이다. f(x) + 1 위치에도 값이 저장되어 있다면 + 1… 씩 저장 위치를 이동 시킨다.

선형 조사법을 사용하면 특정 위치에 데이터가 몰리는 문제가 발생하는데, 조금 더 멀리 데이터를 저장하면 어떨까 하는 생각으로 만들어 졌다.

이차 조사법은 f(x) + 1 ^ 2 → f(x) + 2 ^ 2 으로 값을 저장한다.

충돌 문제를 해결하기 위한 다른 방법으로 사용할 수 있는 방법중 하나는 체이닝이다.

위의 예시와 같이 LinkedList를 사용해 같은 해쉬 값을 갖는 데이터들을 엮는다.

위의 방식을 “닫힌 어드레스 방식”이라고 부른다. 체이닝을 사용하면 하나의 해쉬값으로 묶여 있는 슬롯 들을 모두 검사해야 한다는 단점이 있지만, 좋을 해쉬값을 사용해서 이러한 문제점을 해결 할 수 있다.

 

테이블 해쉬 코드(c++): https://boiling-fowl-6d6.notion.site/c-140f3da88dd546f4bd32a9c7cbbe5a22

테이블 해쉬 코드(c): https://boiling-fowl-6d6.notion.site/c-6f5cf4e65c4a483086845db21ace545a