해당 게시글은 CodeTree 강의를 참고하였습니다.
🤷♀️ 해싱
리스트나 배열에서 위치를 찾기 위해 인덱스를 사용하는데, 이것만으로는 원하는 코드를 작성하기 힘든 경우가 발생할 수 있습니다.
예를 들어, 회원정보를 관리하는데에 아이디를 가지고 알맞은 비밀번호를 찾는 경우가 그렇습니다.
이를 극복하기 위해 해시 함수를 사용할 수 있는데, 해시 함수는 임의의 데이터를 받아 그 데이터를 고정된 길이의 값으로 반환하는 역할을 하는 함수를 의미합니다.
예를 들어, 회원 정보를 해시 함수에 넣고 인덱스로 반환해서 해당 위치에 값을 저장하면서 원하는 코드를 구현해서 활용이 가능한 것이지요.
해싱은 들어온 순서 상관 없이 삽입, 삭제, 검색이 자주 일어나는 경우에 사용하기에 좋습니다. 그러나, 순서가 있는 경우에는 인덱스로 빠르게 처리할 수 있는 배열이나 리스트가 당연히 좋겠죠?
🤷♂️ 충돌
충돌은 서로 다른 입력이 해시 함수를 이용해서 나오는 고정된 길이의 값이 일치하는 경우 발생합니다.
충돌이 발생한 경우는 일반 배열이나 리스트로는 해결할 수 없고 (한 인덱스 위치에 여러 값이 들어갈 수 없기에) 가장 간단하게 연결리스트를 사용해서 해결이 가능합니다.
즉 동일한 결과지만 입력이 다른 값을 연결리스트로 연결해서 표현하는 것이지요.
그러나, 해당 연결리스트가 길어지면 그만큼 순회를 해야되기에 시간 복잡도도 증가해서 해싱을 쓰는 이유가 사라지게 될 수도 있으니 주의해야합니다.
그래서 때로는 충돌 자체를 최대한 줄이기 위해 저장하는 해시 테이블을 입력되는 데이터의 3~4배의 크기로 설정하기도 합니다.
