706. Design HashMap
-
706. Design HashMapProgramming/leetcode 2021. 2. 22. 10:08
해시맵 디자인 하는 문제 (파이썬은 Dict가 해시맵으로 볼 수 있다.) 해시맵 이론들... 해시맵에서 충돌했을때 해결 방법은 개별체이닝과 오픈어드레싱 방법이 있다. 개별 체이닝 - LinkedList로 데이터를 이어나가는 방법(O(n)도 걸릴수 있다.) 오픈어드레싱 - 충돌이 났을때, 그 주변을 선형으로 탐색해 적절한 위치에다 넣는것, (모든 원소가 반드시 자신의 해쉬값과 일치한다는 보장이 없음) 파이썬은 오픈어드레싱을 사용하고 있다. 해시맵 로드팩터 - 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈것 파이썬의 로드팩터는 0.66이고, 자바는 0.75이다. 이 비율을 넘어가면 각 언어에서 해시 테이블 공간을 재할당 한한다. import sys from itertools import co..