open addressing
-
20221102 TIL 해시 충돌을 어떻게 해결할 것인가TIL 2022. 11. 2. 21:04
오늘은 홀맨님이 맵 자료구조를 직접 구현해서 푼 코딩 문제 풀이를 공유해주셨다. 풀이처럼 필요에 따라 자료구조를 직접 구현할 경우도 있다고 하셔서 해시맵이 어떻게 구현되어 있는지 찾아보았다. 먼저 '맵'은 키와 키에 해당하는 값의 쌍으로 데이터를 다룬다. 그리고 키로 키에 해당하는 값을 바로 조회할 수 있기 때문에 어떤 값을 조회할 때 매우 유리한 자료구조이다. 해시 맵은 이름처럼 해시를 이용한 맵이다. 키에 대한 해시값으로 값을 저장하고 조회한다. 그런데 해시함수는 반환 값으로 가능한 경우의 수가 정해져 있기 때문에 그 개수 이상의 값을 해시함수에 돌렸을 때 무조건 겹치는 값이 나올 수 밖에 없다. 따라서 해시 함수를 돌렸을 때 동일한 결과가 나올 수 있는데, 이를 해시 충돌이라고 하고, 해시 맵에서는..