CHAP 11:해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.

Slides:



Advertisements
Similar presentations
1 08 배열. 한국대학교 객체지향연구소 2 C 로 배우는 프로그래밍 기초 2 nd Edition 배열  동일한 자료유형의 여러 변수를 일괄 선언  연속적인 항목들이 동일한 크기로 메모리에 저장되는 구조  동일한 자료 유형이 여러 개 필요한 경우에 이용할 수 있는.
Advertisements

Hashing 함수의 종류 및 특징 컴퓨터 과학과 심형광. I N D E X 1. Hashing 함수 2. Hashing 함수의 종류 3. 참조 자료.
2.6 탐색(Search) 1. 순차검색 (Sequential Search, Linear Search)
UNIX 운영 체제의 설계 - Chapter 4. 파일의 내부 표현
2장. 프로그램의 기본 구성. 2장. 프로그램의 기본 구성 2-1"Hello, World!" 들여다 보기 /* Hello.c */ #include int main(void) { printf("Hello, World! \n"); return 0;
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
Excel 일차 강사 : 박영민.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
컴퓨터 프로그래밍 기초 [Final] 기말고사
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express Slide 1 (of 13)
8장 직접 화일.
9.1 해싱의 정의 및 필요성 9.2 정적 해싱(Static Hashing) 9.3 동적 해싱
해싱(hashing) Ref. C로 쉽게 풀어쓴 자료구조, 생능출판사, 2005.
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
SqlParameter 클래스 선문 비트 18기 발표자 : 박성한.
컴퓨터 프로그래밍 기초 #02 : printf(), scanf()
13 인덱스 인덱스의 개념 인덱스의 구조 인덱스의 효율적인 사용 방법 인덱스의 종류 및 생성 방법 인덱스 실행 경로 확인
CHAP 11: 해싱 순천향대학교 하상호.
2주차: 변수, 수식, Control Flow.
프로그래밍 랩 – 7주 리스트.
11장. 1차원 배열.
13 인덱스 인덱스의 개념 인덱스의 구조 인덱스의 효율적인 사용 방법 인덱스의 종류 및 생성 방법 인덱스 실행 경로 확인
쉽게 배우는 알고리즘 6장. 해시 테이블Hash Table
다음 주 과제 기말고사 시험범위 : 7장 ~12장 필기시험 : 2016년 12월 12일(6교시) 필기장소 : E???
CHAP 11: 해싱 순천향대학교 하상호.
JA A V W. 03.
어서와 C언어는 처음이지 제14장.
인터넷응용프로그래밍 JavaScript(Intro).
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
3장 상수 변수 기본 자료형 키워드와 식별자 상수와 변수 기본 자료형 형변환 자료형의 재정의.
CHAP 11 : 해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
27강 JAVA Collections - II - Map계열 컬렉션 클래스 살펴보기 - Set계열 컬렉션 클래스 살펴보기
USN(Ubiquitous Sensor Network)
CHAP 11 : 해싱.
충돌 해결의 종류 및 특징 최현경.
제 6 장 해시테이블.
CHAP 11 : 해싱.
CHAP 11 : 해싱.
해싱 이 현 직
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
문자열 컴퓨터시뮬레이션학과 2015년 봄학기 담당교수 : 이형원 E304호,
리스트(List)를 이용한 자료 관리 이점숙 /
CHAP 21. 전화, SMS, 주소록.
객체기반 SW설계 팀활동지 4.
Canary value 스택 가드(Stack Guard).
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
알고리즘 알고리즘이란 무엇인가?.
데이터 동적 할당 Collection class.
1과목 데이터베이스 강사 이 민 욱.
자료구조론 12장 검색(search).
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
다음 주 과제 기말고사 시험범위 : 6장 ~12장 필기시험 : 2015년 12월 18일(5교시) 필기장소 : E327
7주차: Functions and Arrays
Chapter 10 데이터 검색1.
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
발표자 : 이지연 Programming Systems Lab.
실습과제 (변수와 자료형, ) 1. 다음 작업 (가), (나), (다)를 수행하는 프로그램 작성
제 4 장 Record.
07. DB 설계 명지대학교 ICT 융합대학 김정호.
어서와 C언어는 처음이지 제21장.
 6장. SQL 쿼리.
개정판 누구나 즐기는 C언어 콘서트 제13장 동적 메모리 출처: pixabay.
C++ Espresso 제15장 STL 알고리즘.
6 객체.
Presentation transcript:

CHAP 11:해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2005

해싱이란? 지금까지 배운 모든 탐색 방법들은 키값을 비교함으로써 탐색하고자 하는 항목에 접근 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 부르며, 해시테이블을 이용한 탐색을 해싱(hashing) 해싱의 예: 심볼 테이블

사전구조 추상자료형 사전구조(dictionary): 맵(map)이나 테이블(table)로 불리우기도 한다. 사전 구조는 다음과 같이 탐색키와 탐색키와 관련된 값의 2가지 종류의 필드를 가진다. 영어 단어나 사람의 이름같은 탐색키(search key) 단어의 정의나 주소 또는 전화 번호같은 탐색키와 관련된 값(value) ∙객체: 일련의 (key,value) 쌍의 집합 ∙연산: ▪ add(key, value) ::= (key,value)를 사전에 추가한다. ▪ delete(key) ::= key에 해당되는 (key,value)를 찾아서 삭제한다. 관련된 value를 반환한다. 만약 탐색이 실패하면 NULL를 반환한다. ▪ search(key) ::= key에 해당되는 value를 찾아서 반환한다.만약 탐색이 실패하면 NULL를 반환한다.

해싱의 구조 해시 함수(hash function)란 탐색키를 입력으로 받아 해시 주소(hash address)를 생성하고 이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스가 된다. 예를 들어 영어사전에서는 단어가 탐색키가 되고 이 단어를 해싱 함수를 이용하여 적절한 정수 i로 변환한 다음, 배열 요소 ht[i]에 단어의 정의를 저장하는 것이다. 

해시 테이블의 구조 해시테이블 ht는 M개의 버켓(bucket)으로 이루어지는 테이블로서 ht[0], ht[1], ...,ht[M-1]의 원소를 가진다. 하나의 버켓은 s개의 슬롯(slot)을 가질 수 있다. 충돌(collision) : 서로 다른 두 개의 탐색키 k1과 k2에 대하여 h(k1) = h(k2)인 경우 이러한 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하게 되면 버켓에 더 이상 항목을 저장할 수 없게 되는 오버플로우(overflow)가 발생 오버플로우를 해결하기 위한 방법이 반드시 필요

이상적인 해싱 (예) 학생들에 대한 정보를 해싱으로 저장, 탐색 학번을 탐색키로 생각하자. 학번은 5자리로 되어 있고 앞의 2개의 숫자가 학과를 나타내고 뒤의 3자리 숫자가 각 학과의 학생들의 번호 같은 학과 학생들만 저장된다고 가정하면 뒤의 3자리만 사용할 수 있다. 이 경우에는 어떤 학생의 학번이 01023이라면 이 학생의 인적사항은 해시테이블의 이름을 ht이라고 하면 ht[23]에 저장 add(key, value) index ← hash_function(key) ht[index] = value search(key) index ←hash_function(key) return ht[index]

실제의 해싱 실제로는 해시 테이블의 크기가 제한되어 있으므로 하나의 탐색키당 해시테이블에서 하나의 공간을 할당할 수가 없다 해싱함수가 필요 h(k)= k mod M 충돌과 오버플로우 발생

실제의 해싱(cont.) 두 번째 예제: 탐색키는 알파벳으로 되어 있다고 가정 해시함수는 각 키의 첫 번째 문자를 숫자로 바꾼다. h("array")=1 h("binary")=2 … (입력데이터) (array, binary, bubble, file, digit, direct, zero, bucket)

해시함수 좋은 해시 함수의 조건 충돌이 적어야 한다. 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 한다. 계산이 빨라야 한다.

해시함수 제산 함수 폴딩함수 h(k)=k mod M 해시 테이블의 크기 M는 소수(prime number) hash_index=(short)(key ^ (key>>16)) 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)

해시함수(cont.) 중간제곱함수 비트추출함수 숫자 분석 방법 중간 제곱 함수는 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다. 비트추출함수 탐색키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용하는 것이다. 숫자 분석 방법 키의 각각의 위치에 있는 숫자 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용

충돌해결책 충돌해결책 선형조사법: 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다. 체이닝: 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조를 변경한다.

선형조사법 충돌이 ht[k]에서 충돌이 발생했다면 ht[k+1]이 비어 있는지를 조사 이런 식으로 비어있는 공간이 나올 때까지 계속하는 조사하는 방법이다. 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 간다. 만약 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득찬 것이 된다. 조사되는 위치 h(k), h(k)+1, h(k)+2,… (예) h(k)=k mod 7   1단계 2단계 3단계 4단계 5단계 [0] 13 [1] 8 [2] 1 [3] 9 [4] [5] [6] 6 1단계 (8) : ∙h(8) = 8 mod 7 = 1(저장) 2단계 (1) : ∙h(1) = 1 mod 7 = 1(충돌발생)            ∙(h(1)+1) mod 7 = 2(저장) 3단계 (9) : ∙h(9) = 9 mod 7 = 2(충돌발생)            ∙(h(9)+1) mod 7 = 3(저장) 4단계 (6) : ∙h(6) = 6 mod 7 = 6(저장) 5단계 (13) :∙h(13) = 13 mod 7 = 6(충돌 발생)

이차조사법 이차 조사법(quadratic probing)은 선형 조사법과 유사하지만, 다음 조사할 위치를 다음 식에 의하여 결정한다. (h(k)+i*i) mod M 따라서 조사되는 위치는 다음과 같이 된다. h(k), h(k)+1, h(k)+4,… 선형 조사법에서의 문제점인 집중과 결합을 크게 완화

이중해싱법 이중 해싱법(double hashing) 또는 재해싱(rehashing)은 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법이다. step=C-(k mod C) h(k), h(k)+step, h(k)+2*step, … (예) 크기가 7인 해시테이블에서 첫 번째 해시 함수가 k mod M이고 오버플로우 발생시의 해시 함수step=5-(5 mod 5) 입력 파일 (8, 1, 9, 6, 13 )   1단계 2단계 3단계 4단계 5단계 [0] [1] 8 [2] 9 [3] 13 [4] [5] 1 [6] 6 1단계 (8) : ∙h(8) = 8 mod 7 = 1(저장) 2단계 (1) : ∙h(1) = 1 mod 7 = 1(충돌발생) ∙(h(1)+h‘(1)) mod 7 = (1+5-(1 mod 5)) mod 7 = 5(저장) 3단계 (9) : ∙h(9) = 9 mod 7 = 2(저장) 4단계 (6) : ∙h(6) = 6 mod 7 = 6(저장) 5단계 (13) :∙h(13) = 13 mod 7 = 6(충돌 발생) ∙(h(13)+h‘(13)) mod 7 = (6+5-(13 mod 5)) mod 7= 1(충돌발생) ∙(h(13)+2*h‘(13)) mod 7 = (6+2*2) mod 7= 3(저장)

체이닝 체이닝(chaining)은 오버플로우 문제를 연결 리스트로 해결한다. 각 버켓에 고정된 슬롯을 할당하는 것이 아니라 각 버켓에, 삽입과 삭제가 용이한 연결 리스트를 할당한다. 버켓 내에서는 원하는 항목을 찾을 때는 연결 리스트를 순차 탐색한다. (예) 크기가 7인 해시테이블에 h(k)=k mod 7의 해시 함수를 이용하여 8, 1, 9, 6, 13 을 삽입할 때에의 체이닝에 의한 충돌 처리 1단계 (8) : ∙h(8) = 8 mod 7 = 1(저장) 2단계 (1) : ∙h(1) = 1 mod 7 = 1(충돌발생->새로운 노드 생성 저장) 3단계 (9) : ∙h(9) = 9 mod 7 = 2(저장) 4단계 (6) : ∙h(6) = 6 mod 7 = 6(저장) 5단계 (13) :∙h(13) = 13 mod 7 = 6(충돌 발생->새로운 노드 생성 저장)

해싱의 성능분석 적재 밀도(loading density) 또는 적재 비율(loading factor) 은 저장되는 항목의 개수 n과 해시 테이블의 크기 M의 비율이다. 선형 조사법 체이닝

그림 11.20 각 알고리즘에 따른 평균 버켓 접근수그림 11.20 각 알고리즘에 따른 평균 버켓 접근수 해싱의 성능분석(cont.)          .50 .70 .90 .95 해싱 함수 체인 선형조사 중간 제곱 1.26  1.73 1.40  9.75 1.45 37.14 1.47  37.53 제산 1.19  4.52 1.31  7.20 1.38 22.42 1.41  25.79 이동 폴딩 1.33 21.75 1.48 65.10 77.01 1.51 118.57 경제 폴딩 1.39 22.97 1.57 48.70 1.55 69.63  97.56 숫자 분석 1.35  4.55 1.49 30.62 1.52 89.20 125.59 이론적 1.25  1.50 1.37  2.50  5.50  10.50 (V.Lum, P.Yuen, M.Dodd, CACM, 1971, Vol.14, No.4 참조)(V.Lum, P.Yuen, M.Dodd, CACM, 1971, Vol.14, No.4 참조) 그림 11.20 각 알고리즘에 따른 평균 버켓 접근수그림 11.20 각 알고리즘에 따른 평균 버켓 접근수

해싱과 다른 탐색 방법의 비교