자료구조 뿐만 아니라 어떤 개념에 대해 이해할 때 탄생 배경을 아는 것, 그리고 정확하지는 않더라도 개인적으로 추측해보는 과정이 제일 중요하다고 생각한다.
HashMap의 탄생 배경은 배열이다. 배열은 데이터를 하나의 논리적인 개념으로 묶어 사용할 수 있도록 편의성을 제공하지만 한 가지 큰 단점이 있는데, 바로 인덱스와 저장된 데이터 사이의 관계가 전혀 없다는 것이다. 즉, 배열에서 데이터를 활용하기 위해서는 배열의 모든 데이터에 접근해야 하는 것이다. 따라서 이 인덱스와 저장된 데이터 사이에 관계를 만들어 배열의 모든 데이터에 접근할 필요 없이 바로 해당 데이터가 저장된 위치를 알아낼 수 있도록 한 것이 바로 HashMap이다.
간단하게는 데이터를 HashCode라는 함수를 통해 int형으로 변환한 뒤 이를 배열의 길이로 나눠 남는 나머지를 인덱스로 설정을하고 그 인덱스에 데이터를 집어넣는다. 근데 이 과정에서 나머지를 사용하면 보나마나 무조건 같은 나머지 값을 가지는 데이터가 발생하는데, Seperate Chaining이라고해서 이중 배열같은 느낌으로 같은 인덱스 안에서 링크드리스트를 만들어서 관리한다.
평소 HashMap은 데이터 검색에 있어서 O(1)의 속도를 가진다고해서 나는 모든 데이터가 바로 고유의 값을 가지고 검색이 되는 줄 알았는데 사실 그게 아니고 Seperate Chaining 구조라면 데이터마다 검색되는 속도가 다르다고 생각하면 된다. (맞겠지? 맞을것이다. 이론상으로 검색 속도가 다를 수 밖에 없음.) 재수없으면 O(n)이 될 듯?(저장된 모든 데이터의 인덱스가 동일할 경우.)