Algorithm&Data Structure
2022. 12. 10.
[Data Structure] Hash Table
Hash Table에 대한 공부 기록이다. Hash Table 입력값에 대해 hash 함수를 거치고, 결과값 즉, key값에 의해 위치가 결정된다. 정렬이 아닌 결정된 위치에 데이터를 보관하기 때문에 빠른 삽입, 검색, 삭제 작업을 제공한다. 예시 해시함수 h(x)=x%13이라고 하면, 입력값에 대해 위의 연산을 진행하고 그 결과값을 key값으로 해당 Table에 저장하는 것. 적재율 입력값에 대해서 해시 함수의 연산 결과가 같으면 어떨까? Hash Table에 이미 값이 있을 때 충돌이발생한다. Hash Table에 원소가 차 있는 비율을 적재율이라고 한다. 적재율은 Hash Table의 크기가 m이고, 저장된 키의 총 수가 n일 때 n/m으로 정의된다. 적재율이 높아지면 충돌 확률이 높아지고, 해시 ..
![[Data Structure] Hash Table](http://i1.daumcdn.net/thumb/C230x230/?fname=https://blog.kakaocdn.net/dn/cSvdyy/btrTlsoqhkg/RN811KgjkmGwYruijF0o70/img.png)