Hash Function
어떠한 값을 넣었을때, 일련의 계산과정을 거쳐서 index 값으로 변환하는 Function.
Hash Table
Hash Fuction을 통해 나온 Index값 기준으로 해당 구역에 원하는 값을 넣어 나중에 Key값을 통해 값을 찾고자 할때 다시 Hash Function을 통해 나온 Index값으로 바로 찾을 수 있다 = O(1)
Hash Collision
Hash Function을 통해 생성된 Index의 구역에 값을 저장하려 하니 이미 같은 Index값이 존재했을때 충돌이 발생되는데 이것을 Hash Collision이라고 한다.
이 때 Channing을 써서 Index구역에 값을 계속해서 달아주는 방법을 쓸 수 있는데, 이렇게 되면 한번에 가져온다는 이점을 이용하지 못하여 이를 해결하기 위해 여러 방법이 도출되었다.
1) 선형조사
- 빈 index를 찾을 때까지 다음 index로 넘어간다.
- 특징 : 연속해서 값이 있을 경우 너무 많은 원래 index와 너무 많은 차이가 발생하여 연산 과정이 많아진다
2) 이차원 조사
- 선형조사와는 다르게 바로 다음 index가 아닌 이차 함수로 Jump하여 본다.
- 특징 : 이 또한 빈 index를 찾을 때 까지 다음 index로 넘어가는 연산이 반복될 수 있다.
3) 더블 해싱
- 두개의 Hash Function을 사용한다.
- 첫번째 함수를 통해 빈 index를 찾았다면 넣어준다
- 만약 충돌이 일어난다면 두번째 함수를 또 돌려서 넣어준다.
- 특징 : Hash Function을 두개 쓰면 충돌이 일어나더라도 중복된 index가 걸릴 확률이 낮음
Secure Hash Algorithm (SHA)
대표적인 Hash Function이며 주로 사용되는 것은 SHA-2 함수군으로 SHA-256, SHA-512가 있다.
256의 의미는 해싱했을때 2^256개의 해시값중 하나가 된다는 뜻이다.
:)