- 해시
- == 해시는 키 밸류 형태로 데이터 저장하는 자료구조 입니다. 파일 등 데이터를 매개변수로 해시펑션을 통해 해쉬코드 만들고 인덱스로 반환하고 해쉬버킷에 데이터를 저장하는 자료구조 입니다. 해쉬코드로 다이렉트 데이터 접근가능. 하지만 해쉬버킷에 값이 많으면 검색시간이 O(n)까지 걸릴수잇음, 키는 많은데 해쉬코드는 정수라서 중복될수있음. 해쉬코드는 다른데 인덱스가 같아서 같은 방에 배정, 콜리전(충돌) 최소화를 위한 좋은 해쉬 알고리즘 필수. 시간복잡도는 보통 삽입, 삭제, 조회가 모두 0(1)을 가집니다.
- 해시충돌회피방법 == 해쉬 버킷에 같은 값 이미 있을때 처리법
- open addressing - 다른 해시값에 저장
- chaining - 해쉬 테이블이 원소 하나를 담는게 아니라 링크드 리스트를 담음.
- 해시버킷에 키(해쉬펑션에들어가는값)를 해쉬펑선기준(가ㅁ령, %3의 나머지)으로 해쉬(해쉬펑션의 결과)와 값(밸류) 을 저장해둔상태
- 검색 = O(1), 삽입=O(1), 삭제 =O(1)
