CHAP 11 : 해싱.

Slides:



Advertisements
Similar presentations
시스템 프로그래밍 박진희 컴퓨터 시스템 연구실. 2 Project 3 Key-value store 유일한 Key 에 하나의 Value 를 가지고 있는 방식 - Key 와 Value 를 쌍으로 관리 - Hash table, B-Tree, B+ Tree 등 분산형 데이터베이스에서.
Advertisements

주 40 시간 근무제 조기 시행계획 ( 급여 체계 변경안 포함 ) XXXXXXX.
연천 새둥지마을 체재형 주말농장 준공식 초청장 오시는 길 주제 일시 장소 21C 경기농촌희망심기 2005년 제1기 교육수료마을
10월 충북노회 남선교회 순회 헌신예배 묵 도 기 도 성 경 봉 독 특 송 찬 양 설 교 찬양 / 봉헌 봉 헌 기 도
라오디게아 교회의 교훈 본문 계 3: ○라오디게아 교회의 사자에게 편지하라 아멘이시요 충성되고 참된 증인이시요 하나님의 창조의 근본이신 이가 이르시되 15. 내가 네 행위를 아노니 네가 차지도 아니하고 뜨겁지도 아니하도다 네가 차든지 뜨겁든지 하기를 원하노라.
한알Ⅱ「더불어 살기」전국대회 일정표 날짜 시간 7월 26일(목) 7월 27일(금) 7월 28일(토) 7월 29일(일)
선거관리위원회 위원 공개모집 4차 공고 제4기 선거관리위원회를 구성하는 위원 모집의
열왕기하 1장을 읽고 묵상으로 예배를 준비합시다..
전도축제 계획서 *일시 : 2013년 4월 21, 28일 주일 (연속 2주)
이공계의 현실과 미래 제조업 立國 / 이공계 대학생의 미래 준비
신앙의 기초를 세우는 중고등부 1부 대 예 배 : 11 : 00 ~ 12 : 층 본당
신앙의 기초를 세우는 중고등부 1부 대 예 배 : 11 : 00 ~ 12 : 층 본당
◆ 지난주 반별 출석 보기 ◆ 제 56 권 26호 년 6월 26일 반 선생님 친구들 재적 출석 5세 화평 김성희 선생님
임상시험 규정 (최근 변경 사항 중심으로) -QCRC 보수 교육 과정 전달 교육
성 김대건 피츠버그 한인 성당 그리스도왕 대축일 공지사항
지금 나에게 주신 레마인 말씀 히브리서 13장 8절.
KAINOS 날마다 더하여지는 Kainos News 이번 주 찬양 20 / 300 – 20개의 셀, 300명의 영혼
천주교 의정부교구 주엽동본당 사목협의회 사목활동 보고서
1. 단위사업 관리, 예산관리 사업설정 (교직원협의/의견수렴) 정책 사업 학교 정책 사업 등록 사업 기본정보 목표 설정
서비스산업의 선진화, 무엇이 필요한가? 김 주 훈 한 국 개 발 연 구 원.
통신이론 제 1 장 : 신호의 표현 2015 (1학기).
I. 기업과 혁신.
[ 한옥 실측 ] 1. 약실측 2. 정밀실측 조선건축사사무소.
A제조용수/B환경관리/C시설관리 ㈜ 에이플러스 코리아
Introduction to Network Security
제14장 스팸 메일 대응 기술.
원무 관리 ’15.4.7(화).
노동조합의 기능과 사용자의 고용관계 정책 노사관계론 이성희 교수님
중학교 기술ㆍ가정 1.
George Soros의 투자 전략 협동조합 금융학과 담당교수 : 류 덕 위.
경쟁력 있는 마늘생산 재배기술 삼척시농업기술센터 최 준 수.
임방울의 출생과 성장 - 출생에서 전국명창대회 입상하기까지 - 임방울의 후원자 2 지 춘 상(전남대학교 명예교수)
교육학개론 2조 강재현 황소정 연미란 이호 장윤정 이아림 김효연
2008 대한민국*조경박람회 한국조경사회 / 환경조경발전재단 / 리드엑스포.
전도 Part Ⅱ.
Ⅸ 대한민국의 발전과 국제 정세의 변화 주제3 산업화와 대중문화의 발달.
How to jump ?.
사업계획서 추억을 만드는 기업 ㈜아이포토 인터넷경영정보 2-M 강미선 서남희
2004년 인천시 2차 동시분양 일정표 Monday Tuesday Wednesday Thursday Friday
Korea Under Japanese Rule
HOT100 소개.
1. 자료구조 개념 (1) 자료구조의 개요 1) 자료구조 ① 일련의 자료들을 조직하고 구조화하는 것 ② 자료의 표현과 그것과 관련된 연산 2) 자료구조에 따라 저장공간의 효율성과 프로그램의 실행시간이 달라짐 3) 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이.
Ⅲ. 5S • 3정.
8장 직접 파일.
쉽게 배우는 알고리즘 6장. 해시 테이블Hash Table.
<엘리제를 위하여>를 감상하며 론도 형식 이해하기
해싱(hashing) Ref. C로 쉽게 풀어쓴 자료구조, 생능출판사, 2005.
CHAP 11: 해싱 순천향대학교 하상호.
쉽게 배우는 알고리즘 6장. 해시 테이블Hash Table
CHAP 11: 해싱 순천향대학교 하상호.
국가대표 생애주기교육 프로그램 참여방법 안내
CHAP 11 : 해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
수업 첫 날 교육B 황유미 첫 수업 계획에 대해 알아보도록 하겠습니다..
CHAP 11 : 해싱.
연결링크 이미지를 마일리지샵 내에 기획전으로 제작하여 오픈/노출 사이즈 가로 1000/세로 상관x 배너사이즈 가로 400
해쉬함수 충돌해결법과 특징 강원대학교 컴퓨터과학과 이해원.
해시와 해시 함수.
7장. 해시 테이블Hash Table.
CHAP 11 : 해싱.
해싱 이 현 직
CHAPTER 04 파일 설계(FiLE Design).
Chapter 11 해쉬(Hash) SANGJI University Kwangman KO
C언어 응용 제 15 주 검색.
정렬(Sorting)과 해싱(Hashing)
제 8 장 계산복잡도 개론 검색 문제 알고리즘 강의 슬라이드 8 검색 문제
문서의 작성 정보과학부 이지연.
5. 인류의 건강과 과학 기술 2. 건강관리 1) 면역.
데이터 베이스의 내부 구조.
유예 X-FILE *조사자* 1301권희원 1315이예지 1317장아정 1322홍자현.
CHAP 11:해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
Presentation transcript:

CHAP 11 : 해싱

해싱이란? 해싱은 사전구조(dictionary)를 가장 효율적으로 구현할 수 있는 방법으로 사용됨 대부분의 탐색 방법들은 키 값을 직접 비교함으로써 탐색하고자 하는 항목에 접근 해싱(hashing) 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근 키 값에 대한 산술적 연산 결과를 해시값이라 함 즉, 해싱은 키 값에 대한 해시값을 계산하여 탐색하고자 하는 항목에 접근하는 방법 해시 테이블(hash table) 해시값에 의해 직접 접근이 가능한 구조 해싱은 사전구조(dictionary)를 가장 효율적으로 구현할 수 있는 방법으로 사용됨

추상자료형 사전구조 사전구조(dictionary) 맵(map) 이라 불리기도 함 (키, 값) 쌍을 저장하고 나중에 키를 이용해 값을 탐색할 수 있게하는 구조 영어 단어나 사람의 이름같은 탐색키(search key) 단어의 정의나 주소 또는 전화 번호같은 탐색키와 관련된 값(value) ∙객체: 일련의 (key,value) 쌍의 집합 ∙연산: ▪ add(key, value) ::= (key,value)를 사전에 추가한다. ▪ delete(key) ::= key에 해당되는 (key,value)를 찾아서 삭제한다. 관련된 value를 반환한다. 만약 탐색이 실패하면 NULL를 반환한다. ▪ search(key) ::= key에 해당되는 value를 찾아서 반환한다. 만약 탐색이 실패하면 NULL를 반환한다.

해싱의 구조 해시 함수(hash function) 탐색키 k를 입력받아 해시값 h(k)을 생성 이 해시값은 배열로 구현된 해시 테이블(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.) 키 값들이 알파벳 문자열이라 하고, 해시값은 문자열의 첫 번째 문자만 고려하여 a인 경우 0, b인 경우 1, c인 경우 2, … , z인 경우 25 라 하자. h("array")=0 h("binary")=1 입력데이터: array, binary, bubble, file, digit, direct, zero, bucket

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

해시함수(cont.) 제산 함수 폴딩 함수 h(k)=k mod M 해시 테이블의 크기 M은 소수(prime number) 선택 이동 폴딩(shift folding)과 경계 폴딩(boundary folding) 이동 폴딩: 탐색 키를 여러 부분으로 나눈 값들을 더하여 해시값 계산 경계 폴딩: 탐색 키의 이웃한 부분을 거꾸로 더하여 해시값 계산

해시함수(cont.) 중간제곱 함수 비트추출 함수 숫자 분석 방법 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시값 생성 해시 테이블의 크기가 2k일때 탐색키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용 탐색 키의 일부 정보만을 사용하므로 해시값의 집중 현상이 일어날 가능성이 높다. 숫자 분석 방법 키 중에서 편중되지 않는 수들을 해시테이블의 크기에 적합하게 조합하여 사용 예) 학생의 학번이 200812345라 한다면 입학년도를 의미하는 앞의 4 자릿수는 편중되어 있으므로 가급적 사용하지 않고 나머지 수를 조합하여 해시값을 계산 숫자로 구성된 키에서 각각의 위치에 있는 수의 특징을 미리 알고 있을 때 유용한 방법

충돌해결책 충돌(collision) 충돌해결책 서로 다른 탐색 키를 갖는 항목들이 같은 해시값를 가지는 현상 충돌을 효과적으로 해결하는 방법 반드시 필요 충돌해결책 오픈 어드레싱(Open addressing): 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장 (선형조사법, 이차 조사법, 이중해싱법 등이 이에 해당) 체이닝(Chaning): 각 버켓에 삽입과 삭제가 용이한 연결 리스트 할당

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

선형조사법(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(저장) 한 번 충돌이 시작되면 그 위치 근방에 항목들이 집중되는 군집화(clustering) 문제 발생

이차 조사법(quadratic probing) 선형 조사법과 유사하지만, 다음 조사할 위치를 아래 식 사용 (h(k)+i*i) mod M 조사되는 위치는 다음과 같음 h(k), h(k)+1, h(k)+4,… 선형 조사법에서의 문제점인 군집 문제 크게 완화 가능

이중해싱법(double hashing) 재해싱(rehashing)이라고도 함 오버플로우가 발생하면 원 해시함수와 다른 별개의 해시 함수 사용 step=C-(k mod C) (C는 상수) 이라 할때, h(k), h(k)+1*step, h(k)+2*step, … (예) 크기가 7인 해시테이블에서, 첫 번째 해시 함수가 k mod M 오버플로우 발생시의 해시 함수는 step=5-(k 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(저장)

Load factor O(1 + α) 1: 해시값을 계산하고 해시테이블에 접근하는데 필요한 시간 저장되는 항목의 개수 n과 해시 테이블의 크기 M의 비율 체이닝에서의 평균 탐색 시간 O(1 + α) 1: 해시값을 계산하고 해시테이블에 접근하는데 필요한 시간 α: 리스트를 탐색하는데 필요한 시간

해싱과 다른 탐색 방법의 비교 이진탐색: 삽입/삭제 에서 + n 은 삽입/삭제 후의 shift 하는데 걸리는 시간