각 값들의 명확한 차이점을 생각해야함

1. 자릿수 선택: 키의 값 중에서 일부 자릿수만 골라내서 인덱스를 생성하는 함수

2. 자릿수 접기: 키의 각각의 자릿수를 더해서 인덱스를 생성하는 함수

3. 모듈로 연산: 키를 해쉬 테이블의 크기로 나눈 나머지를 인덱스로 생성하는 함수

세 번째 방법이 가장 사용빈도가 높다고 한다.

해시 함수(hash function)는 임의 크기의 입력 데이터를 고정된 크기의 (보통은 작은) 출력으로 매핑하는 함수입니다. 이 출력값을 해시 값(hash value) 또는 해시 코드(hash code)라고 합니다. 해시 함수는 빠른 검색을 위해 데이터 구조에서 중요한 역할을 합니다, 대표적으로 해시 테이블(HashTable)에서 사용된다고 생각합니다.

데이터에 맞게 기준을 설정하고 나눌 데이터의 글자에 맞게 해시 테이블에 담는다.

 데이터를 해시 함수에 넣을때 같은 포인터에 여러개가 연결되지 않도록 (같은 바구니에 담기지 않도록) 데이터의 구조를 파악해 데이터 마다 고유한 값이 나오도록 연산해 주어 해시 테이블에 적절하게 요소가 분배되도록 만들어야 한다.

데이터 값을 비트/바이트 단위로 수학적으로 연산하여,

데이터의 값에 따라 다르며 크기와 상관없이 동일한 해시값 크기를 가지는 해시 함수가 이상적입니다.

md-5, sha-256 등 흔히 쓰이는 해시 함수는 모두 이러한 방식으로 계산됩니다.

간단한 예를 들어보자

a-z까지의 알파벳으로 이루어진 문자열이 들어올 때 각 알파벳들의 개수를 카운팅하려면 어떻게 해야 할까?

알파벳이라는 데이터를 통해 각 알파벳이 저장될 위치를 결정할 수 있다면 다음과 같은 코드를 작성할 수 있다.

#include <string>
#include <iostream>

using namespace std;

int main()
{
string text = "aaabbbcccadd";
int cnt[26] = {};

for (int i = 0; i < text.size(); ++i)
{
char alphabet = text[i];

// 저장될 위치
int index = alphabet - 'a';
cnt[index] ++;
}

// 출력
for (int i = 0; i < 26; ++i)
{
char alphabet = i + 'a';
cout << alphabet << " : " << cnt[i] << endl;
}

return 0;
}

이 예제는 굉장히 축소된 해시 예제이지만, 약식 해시테이블로서 코드를 다시 작성해볼 수 있다. 

'a'와 같은 알파벳들은 데이터 그 자체로서, 해시테이블에 저장될 값(value)과 대응된다.

알파벳의 아스키 값은 데이터의 고유한 식별값으로서, 키(key)와 대응된다.

배열[26]은 해시 테이블의 저장공간으로서, 버킷(Bucket)과 대응된다.

alphabet - 'a'라는 계산식은 각 데이터가 저장될 위치를 결정하는 방법으로서, 해시 함수에 대응된다.

hash function 통해 계산된 index는 실제 값이 bucket에 저장될 위치로서, 해시와 대응된다. 

입력값으로 해시키를 만들고 해시키를 해시 테이블의 크기로 나눈 나머지 값을 반환하게 만든다.

해시함수를 정의하는 것들은 대표적으로 다음과 같은 것들이 있습니다.

1.자릿수 선택(digit selection)

     : 키값 중, 일부 자릿수 골라내어 인덱스 생성

     : h(121234345656) ⇒ 113355 *key값 (예.주민번호) 중 홀수자릿수 선택

2.자릿수 접기(digit folding)

     : 키값 각각의 자릿수를 더해 인덱스 생성

     : h(123456) = 1+2+3+4+5+6 = 21

3.모듈로 연산(modulo function) - 많이 사용됨.

     : 키를 해쉬테이블의 크기로 나눈 나머지를 인덱스로 생성

     : h(157) ⇒ mod(157) = 7 *h(KEY) = KEY MOD TABLESIZE

https://makemethink.tistory.com/139?category=768133

적절한 기준을 세워 만든다

입력값의 특징을 잘 분석하여 최대한 겹치지 않는 값을 반환하고 해시테이블에 담을 수 있도록 만들어야 한다.

1. 나누기 방법 : 원소를 해시 테이블의 크기로 나누어 나머지 값을 테이블 주소로 사용.

2. 곱하기 방법 : 반대로, 원소를 0과 1사이의 소수로 대응 시킨 다음 해시 테이블 크기 m을 곱하여 0~m~1 사이로 팽창.

참고 : https://smujihoon.tistory.com/165

각각의 최솟값을 만들어 해시 함수를 만들어 해시 테이블에 정렬하면 될것같습니다.

가능한 한 충돌이 일어나지 않으면서 값을 분류할 수 있도록 만든다. 다만, 충돌을 피하려고 분류 기준을 까다롭게 하면 필요한 배열의 개수가 많아질 수 있으므로 충돌을 얼마나 허용할 때 검색 시간이 가장 짧아지는지를 생각하면서 함수를 만드는 게 좋을 것 같다.

각 값들을 분류하고자 하는 기준을 세워서 해시 함수를 만들어 해시 테이블에 정렬하면 됩니다.

해시함수를 만드는 방법은 다음과 같다. 사실 더 많이 있는데 https://itwiki.kr/w/%ED%95%B4%EC%8B%9C 이 곳을 참고하면 될 것 같다. 

x = 데이터 값, m = 해시테이블 크기 
1. 나누기 방법
데이터값(정수일 경우 그냥 사용, 문자(열)의 경우 아스키코드 사용)를 해시 테이블의 크기로 나누어 나머지의 값을 테이블 주소로 사용해 저장하는 방식. 이 방법은 해시테이블 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 수축시킨다.
h(x) = x mod m 
2. 곱하기 방법
입력값을 0과 1 사이의 소수에 대응시킨 후, 해시 테이블 크기 m을 곱해 해시값을 0<h(x)<m에 대응시킨다. 이 방법을 쓰려면 해시함수의 특성을 결정짓는 상수 A(0<A<1)를 미리 준비해야 한다.
h(x) = [m(xA mod 1)] 

3. 개방주소방법(충돌해결법 중 하나)의 경우

- 선형조사법: h_i(x) = (h(x) + i) mod m

- 이차원조사법: h_i(x) = (h(x) + c_1i^2 + c_2i) mod m

- 더블 해싱: h_i(x) = (h(x) + if(x)) mod m -> 권장: h(x) = x mod m, f(x) = 1+(x mod m)

데이터의 특정 값이 중복되는 부분을 파악하여 배열(해시 함수)로 만들고,

중복되지 않는 부분을 연결리스트로 구분지어 만들 수 있습니다.

데이터 형태에 따라서 최대한 충돌 되지않는 선에서 분류하고 만든다.

데이터의 형태를 보고 , 어떤 기준을 세워서 함수를 만들면 된다. 되도록 효율적인 기준.

데이터의 형태를 보고, 공통적으로 구분하여 정리할 수 있는 방법을 생각하여 함수를 만들면 될 거 같다.