Hash2 [MIT 6.006 정리] Lec 10. 해싱 (개방 주소법, 균일 해싱) * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 개방 주소법 (Open Addressing) 해싱 구현 과정에서 충돌(collision) 을 해결하는 방법 중 하나로, 해시 테이블을 구현하는 가장 쉬운 방법 포인터를 사용하지 않기 때문에 구현하기 쉽고 적은 메모리를 차지함 BUT... 효율적으로 구현하기 위해선 체이닝(chaining) 을 이용할 때보다 더욱 정교하게 짜야함! 여러 항목을 갖고 있는 배열(array) 로서 해시 테이블을 구현하되, 배열의 각 슬롯 당 하나의 아이템만 존재.. 2021. 3. 10. [MIT 6.006 정리] Lec 09. 해싱 (테이블 더블링, 분할 상환, 롤링 해시, Karp-Rabin) * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 해싱 with 체이닝 Recap 모든 키에 대한 거대한 집합이 존재할 때 (maybe infinite size...), 실제로 데이터 구조에 저장되는 것은 유한한(finite) n 개의 키일 뿐! 해시 함수 h 를 이용해 n 개의 키를 m 크기의 해시 테이블에 저장 (맵핑!) 서로 다른 키들이 해시 테이블의 동일한 슬롯으로 맵핑될 경우 (충돌), 연결 리스트로 저장함 해당 구조의 총 크기는 n (연결 리스트로 된 총 항목 수) + m (해.. 2021. 3. 6. 이전 1 다음