기본

1. 정의: key 연산 적용 --> Key값 위치 찾아내는 것
2. 용어
   1. hash table: 원소 저장되는 공간, 연속적인 공간(배열의 형태)
      1. 버킷: 테이블 자체를 버킷이라고 하기도 함
      2. 슬롯: 하나의 버킷에 여러개 슬롯 존재 가능
      3. 해시: key 값 mapping 후 값을 hash라고 함
   2. collision: 서로 다른 key값이 동일 bucket 주소로 mapping
   3. overflow: bucket에 슬롯보다 더 많은 원소가 저장되려고 할 때
      1. 모든 콜리전이 오버플로우는 아님 --> 슬롯이 여러개 일 수도 있음
3. issue
   1. hash function
   2. overflow handlong method

hash function

1. 요건
   1. easy to compute
   2. 컬리전 최소화
2. 종류
   1. mid square
      1. key값 제곱 후 중간 일정 bit 선택 --> 기본적으로 key값 이진 비트로 생각
   2. Folding
      1. key 값의 2진수 string 몇개 Part로 나눔 --> 겹쳐서 덧셈
   3. Division
      1. %(나머지 연산), f(k) = k%m --> m은 table size
      2. m값으로는 2의 제곱수는 좋지 않음 --> 규칙이 있는 경우 분산이 되지 않을 수 있음
   4. digit analysis
      1. key값 임의의 진수로 전환
         1. ex) 21100248 --> 앞 3개, 뒤 3개만 선택
      2. key값의 형태를 사전에 알 수 있는 경우 사용

hash overflow handling

1. 종류
   1. linear probing
      1. overflow 발생 시 --> closest unfilled bucket에 넣음
      2. 단점
         1. 삭제된 공간 --> search 오류
            1. 초기 empty 와 deleted 공간 구분
         2. clustering 문제
            1. clustering --> 빈 공간을 찾는데 오래 걸림
   2. quadratic probing(제곱)
      1. overflow --> (f(k))%m, (f(k)+i^2)%m, (f(k)-i^2)%m ...(i=1, 2, 3 ...)
      2. 단점
         1. 줄긴 하였지만 여전히 clustering 문제 존재
   3. rehashing
      1. overflow --> 매번 다름 함수 적용, f1(K), f2(k), f3(k) ...
      2. 단점
         1. table을 효율적으로 사용할 적절한 함수 필요
   4. chaining
      1. 각 bucket --> Linked list로 구성
         1. 최근 것이 앞으로 오도록 구성 --> 일반적으로 최근 것을 먼저 찾음!
      2. 장점
         1. 서로 다른 hash 끼리 영향 없음

추가

1. loading density
   1. a=n/(s*b) --> Sb는 전체 용량
      1. n: 저장된 원소 수
      2. s: bucket 당 slot 수
      3. b: bucket 수
   2. loading density 클수록 --> 공간 활용도 높아지나, collision 발생 빈도 증가
2. hash table size
   1. too large --> 활용도 낮음
   2. too small --> 성능 저하(collision 증가)
3. hash 단점
   1. sorted order로 traverse 기능 어려움
      1. ex) key 값 순서로 조회
      2. hash의 순서가 key값의 순서와 관계가 없을 수 있음