HashTable

해시 테이블

정의?

키 값을 해싱하여 특정위치에 있는 데이터로 직접 액세스 하기위해 고안된 방식

해싱 : 임의의 길이를 가진 데이터를 고정된 길이를 가지는 데이터로 매핑

Big-O

접근 탐색 삽입 삭제
X O(1) O(1) O(1)

조건?

입력에 대한 해시 함수의 결과가 항상 동일한 값이어야 함 (시간/공간적 제약을 받지않아야함 어디서하든 언제하든 동일한 키값에 동일한 메모리 접근)

효율?

해시함수의 처리속도가 빠를수록 효율이 좋다
해시함수의 결과가 밀집도가 낮아야 함
해시테이블의 크기가 클수록 빠르지만 메모리가 부담이 된다.

충돌!

해시함수가 서로다른 입력 값에 대해 동일한 해시테이블 주소를 반환하는경우가있음.
모든 입력값에 대해 고유한 해시값을 만드는건 불가능 하며 충돌은 불가피
체이닝과 개방 주소법이 있음

• 체이닝 : 해시 충돌이 발생하면 연결 리스트로 데이터를 연결하는 방식
  장점 : 해시테이블에 자료가 많아지더라도 성능 저하가 적음
  단점 : 해시테이블 외 추가적인 저장공간이 필요함
• 개방주소법 : 해시 충돌이 발생하면 다른 빈 공간에 데이터를 삽입하는 방식(선형탐색/제곱탐색/이중해시 등등을 통해 다른 빈 공간 확보)
  장점 : 추가적인 저장 공간이 필요하지 않음, 삽입 삭제시 오버 헤드가 적음
  단점 : 해시 테이블에 자료가 많아질수록 성능저하가 많음
  해시테이블의 공간 사용률이 높을 경우 성능저하가 발생하므로 재해싱 과정을 거침(70~80%?)
  재해싱 : 해시테이블의 크기를 늘리고 테이블 내의 모든 데이터를 다시 해싱하는과정