해시(Hash) 자료구조와 충돌 회피 기법
해시 자료구조는 16자리의 번호의 일부분을 index로 사용하는 자료구조입니다. 해시 함수란? 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수 왜 일부분만 사용하는가? 모든 해시를 배열로 가지고 있으면 10^16의 배열이 필요합니다. 이는 40페타 바이트를 차지하게 됩니다. 그렇기에 모든 hash 값을 사용하는 게 아닌 일부분만의 값을 사용하여 해시 테이블을 생성합니다. 충돌 회피 방법 1. Chaining Key가 중복된 노드를 LinkedList로 연결하여 관리합니다. Java의 STL 자료구조는 Chaining 방식을 사용합니다. 주의사항: 충돌이 빈번할수록 성능이 안 좋아지고, 해시 충돌이 한 곳으로 몰렸다면 O(N)의 시간 복잡도를 가질 수 있습니다. ...