파이썬의 딕셔너리는 어떻게 구현되어 있을까? -해시-
파이썬에는 {} 이렇게 생긴 구조를 dict(딕셔너리)라 부릅니다. 이 딕셔너리는 해시 구조로 이루어져있는데, 덕분에 원하는 키(key)에 따른 값(value)를 바로 추출할 수 있게 설계되어 있습니다. 해시 해시는 공간을 좀 더 사용해 시간을 축소시키며 (공간와 시간을 맞바꾼 기법) 데이터의 양이 어떻든 일반적인 경우 항상 O(1)을 기대할 수 있습니다. 해시는 특정 키(key)를 해시 함수를 통해 해시 테이블의 주소값으로 변경합니다. 이 과정을 해싱(hashing)이라고 합니다. 해시의 효율성 해시 함수는 해싱의 효율성을 결정하는 결정적인 요인입니다. 해시 테이블의 특정 부분만 밀도가 높아서도 안되고, (테이블 사용 효율) 연산도 빨라야 하며, 무엇보다 해시 함수 값의 충돌이 적어야 합니다. 로드 팩..
소프트웨어/자료구조 + 알고리즘
2021. 4. 4. 04:51
