Hashing

해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다.
즉 해쉬 알고리즘은 해쉬를 하는 방법에 대해 절차적으로 명세한다.
이를 이용해 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.
기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던것에 비해,
해쉬를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.
해시 알고리즘

문자열을 해싱하면 더 빠르게 검색가능함
일정한 문자열 = O(1)

mapping

n=테이블 크기
m=문자열 크기

#define SIZE 10
char* hash_table[SIZE];

int hash(char* str) {
    int sum = 0;
    for (int i = 0; str[i]; i++) {
        sum += str[i];
    }
    return sum % SIZE;
}

void put(char* key, char* value) {
    int idx = hash(key);
    hash_table[idx] = value;
}

O(m)

for (int i = 0; i < n; i++) {
    if (strcmp(arr[i], key) == 0)
        return i;
}

O(n*m)

hash가 훨씬 빠름
ex) 데이터 개수가 100만개 있다고 가정하자. for문으로 돌리면 100만개 데이터들을 하나씩 입력받은 문자열과 비교하기 때문에 1000000*m이다.
hash의 경우 문자열 m개를 hashing 후 그 index를 반환 받기 때문에 O(m)만 걸린다.
jtim을 해싱하는 경우 106 + 116 + 105 + 109 = 436, 435%table_size 여기서table_size=1000000이였으므로 436번째 인덱스에 jtim이 저장된다.