📌해시
해시는 Key-value쌍으로 데이터를 저장하는 자료구조로, 데이터의 효율적인 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수다.
이 때 매핑 전 원래 데이터의 값을 키(Key), 매핑 후 데이터의 값을 해시값(Hash value) 또는 해시코드, 매핑하는 과정 자체를 해싱(hashing) 이라고 한다.
해시 함수의 가장 기본적인 성질은 두 해시 값이 다르면 원래의 데이터의 값도 다르다는 것이다.
하지만, 같은 해시값을 가지고 있더라도 원래의 데이터가 꼭 같은 것은 아니다.
파이썬에서는 딕셔너리(Dictionary) 타입이 해쉬 테이블과 같은 구조다.
기본적으로는, 배열로 미리 Hash Table 크기만큼 생성해서 사용한다.
검색이 많이 필요한 경우, 저장, 삭제, 읽기가 많은 경우, 캐쉬를 구현할 때 주로 사용된다.
- 장점
데이터 저장/검색 속도가 빠르다.
해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽다. - 단점
일반적으로 저장공간이 좀더 많이 필요하다.
여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다. (충돌 해결 알고리즘) - 시간 복잡도
일반적인 경우(충돌이 없는 경우): O(1)
최악의 경우(모든 경우에 충돌이 발생하는 경우): O(n)
