Hashing

Hashing은 효율적으로 자료를 저장하고 가져오기위한 자료구조입니다.
이것은 키값을 해쉬함수를 통해 자료를 저장할 특정 인덱스를 구하고 해당 인덱스에 자료를 저장합니다. 궁극적으로 키 값과 자료가 매핍되는 것입니다.

Hasing의 구성 요소

• Key
  Key는 해쉬 함수에 들어가는 값으로 Value값이 저장될 인덱스를 결정하게 됩니다.

• Hash Function
  Hash Function은 Key를 입력 값으로 받고 인덱스를 반환합니다.

• Hash Table
  해쉬 테이블은 자료 구조로 키와 값을 매핍합니다.
  해쉬는 데이터들을 각 데이터의 고유한 인덱스에 저장합니다.

Hashing은 어떻게 작동하는가?

우리가 사용자 정보를 가지고 있다고 가정해봅시다.
각 사용자의 정보는 다음과 같습니다.

{ 
{ name: 'ab', age: 15, sex: 'male' },
{ name: 'cd', age: 16, sex: 'female' },
{ name: 'efg', age: 17, sex: 'male' }
}

우리는 사용자 이름을 기반으로 age와 sex에 대한 정보를 가져오고 싶습니다.
그렇기 때문에 사용자 이름은 Key가 됩니다.
이를 염두에 두고 다음과 같은 절차를 밟으면 됩니다.
1. 각 키에 해당하는 수 구하기
a는 1 b는 2 c는 3 ... 형식으로 각 알파벳에 숫자를 부여한다고 하겠습니다.
그럼 이름 문자열은 아래와 같은 값을 가지게 됩니다.

“ab” = 1 + 2 = 3,
“cd” = 3 + 4 = 7 ,
“efg” = 5 + 6 + 7 = 18

2. 구한 수를 특정 숫자로 나누기
   위와 같이 구한 특정한 값으로 나눠 나머지를 구합시다.
   여기서는 7로 나눈 나머지를 구한다고 가정하겠습니다.

“ab” in 3 mod 7 = 3,
“cd” in 7 mod 7 = 0,
“efg” in 18 mod 7 =4

이렇게 구한 값은 인덱스가 됩니다.

이를 이용해서 정보를 저장하면 아래와 같이 인덱스에 각 이름에 대한 정보가 들어가게 됩니다.

Hash functions의 유형

1. Division Methid
2. Mid Square Method
3. Folding Method
4. Multiplication Method

좋은 Hash functions의 조건

1. 효율적인 계산
2. 균일하게 키를 분배
3. 충돌의 최소화
4. 테이블의 크기에 비해 적은 저장된 값

충돌

충돌이란 어떤 값을 Hash Function을 이용해 인덱스를 구했을 때 해당 인덱스에 이미 다른 값이 저장되어 있을 경우를 말합니다.
즉, 서로 다른 키 값이 Hash Function을 통해 반환 된 인덱스 값이 같은 것입니다.

충돌 해결법

1. Chaining
   해당 인덱스안에 배열로 값들을 여러 개 저장하는 것입니다.
   서로 다른 키 값에 대해 같은 인덱스를 반환하면 배열에 같이 저장하는 것입니다.

2. Open Addressing

   • Linear Probing
     충돌이 일어날 경우 순차적으로 다음 인덱스에 값이 들어갈 수 있는지 검토하고 들어갈 수 있으면 들어갑니다.

   • Quadratice Probing
     충돌이 일어날 경우 특정 수에 제곱한만큼 인덱스를 이동해 값이 들어갈 수 있는지 검토하고 들어갈 수 있으면 들어갑니다.

   • Double Hashing
     충동이 일어날 경우 해싱을 한번 더 한 뒤 인덱스를 구합니다.

Hash의 이점

• 다른 데이터 구조보다 더 나은 동기화
• 검색,삭제, 삽입에서의 아주 빠른 속도

Hash의 단점

• 많은 충돌이 있을 때 비효율적
• 충돌은 피할 수 없음
• Null값을 허용하지 않음