Week7_해시테이블(1)

해시테이블(hash table): 키-주소 매핑에 의해 구현된 사전 ADT 

 

해시테이블 = 버켓 배열 + 해시함수

 -항목들의 키를 주소(인덱스 i)로 매핑함으로서 1차원 배열에 사전 항목들을 저장

 

성능: 탐색, 삽입, 삭제- O(n) 최악시간, 그러나 O(1) 기대시간

 

버켓 배열: 해시테이블을 위한 버켓 배열은 크기 M의 배열 A로서,

A의 각 셀은 버켓(키-원소 쌍) = 슬롯

-정수 M: 배열의 용량

-키 k를 가진 원소 e는 버켓 A[k]에 삽입

-사전에 존재하지 않는 키에 속하는 버켓 셀들- NoSuchKey 라는 특별한 개체를 담는 것

-

 

버켓 배열 분석

-키가 유일한 정수며 [0, M-1] 범위에 잘 분포되어 있다면, 해시테이블에서의 탐색, 삽입, 삭제에 O(1)

최악의 시간 소요

-2가지 중요한 결함!!!!

->O(n) 공간을 사용하므로, M>>>n이면 공간 낭비

->키들이 [0, M-1]범위 내의 유일한 정수여야 하지만, 이는 종종 비현실적

 

*설계 목표: 해시테이블 데이터구조를 정의할 때는, 키를 [0, M-1] 범위 내의 정수로 매핑하는 좋은, adequate한 방식과 함께 버켓 배열을 구성함.

 

*해시함수 및 해시테이블 

 -해시함수(hash function) h: 주어진 형의 키를 고정 범위 [0, M-1]로 매핑

 -h(x) = x%M, h: 정수 키 x에 대한 해시함수, 주어진 키 형의 해시테이블

 -h(x): 키 x의 해시값(hash value)

 -주어진 키 형의 해시테이블 2가지로 구성

 1)해시함수 h

 2)크기 M의 배열(=테이블)

 

-사전을 해시테이블로 구현할 때, 목표는 항목 (k, e)를 첨자 i=h(k) 에 저장하는 것

 

<해시함수>

 -해시코드맵 h1: keys -> integers

 -압축맵 h2: integers -> [0,M-1]

 -해시코드맵을 적용, 그 결과에 압축맵을 적용 -즉, h(k)=h2(h1(k))

 -좋은 해시함수가 되려면?? : 키들은 외견상 무작위하게 분산, 빠르고 쉬운 계산(가능하면 O(1))

 

해시함수 예)

 임의의 키들->해시코드맵(-2,-1,0,1,2)->압축맵(0,1,----M-1)

 ex) 학번을 마지막 4자리 수로 분류한 다음, 방번호[0,1,2]를 분류한다. 

 

[해시코드맵]

-메모리 주소

-정수 캐스트

-요소합

-다항 누적

 

[압축맵]

*나누기

-h2(k)=|k|%M

-해시테이블의 크기 M은 일반적으로 소수로 선택

 

*승합제(MAD)

-h2(k)=|ak+b|%M

-a,b는 음이 아닌 정수로서 a%M not 0, 그렇지 않으면, 모든 정수가 동일한 값 b로 매핑됨