해시함수의 모든 것

소개글

해시에 대해 조사하고 분석하였습니다.
각종 경우에 대해 정리와 수학적인 증명이 되어 있습니다.

해시 함수에 대해 조사를 해야되거나, 차근차근 공부하고 싶은 분들께 도움이 될 것입니다.

목차

< 체이닝을 사용하는 해싱의 분석 >

1. 적재율(Load Factor)에 대하여
2. 체이닝을 사용하는 해싱의 평균적인 경우에 대한 고찰
3. 검색이 성공하는 경우
4. 검색이 실패하는 경우
5. 결론

< 개방 번지화 방법 >

1. 개방 번지화 방법에 대한 개괄
2. 선형조사
3. 2차원조사
4. 중복해싱
5. 개방번지 해싱에 대한 분석

< 체이닝과 개방 번지화의 비교 >

< 해싱과 다른 탐색의 비교 >

본문내용

1. 적재율(Load Factor)에 대하여

적재율: 해시함수에 데이터가 얼마나 차 있느냐
적재율 α는 n/m 로 정의

{█(n = 테이블에 있는 원소의 개수@m = 테이블에 있는 슬롯의 개수 = (사용 가능한 빈) linked lists의 개수)┤

적재율의 의미: Linked List 당 평균적인 원소의 개수
적재율의 가능한 범위는 0 ≤ α < 1, α = 1, α > 1 이 있다.
해시 테이블의 성능에 매우 중요한 영향을 미침


2. 체이닝을 사용하는 해싱의 평균적인 경우에 대한 고찰

같은 주소로 해싱되는 원소를 모두 하나의 연결리스트(Linked List)로 관리
추가적인 연결리스트가 필요하다.
장점: 원소의 삭제가 용이하다.
단점: 포인터 저장을 위한 추가공간이 필요하고, 메모리 할당이 동적으로 이루어져야 한다.

먼저 균등 해싱에서 임의의 원소가 m개의 위치에 균등한 확률로 해시된다고 가정하자.
j = 0, 1, … , m – 1에 대해 리스트T [ j] 의 크기를 nj 로 놓는다.
따라서 n = n0 + n1 + … + nm−1
nj 의 평균값 E [nj ] = α = n/m
해시 함수가 O(1)에 계산된다고 하면, 키 k 를 갖는 원소 검색에 요구되는 시간은 nh(k). 즉, 길이 리스트 T [h(k)]에 달려있다.

두 가지 경우에 대해 생각해본다.
- 키 k를 가진 원소를 찾아서 『검색이 성공하는 경우』
- 키 k를 가진 원소가 테이블에 존재하지 않아 『검색이 실패하는 경우』

[체이닝에 의해 충돌을 해결하는 해시테이블에서, 단순 균등 해싱이라는 가정을 한다.]

3. 검색이 성공하는 경우

참고 자료

없음