(해시) 충돌은 1) 서로 다른 값이 동일한 해시를 뱉거나(해시 충돌) 2) 서로 다른 해시가 동일한 인덱스를 뱉는 경우를 말한다. 해시 자료구조를 구성할때 모든 key가 충돌한다면, 탐색에 O(n)이 걸린다. 모든 데이터가 하나의 인덱스에 저장(Separate Chaning)되거나 다른 인덱스에 순차적으로 저장(Open Addressing)될 것이기 때문이다. 저장할 값의 배열이 크지 않다면, Open Addressing 이 캐시 효율적이다. 연속된 공간에 저장한 데이터는 함께 캐싱될 것이고(cache line), spatial locality 에 따라 hit …

Read More

특정 집합 객체 요소에 순차적으로 접근 가능하도록 구현해놓은 객체. Iterator 패턴을 따라서 내부를 노출하지 않고 집합 객체의 구현에 종속되지 않아야한다. Iterator 를 제공하는 객체는 Iterator Protocol 을 따랐다고 표현하는데, 이는 언어마다 상이하다. 에를 들어 javascript 에선 Iteration Protocol 하위에 Iteration Protocol 과 Iterator Protocol이 존재한다. 구현은 프로그래밍 언어마다 다양할 수 있다. 보통 Iterable 객체와 묶여서 구현한다. python과 java 모두 Iterable …

Read More