Hash(해시)

Hash?

key와 Value로 이루어진 데이터 구조를 의미한다. 

파이썬에서는 딕셔너리 타입이 해시 테이블과 같은 구조이다.

 

장점

데이터 저장/검색 속도가 빠르다.

해시는 키에 대한 데이터가 있는지 확인이 쉽다.

 

단점

일반적으로 저장공간이 좀더 많이 필요하다.

여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.

 

시간복잡도

일반적인 경우(충돌이 없는 경우) : O(1)

최악의 경우(모든 경우에 충돌이 발생하는 경우) : O(n)