[Data Structures] 테이블(Table)과 해쉬(Hash)

1. 테이블 (Table) 자료구조의 이해

• 탐색대상을 단번에 찾을 수 있는 자료구조로, O(1)의 시간복잡도를 가진다
• 저장되는 데이터는 키(key)와 값(value)이 하나의 쌍을 이룬다 
• 키(key)가 존재하지 않는 값은 저장할 수 없다
• 모든 키(key)는 중복되지 않는다
• map 으로 불리기도 한다

//"UnderstandTable.c"
 
typedef struct _empInfo
{
    int empNum;    //직원의 고유번호
    int age;    //직원의 나이
} EmpInfo;
 
int main(void)
{
    EmpInfo empInfoArr[1000];
    EmpInfo ei;
    int eNum;
 
    printf("사번과 나이 입력: ");
    scanf("%d %d", &(ei.empNum), &(ei.age));
    empInfoArr[ei.empNum] = ei;    //단번에 저장
    printf("확인하고픈 직원의 사번 입력: ");
    scanf("%d", &eNum);
    ei = empInfoArr[eNum];     //단번에 탐색
    return 0;
}

 

 

2. 해쉬(Hash) 의 필요성

• 문제점: 직원 고유번호의 범위가 1000000~9999999라면 위와 같은 방식으로 데이터를 구성하려면 매우 큰 배열이 필요하다
• 예를 들어, 입사 직원의 고유번호가 입사년도+입사순서 로 구성된다면 ex) 20120003, 20120004... 이러한 직원의 고유번호를 활용해서 가공의 과정을 거친다

//"TableHashFunction.c"
 
typedef strcut _empInfo
{
    int empNum;    // 직원의 고유번호
    int age;    // 직원의 나이
} EmpInfo;
//해쉬 함수 - 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할
//여덞 자리의 수로 이뤄진 직원의 고유번호를 두 자리의 수로 변경한다
int GetHashValue(int empNum)
{
    return empNum % 100;
}
 
int main(void)
{
    EmpInfo empInfoArr[100];
    
    EmpInfo emp1={20120003, 42};
    EmpInfo emp2={20130012, 33};
    EmpInfo r1, r2;
    
    //키를 인덱스 값으로 이용해서 저장
    empInfoArr[GetHashValue(emp1.empNum)] = emp1;
    //키를 인덱스 값으로 이용해서 탐색
    r1 = empInfoArr[GetHashValue(20120003)];
    
    return 0;
}

출처: https://velog.io/@seochan99/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%85%8C%EC%9D%B4%EB%B8%94%EA%B3%BC-%ED%95%B4%EC%89%AC-4

    6. 체이닝 (Chaining)

• 위의 방법들은 열린 어드레싱 방법으로 충돌이 발생하면 다른 자리에 대신 저장한다는 의미
• 체이닝은 닫힌 어드레싱 방법으로 무슨 일이 있어도 자신의 자리에 저장을 한다는 의미 -> 자리를 여러 개 마련한다
  1. 배열을 이용하는 법 - 해쉬 값 별로 다수의 슬롯을 마련할 수 있으나 충돌이 발생하지 않을 경우 메모리 낭비가 심하다는 단점이 있다
   

       2.  연결 리스트를 이용하는 법 - 슬롯을 생성하여 연결 리스트의 모델로 연결해나가는 방식, 하나의 해쉬 값에 다수의 슬롯을 둘 수 있다. 따라서 탐색을 위해서는 동일한 해쉬 값으로 묶여있는 연결된 슬롯을 모두 조사해야 한다는 불편이 따른다.