자료구조

선형 자료구조

1. 스택
2. 힙
3. 해시맵/ 해시테이블
   - 해시함수: 임의의 크기의 데이터를 일정한 크기의 데이터로 매핑하는 함수
   • 좋은 해시함수의 특성:
     - 충돌이 적고, 계산이 빠르고, 해시값이 균등하게 분포하도록 해야 함
     • ex) modulo 연산
   • 로드펙터: n/k (아이템 개수 / 전체 버켓 사이즈)
   • 구현방식:
     - 체이닝: 키값이 충돌하면 연결리스트 형태로 데이터를 저장
     - 오픈어드레싱: 키값이 충돌하면비어있는 탐색을 통해 비어있는 버켓을 찾음
   • 오픈어드레싱 방식은 linear probing으로 구현되는데, 값이 많이 저장될수록 1) 탐사 속도가 느려지고, 2) 데이터가 고르게 분포되지 않는다는 단점이 있음
   • 오픈어드레싱방식은 버켓 사이즈 이상의 데이터는 저장할 수 없음
   • 따라서, 일정 로드펙터 기준 이상이 되면 새로 해시맵 공간을 할당해 리해싱 작업을 진행함
   • 파이썬은 오픈어드레싱 방식을 택함 (매번 linked list를 위해 메모리를 새로 할당해야하기때문)
     

2. 비선형 자료구조