1. 해시
해시 함수에 의해 얻어지는 값
2. 해시 함수
- 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
- 서로 다른 입력 값을 넣어도 해시 함수에 의해 동일한 결과 값이 나오는 경우가 있는데 이를 해시 충돌이라고 한다.
- 이 때, 해시 함수는 제곱, 나눗셈 등 산술연산을 이용하여 구현된 알고리즘
3. 해시 테이블
다음 아래 그림과 같이 해시 함수를 통해 인덱스를 알아내고 array[인덱스]에 키 값을 저장한다.
버킷 : 해시 함수로 부터 나온 결과 값으로 array의 인덱스 값에 해당해도 저장할 키 값을 가르킨다.
삽입 : 버킷이 해당하는 리스트의 목록 끝에 삽입
삭제 : 리스트에 주어진 키가 있는 경우 노드 삭제
4. 코드 구현
코드 참고 : https://www.geeksforgeeks.org/c-program-hashing-chaining/ hash function for string : https://en.cppreference.com/w/cpp/utility/hash
5. 참고 자료
1) 해시 함수 알고리즘 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jvioonpe&logNo=220708952160
2) 해시 테이블에 대한 이해 : https://bcho.tistory.com/1072
3) 해시 c++ 코드 구현 : https://www.geeksforgeeks.org/c-program-hashing-chaining