set/dictionary는
hash table
hash collision을 막는 방법으로는 closed hashing(open addressing, 같은 의미인데 하나는 closed, 하나는 open...)
따라서, 특정 element가 set/dictionary에 존재하냐는
element의 hash값을 구하고 그 위치만 따지면 되므로 O(1)
참고자료:
stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented
How are Python's Built In Dictionaries Implemented?
Does anyone know how the built in dictionary type for python is implemented? My understanding is that it is some sort of hash table, but I haven't been able to find any sort of definitive answer.
stackoverflow.com
[python] 자료구조 - 해시 테이블(Hash Table)
해시 테이블(Hash Table) 해쉬 테이블은 키와 밸류를 기반으로 데이터를 저장한다. 파이썬에서는 딕셔너리가 있어서 굳이 만들 필요는 없는데, 아무래도 파이썬으로 코드를 짜면 간단해서 파악하
jinyes-tistory.tistory.com
[python] 자료구조 - 오픈 해싱(Open Hashing)
오픈 해싱(Open Hashing) 오픈 해싱은 해시 테이블의 충돌 문제를 해결하는 대표적인 방법중 하나로 체이닝(Separate Chaining) 기법이라고도 한다. 만약 해시 값이 중복되는 경우, 먼저 저장된 데이터에
jinyes-tistory.tistory.com
[python] 자료구조 - 클로즈 해싱(Close hashing) / Open Addressing
클로즈 해싱(Close Hashing) 클로즈 해싱은 해시 테이블의 충돌 문제를 해결하는 방법 중 하나로 Linear Probing, Open Addressing 이라고 부르기도 한다. 구조는 간단하다. 위 이미지에서 John Smith와 Sandra D..
jinyes-tistory.tistory.com
'CS' 카테고리의 다른 글
| [Python]List comprehension에서 if else 쓰기 (0) | 2020.10.30 |
|---|---|
| (미완)Faiss, Facebook AI Similarity Search (0) | 2020.10.29 |
| (미완)[Elasticsearch]특징 (0) | 2020.10.29 |
| Inverted index 이해하기 (0) | 2020.10.29 |
| (미완)[Docker] option 정리 (0) | 2020.10.21 |