Open Addressing을 쓰는 해시 테이블 시간 복잡도

Open Addressing 의 삽입 연산은 탐사를 통해서 빈 인덱스를 찾고, 탐색과 *삭제 연산은 원하는 key를 갖는 데이터 쌍을 찾는다.

<Open Addressing을 사용하는 해시 테이블의 연산들도 평균 시간 복잡도로 표현>

해시 테이블 연산들을 분석할 때는 load factor라는 것을 사용합니다. load factor- alphaα는 해시 테이블이 사용하는 배열의 크기를 m, 해시 테이블 안에 들어 있는 데이터 쌍 수를 n이라고 할 때:
Open addressing을 할 때 해시 테이블의 연산들을 분석할 때는 load factor는 굉장히 중요한 역할을 합니다. 해시 테이블 안에 배열의 크기보다 많은 key - value 쌍을 저장할 수 없기 때문에 load factor - alphaα는 항상 1보다 작다고 가정합니다. [alpha] < 1