CHAP 11: 해싱 2015. 11. 30 순천향대학교 하상호.

Slides:



Advertisements
Similar presentations
Datamining Lab 이아람.  How to count the matches The cat ate the bird.  Token : 5/Type : 4.
Advertisements

1. 자료구조 개념 (1) 자료구조의 개요 1) 자료구조 ① 일련의 자료들을 조직하고 구조화하는 것 ② 자료의 표현과 그것과 관련된 연산 2) 자료구조에 따라 저장공간의 효율성과 프로그램의 실행시간이 달라짐 3) 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이.
8. 파일 인덱스: 탐색트리 (Search Tree)
8장 직접 파일.
데이터 구조 - 소개 순천향대학교 컴퓨터공학과 하 상 호.
시스템 생명 주기(System Life Cycle)(1/2)
쉽게 배우는 알고리즘 6장. 해시 테이블Hash Table.
시스템 생명 주기(System Life Cycle)(1/2)
자료 구조: Chapter 3 배열(1) 순천향대학교 컴퓨터공학과 하 상 호.
강의 #7 트리(Tree).
쉽게 배우는 알고리즘 5장. 검색트리
제 4 장 L i s t.
자료구조: CHAP 7(3) 트리 순천향대학교 컴퓨터공학과 하 상 호.
자료구조: CHAP 7 이진 탐색 트리 순천향대학교 컴퓨터공학과 하 상 호.
<엘리제를 위하여>를 감상하며 론도 형식 이해하기
자료구조: CHAP 4 리스트 (2) 순천향대학교 컴퓨터공학과 하 상 호.
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express.
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express.
동적메모리와 연결리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
제 8 장 이진 탐색 트 리 8.1 이진 탐색 트리 정의 8.2 이진 탐색 트리의 탐색 8.3 이진 탐색 트리의 삽입
해싱(hashing) Ref. C로 쉽게 풀어쓴 자료구조, 생능출판사, 2005.
IS lab. 김건영 Awk, Posting list IS lab. 김건영
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
12 검색.
Tree & Heap SANGJI University Kwangman Ko
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 11: 해싱 순천향대학교 하상호.
C언어 응용 제10주 실습 해보기 제8장 트리.
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
컴퓨터의 기초 제 2강 - 변수와 자료형 , 연산자 2006년 3월 27일.
CHAP 11 : 해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
게임인공지능 제 6 장 스크립트 2008년 5월 6일.
CHAP 9: 정렬 (part 2) 순천향대학교 컴퓨터학부 하 상 호.
CHAP 11 : 해싱.
4장 - PHP의 표현식과 흐름 제어-.
자료구조: CHAP 4 리스트 (2) 순천향대학교 컴퓨터공학과 하 상 호.
해쉬함수 충돌해결법과 특징 강원대학교 컴퓨터과학과 이해원.
해시와 해시 함수.
7장. 해시 테이블Hash Table.
CHAP 11 : 해싱.
CHAP 11 : 해싱.
해싱 이 현 직
자료구조: CHAP 7(2) 트리 순천향대학교 컴퓨터공학과 하 상 호.
작성일 참고서적 – Programing Game AI by Example
6장 반복제어문 for 문 while 문 do while 문 기타 제어문.
4. 어휘 분석(Lexical analysis)
C89(C++03) 프로그래밍 (Part 2) 7 배열 8 변수 범위 9 포인터 10 유도 자료형.
nauten Compiler – Report Ver.3 Mini-C (주간)
CHAPTER 04 파일 설계(FiLE Design).
Chapter 11 해쉬(Hash) SANGJI University Kwangman KO
C언어 응용 제 15 주 검색.
CHAP 12:탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 12 : 탐색.
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
장애인단체 간담회 마스터 제목 스타일 편집 마스터 제목 스타일 편집 장애인 단체 간담회 마스터 부제목 스타일 편집
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
제 8 장 계산복잡도 개론 검색 문제 알고리즘 강의 슬라이드 8 검색 문제
최대 공약수 구하기 (1) 프로그램 예제2 : 최대 공약수 구하기 문제 해결 방법 구상 (아는 지식 정리) GCD1 알고리즘
문서의 작성 정보과학부 이지연.
탐색 선형 탐색, 이진 탐색, 이진 탐색 트리.
Chapter 07 트리.
5. 인류의 건강과 과학 기술 2. 건강관리 1) 면역.
데이터 베이스의 내부 구조.
Report #4 (1) (due 4/4) 문제 #1 3개의 막대 A, B, C와 원판 n개를 전달받아 Hanoi 탑 문제를 해결하는데 필요한 원판의 이동 회수를 구하여 반환하는 hanoi_tower(n, A, B, C)를 작성하라. 여기서 원판 n은 막대 A에 쌓여 있고.
Introduction to Computer System 컴퓨터의 이해 3: 데이터 표현
DataScience Lab. 박사과정 김희찬 (화)
C 프로그래밍은 매우 도전적인 작업이다. 도전의 이면에 철저한 준비와 체계적인 노력
CHAP 11:해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
보고서 #4 (1) (제출기한: 10/6) #1 다음 그래프 G에 대해서 답하시오. (2*5 = 10)
PHP 기초문법 PHP를 공부하는데 있어 가장 기초가 되는 PHP기초문법에 대해서 배워 봅니다.
Presentation transcript:

CHAP 11: 해싱 2015. 11. 30 순천향대학교 하상호

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

해싱 개념 해시 함수(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)인 경우 Key의 개수 >> 해시 테이블의 크기 이러한 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하게 되면 버켓에 더 이상 항목을 저장할 수 없게 되는 오버플로우(overflow)가 발생 오버플로우를 해결하기 위한 방법이 반드시 필요

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

실제의 해싱 실제로는 해시 테이블의 크기가 제한되어 있으므로 하나의 탐색키당 해시테이블에서 하나의 공간을 할당할 수가 없다 학생 수 n, 해시 테이블 크기 m일 때, n >> m인 경우 해싱함수가 필요 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)) key: 32비트, 해시테이블 인덱스: 16비트 이동 폴딩(shift folding)과 경계 폴딩(boundary folding) 탐색 키를 여러 부분으로 나누어 더한다 탐색 키의 이웃한 부분을 거꾸로 더한다

해시함수(cont.) 중간제곱함수 비트추출함수 숫자 분석 방법 중간 제곱 함수는 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다. 비트추출함수 탐색키를 이진수로 표현하고, 임의의 위치의 k개의 비트를 해시 주소로 사용하는 것이다. 해시 테이블의 크기 M = 2k 탐색키의 일부 정보만을 이용하여 해시 주소 집중 현상 가능 숫자 분석 방법 키의 각각의 위치에 있는 숫자 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용 숫자로 구성된 키에서 각각의 위치 수의 특성을 미리 알고 있을 때 유용 Ex) 200212345에서, 입학년도를 의미하는 앞 4자리 수는 사용하지 않는다.

해시함수(cont.) int hash_function(char a[]) { int hash_val = 0; int i = 0;   int hash_function(char a[]) { int hash_val = 0; int i = 0; while (a[i] != ‘\0’) do hash_val = g*hash_val + a[i++]; // 보통 g=31 end while return hash_val; }

충돌해결책 충돌이란? 충돌해결책 2가지 방법 서로 다른 탐색 키를 갖는 항목들이 같은 해시 주소로 사상되는 경우 선형조사법(linear probing): 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다. 체이닝(chaining): 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조를 변경한다.

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

알고리즘: 선형조사법 linearAdd(key: integer, ht: array of integers) { i, hval: integer hval <- h(key); i <- hval; while (ht[i] != null ) { // 충돌 발생되면 if (ht[i] = key) then print(“탐색키 중복”); return; i <- (i+1) mod sizeofHashTable; if (i = hval) then print(“테이블 꽉 참”); return; } ht[i] <- key; // 빈 버켓 발견 linearFind(key: integer, ht: array of integers) i, hval: integer; while (ht[i] != null) {

선형조사법: 평가 단순 키들이 집중/결합되어 저장되는 경향으로 탐색시간이 길어진다.

이차조사법 이차 조사법(quadratic probing)은 선형 조사법과 유사하지만, 다음 조사할 위치를 다음 식에 의하여 결정한다. (h(k)+i*i) mod M I = 0, 1, 2, …. M-1 M은 소수 따라서 조사되는 위치는 다음과 같이 된다. h(k), h(k)+1, h(k)+4,… 평가 선형 조사법에서의 문제점인 집중과 결합을 크게 완화 2차 집중문제 가능성 (동일한 위치로 사상될 경우, 같은 순서로 빈 버킷을 조사하기 때문)

이중해싱법 이중 해싱법(double hashing) 또는 재해싱(rehashing)은 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법이다. step=C-(k mod C), C는 M보다 약간 작은 소수, k는 키 값 h(k), h(k)+step, h(k)+2*step, … (예) 크기가 7인 해시테이블에서 첫 번째 해시 함수가 k mod M이고 오버플로우 발생시의 해시 함수 step=5-(k 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( 충돌 발생->새로운 노드 생성 저장)

알고리즘: 체이닝 (1) key: integer; link: nodeptr; nodeptr chainAdd(key: integer, ht: array of nodeptr) { nodeptr ptr, node, prev = null; int hval; // hash value hval = h(key); ptr = ht[hval]; while (ptr != null) { // 리스트의 끝을 찾는다 } node <- getNode(); // 한 개의 리스트 노드 생성 node.key <- key; node.link <- null; if (prev != null) prev.link <- node; else ht[hval] <- node;

알고리즘: 체이닝 (2) key: integer; link: nodeptr; nodeptr chainFind(key: integer, ht: array of nodeptr) { nodeptr ptr; int hval; // hash value hval = h(key); ptr = ht[hval]; while (ptr != null) { // 리스트로부터 key를 찾는다. } print(“Not found”);

해싱의 성능분석 적재 밀도(loading density) 또는 적재 비율(loading factor) 은 저장되는 항목의 개수 n과 해시 테이블의 크기 M의 비율이다. 탐색을 위한 비교 연산의 개수 선형 조사법 그림 11-18 참고 α>0.5이면 급격하게 탐색 시간 증가 체이닝 그림 11-19 참고 α가 증가하더라도 성능이 급격하게 떨어지지 않으나, 효율성을 위해서 낮게 유지하는 것이 필요

해싱의 성능분석(cont.) 평균 버켓 접근 수(Lum, Yuen, Dodd의 실험적 연구결과) 제산 해시 함수와 체이닝을 사용하는 것이 가장 효율적         적재밀도 해싱함수 .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

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