해시 테이블 + 선형 탐색 + 캐시?

Question

안녕하세요, 강사님 강의를 잘 듣고 있습니다! 선형 탐색에서 '클러스터링(덩어리 형성) 현상이 생길 수 있음'을 단점으로 언급해주셔서 궁금한 게 생겼습니다. 컴퓨터가 리스트를 읽어올 때 주변 값도 같이 가져와서 캐시 hit으로 성능이 높아진다고 알고 있는데, 그러면 덩어리 형성이 오히려 좋은 효과가 아닌가 싶습니다. 그렇지만 이 점이 충돌이 발생하기가 쉬우며, 고르게 분포가 되어있지 않기 때문에 해시 함수 관점에서는 단점인 것인지 여쭤보고 싶습니다

in hm · Answer

아..! '인접한 위치에 저장된 데이터가 같이 조회될 확률이 높다'는 지역성 개념이지만,
하지만 해시 테이블에서는 서로 무관한 데이터가 저장되기 때문에 캐시 hit 확률도 낮아지겠군요
그러므로 단지 시간복잡도만 늘리는 함수로, 단점이 크게 작용하게 되는군요!

yiyj10305235 · Answer

안녕하세요, in hm님! 강의를 주의 깊게 들어주시고 질문까지 해주셔서 감사합니다!   주변의 값을 같이 가져와서 캐시 hit 확률을 높이고 성능을 높이는건 데이터의 시공간 지역성을 기반으로 합니다. 즉 비슷한 위치에 저장된 데이터가 같이 조회될 확률이 높다 는 특성을 이용합니다.   해시 테이블의 경우에는 데이터를 저장할 위치, 즉 내부 배열의 인덱스를 결정할 때 해시 함수를 사용하게 됩니다. 데이터(key)에 대한 해시 함수 연산 결과를 인덱스로 사용하게 되는 거죠. 이때 해시 함수는 키 값을 해시 테이블 공간에 최대한 균등하고 무작위적으로 분포 시키도록 설계되며 이는 데이터의 논리적인 연관성, 인접성과는 무관하게 독립적인 결과를 반환합니다.   따라서 클러스터링이 형성되었을 때, 물리적으로 인접해있는 데이터들이 논리적으로도 연관이 있다고는 할 수 없습니다. 결론적으로, 물리적으로 인접하게 저장된 데이터들이 캐시의 공간적 지역성 이점을 얻을 만큼 의미 있게 '함께 조회될 확률'을 가지지 않는다는 것 입니다. 오히려 선형 탐색의 길이가 길어지는 비효율성으로 인해 O(1)의 평균 접근 속도를 저해한다는 점에서 단점으로 작용합니다.   제 답변이 도움이 되었으면 좋겠습니다. 궁금한 점이 있다면 언제든 편하게 다시 질문해주세요. 감사합니다!