해싱 2013. 11.15 이 현 직 hyunjik@mokwon.ac.kr.

Slides:



Advertisements
Similar presentations
제철고 프로그래밍언어 2015 가을학기 강의 #2 Python 변수, 입출력, 배열 박성우 POSTECH 컴퓨터공학과 2015 년 9 월 30 일.
Advertisements

Ch.08-4 Hashing ( 해싱 ) [CPA340] Algorithms and Practice Youn-Hee Han
6 장. printf 와 scanf 함수에 대한 고찰 printf 함수 이야기 printf 는 문자열을 출력하는 함수이다. – 예제 printf1.c 참조 printf 는 특수 문자 출력이 가능하다. 특수 문자의 미 \a 경고음 소리 발생 \b 백스페이스 (backspace)
Hashing 함수의 종류 및 특징 컴퓨터 과학과 심형광. I N D E X 1. Hashing 함수 2. Hashing 함수의 종류 3. 참조 자료.
2.6 탐색(Search) 1. 순차검색 (Sequential Search, Linear Search)
UNIX 운영 체제의 설계 - Chapter 4. 파일의 내부 표현
재료수치해석 HW # 박재혁.
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 동적 해싱
07 그룹 함수 그룹 함수의 개념 그룹 함수의 종류 데이터 그룹 생성 HAVING 절.
5장. 참조 타입.
07. 디바이스 드라이버의 초기화와 종료 김진홍
해싱(hashing) Ref. C로 쉽게 풀어쓴 자료구조, 생능출판사, 2005.
Heesang kim PL/SQL 3 Heesang kim.
컴퓨터 프로그래밍 기초 #02 : printf(), scanf()
13 인덱스 인덱스의 개념 인덱스의 구조 인덱스의 효율적인 사용 방법 인덱스의 종류 및 생성 방법 인덱스 실행 경로 확인
CHAP 11: 해싱 순천향대학교 하상호.
프로그래밍 랩 – 7주 리스트.
11장. 1차원 배열.
13 인덱스 인덱스의 개념 인덱스의 구조 인덱스의 효율적인 사용 방법 인덱스의 종류 및 생성 방법 인덱스 실행 경로 확인
쉽게 배우는 알고리즘 6장. 해시 테이블Hash Table
다음 주 과제 기말고사 시험범위 : 7장 ~12장 필기시험 : 2016년 12월 12일(6교시) 필기장소 : E???
CHAP 11: 해싱 순천향대학교 하상호.
JA A V W. 03.
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
CHAP 11 : 해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
CHAP 11 : 해싱.
충돌 해결의 종류 및 특징 최현경.
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
제 6 장 해시테이블.
CHAP 11 : 해싱.
CHAP 11 : 해싱.
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
1. 2진 시스템.
5강. 배열 배열이란? 배열의 문법 변수와 같이 이해하는 배열의 메모리 구조의 이해 레퍼런스의 이해 다차원 배열
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
리스트(List)를 이용한 자료 관리 이점숙 /
Choi Seong Yun 컴퓨터 프로그래밍 기초 #03 : 변수와 자료형 Choi Seong Yun
CHAP 21. 전화, SMS, 주소록.
객체기반 SW설계 팀활동지 4.
Canary value 스택 가드(Stack Guard).
2nd day Indexing and Slicing
알고리즘 알고리즘이란 무엇인가?.
데이터 동적 할당 Collection class.
1과목 데이터베이스 강사 이 민 욱.
자료구조론 12장 검색(search).
Excel 일차 강사 : 박영민.
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
클래스 : 기능 CHAPTER 7 Section 1 생성자(Constructor)
다음 주 과제 기말고사 시험범위 : 6장 ~12장 필기시험 : 2015년 12월 18일(5교시) 필기장소 : E327
Chapter 10 데이터 검색1.
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
컴퓨터 프로그래밍 기초 - 9th : 배열 / 포인터 -
제 4 장 Record.
어서와 C언어는 처음이지 제21장.
 6장. SQL 쿼리.
개정판 누구나 즐기는 C언어 콘서트 제13장 동적 메모리 출처: pixabay.
CHAP 11:해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
C++ Espresso 제15장 STL 알고리즘.
6 객체.
Presentation transcript:

해싱 2013. 11.15 이 현 직 hyunjik@mokwon.ac.kr

해싱이란? 대부분의 탐색 방법들은 키 값 비교로써 탐색하고자 하는 항목에 접근 해싱(hashing) 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근 해시 테이블(hash table) 키 값의 연산에 의해 직접 접근이 가능한 구조 해싱은 물건을 정리하는 것과 같다

추상자료형 사전구조 사전구조(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)의 인덱스

해시 테이블의 구조 해시테이블 ht 충돌(collision) 오버플로우(overflow) M개의 버켓(bucket)으로 구성된 테이블 ht[0], ht[1], ...,ht[M-1]의 원소를 가짐 하나의 버켓에 s개의 슬롯(slot) 가능 충돌(collision) 서로 다른 두 개의 탐색키 k1과 k2에 대하여 h(k1) = h(k2)인 경우 오버플로우(overflow) 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하는 것 오버플로우 해결 방법 반드시 필요

이상적인 해싱 학생 정보를 해싱으로 저장, 탐색해보자 5자리 학번 중에 앞 2자리가 학과 번호, 뒤 3자리가 각 학과의 학생 번호 같은 학과 학생들만 가정하면 뒤의 3자리만 사용해서 탐색 가능 학번이 00023이라면 이 학생의 인적사항은 해시테이블 ht[23]에 저장 만약 해시테이블이 1000개의 공간을 가지고 있다면 탐색 시간이 O(1)이 되므로 이상적임

실제의 해싱 실제로는 해시테이블의 크기가 제한되므로, 존재 가능한 모든 키에 대해 저장 공간을 할당할 수 없음 h(k)= k mod M 의 예에서 보듯이 필연적으로 충돌과 오버플로우 발생함

실제의 해싱(cont.) 알파벳 문자열 키의 해시함수가 키의 첫 번째 문자의 순서라고 하자 h("array")=1 h("binary")=2 입력데이터: array, binary, bubble, file, digit, direct, zero, bucket

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

해시함수(cont.) 제산 함수 폴딩 함수 h(k)=k mod M 해시 테이블의 크기 M은 소수(prime number) 선택 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)

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

충돌해결책 충돌(collision) 충돌해결책 서로 다른 탐색 키를 갖는 항목들이 같은 해시 주소를 가지는 현상 충돌이 발생하면 해시 테이블에 항목 저장 불가능 충돌을 효과적으로 해결하는 방법 반드시 필요 충돌해결책 선형조사법: 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장 체이닝: 각 버켓에 삽입과 삭제가 용이한 연결 리스트 할당

선형조사법(linear probing) 충돌이 ht[k]에서 발생했다면, ht[k+1]이 비어 있는지 조사 만약 비어있지 않다면 ht[k+2] 조사 비어있는 공간이 나올 때까지 계속 조사 테이블의 끝에 도달하게 되면 다시 테이블의 처음부터 조사 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 찬것임 조사되는 위치: h(k), h(k)+1, h(k)+2,… 군집화(clustering)과 결합(Coalescing) 문제 발생

선형조사법(linear probing) (예) 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(충돌 발생) (h(13)+1) mod 7 = 0(저장)

이차 조사법(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 ) 적용

이중해싱법(double hashing) 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(저장)   1단계 2단계 3단계 4단계 5단계 [0] [1] 8 [2] 9 [3] 13 [4] [5] 1 [6] 6

체이닝(chaining) 오버플로우 문제를 연결 리스트로 해결 (예) 크기가 7인 해시테이블에서 각 버켓에 고정된 슬롯이 할당되어 있지 않음 각 버켓에, 삽입과 삭제가 용이한 연결 리스트 할당 버켓 내에서는 연결 리스트 순차 탐색 (예) 크기가 7인 해시테이블에서 h(k)=k mod 7의 해시 함수 사용 입력 (8, 1, 9, 6, 13) 적용

체이닝(chaining) 1단계 (8) : h(8) = 8 mod 7 = 1(저장)

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

해싱의 성능분석(cont.) 선형조사법에서의 비교 연산 횟수 0.1 1.1 0.3 1.5 1.2 0.5 2.5 0.7 6.1 2.2 0.9 50.5 5.5

해싱의 성능분석(cont.) 체인닝에서의 비교 연산 횟수

V.Lum, P.Yuen, M.Dodd, CACM, 1971, Vol.14, No.4 참조 해싱의 성능분석(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 참조

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

Question1 아래와 같이 10개의 버켓과 버켓당 2개의 슬롯을 가지는 해시테이블이 있다. 해시 함수는 정수 데이터의 끝자리 숫자를 사용한다. 데이터 (53, 374, 225, 557, 19, 100, 763, 812, 65, 710, 123, 818)가 순서대로 삽입 될 경우에 해시 테이블에 데이터가 저장되는 과정을 보이고, 충돌 횟수와 오버플로우 횟수를 답하라. 버켓 번호 슬롯0 슬롯1 1 2 3 4 5 6 7 8 9

Question2 키 값이 1234567이고 해시 주소가 10진수 4자리로 구성될 때, 이동 폴딩과 경계 폴딩으로 계산되는 해시 주소를 구하시오.

Question3 아래와 같이 10개의 버켓과 버켓당 1개의 슬롯을 가지는 해시테이블이 있다. 해시 함수는 정수 데이터의 끝자리 숫자를 사용하고, 선형 조사법으로 오버플러우 처리한다. 데이터 (74, 30, 12, 28, 24, 33, 52, 60, 10, 20)가 순서대로 삽입 될 경우에 해시 테이블에 데이터가 저장되는 과정을 보이시오. 버켓 번호 슬롯 1 2 3 4 5 6 7 8 9

Question4 아래와 같이 10개의 버켓과 버켓당 1개의 슬롯을 가지는 해시테이블이 있다. 해시 함수는 정수 데이터의 끝자리 숫자를 사용하고, 체이닝으로 오버플러우 처리한다. 데이터 (74, 30, 12, 28, 24, 33, 52, 60, 10, 20)가 순서대로 삽입 될 경우에 해시 테이블에 데이터가 저장되는 과정을 보이시오. 버켓 번호 슬롯 NULL 1 2 3 4 5 6 7 8 9