MMM

김희성의 개발자 면접 cs 강의/ 스터디 Hash Collision (해시 충돌) 서로 다른 Key 값에 대해서 Hash 함수의 반환 값이 동일한 경우를 말한다. key의 값의 경우의 수는 무한하지만 메모리상 버킷사이즈는 줄일 수 밖에 없다. (Java에서 HashMap()의 initial Capacity는 16으로 정의되어있음) 그 때 버킷사이즈를 늘리기위해 리사이징하는 과정에서 해시 충돌 발생 연산 속도도 빠르며, 해시 충돌이 가능 한 발생하지 않아야 성능이 좋은 Hash 함수라 할 수 있다. Hash Collision (해시 충돌) 해결 방법 Open Addressing 해시 충돌이 발생한 경우 비어있는 버킷을 찾아서 저장한다. 해시 충돌이 발생한 경우, 탐색/접근의 시간 복잡도가 O(N) 으로 증..

김희성의 개발자 면접 cs 강의/ 스터디 HashTable (HashMap , unordered_map(set)) java는 HashMap map: [key,value] 저장 / set : key만 저장 Map과 Set은 key가 중복되는 데이터는 저장 불가 비선형 자료구조 일정 크기의 배열(버킷) 생성 후 key값을 hash함수를 통해 배열의 index로 변환하여, 해당 index에 해당 key값과 value값 저장 시간 복잡도 i번째 데이터에 접근(Access) : NONE / *O(N) (순서라는게 없음) X라는 데이터(Key)가 있는지 탐색 : O(1) X라는 데이터(Key)에 접근(Access) : O(1) X라는 데이터(Key)의 삽입/삭제 : O(1) Dictionary는 HashMap 으로..