해시 충돌

(해시) 충돌은 1) 서로 다른 값이 동일한 해시를 뱉거나(해시 충돌) 2) 서로 다른 해시가 동일한 인덱스를 뱉는 경우를 말한다.

해시 자료구조를 구성할때 모든 key가 충돌한다면, 탐색에 O(n)이 걸린다.

1. 모든 데이터가 하나의 인덱스에 저장(Separate Chaning)되거나
2. 다른 인덱스에 순차적으로 저장(Open Addressing)될 것이기 때문이다.

저장할 값의 배열이 크지 않다면, Open Addressing 이 캐시 효율적이다. 연속된 공간에 저장한 데이터는 함께 캐싱될 것이고(cache line), spatial locality 에 따라 hit ratio가 높을 것이기 때문이다. 파이썬이 오픈 어드레싱 방식을 쓴다.

반면, 배열이 커지면 배열이 한꺼번에 캐싱되지 않아 캐시 효율은 떨어진다. 그러면 Separate Chaining의 효율이 높아지는데, 리스트에서 remove 연산의 효율이 배열보다 좋기 때문이다.(자바의 Hashmap 은 Separate Chaining을 쓴다)

refs

• NAVER D2
• caching - Cache Performance in Hash Tables with Chaining vs Open Addressing - Stack Overflow

links

• cache line
• locality