📄 Hash Table
- Key, value로 데이터를 저장하는 구조
- Hash란 해시 함수에 의해 얻어지는 값
✏️ Hash function (Hash algorithm)
- 데이터를 최종 사용자가 원문을 추정하기 힘든 더 작고, 뒤섞인 조각으로 나누는 것
- 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터(해시 값)로 매핑하는 함수
- MD5, SHA, Whirlpool, RIPEMD, CRC32 등
🚀 해시 함수의 특성
- 해시 함수는 단방향 함수로 작용
- 해시 함수에서는 눈사태 효과가 매우 잘 나타남
- 해시 함수는 매우 빨리 연산할 수 있음
- 해시 함수의 결과값은 충돌(Hash Collision)이 일어나지 않음
※ 중복은 허용하나, 충돌 해결 의무 있음 - 해시 함수는 결정론적
✏️ Hash Collision
- 서로 다른 문자열을 해시한 결과가 동일한 경우
- 해시 함수를 H()라고 했을 때 서로 다른 문자열 s1과 s2에 대해서 H(s1) = H(s2)인 경우
- 해시 테이블을 구현할 때 해시 충돌이 일어나게 되면 Chaining 혹은 Open addressing을 통해서 해결해야한다.
이미지 출처
노력하는 게임 개발자