Chapter 11 해쉬(Hash) SANGJI University Kwangman KO (kkman@sangji.ac.kr)

Slides:



Advertisements
Similar presentations
비즈쿨 - 정 성 욱 - - 금오공고 비즈쿨 - 정 성 욱 1. 나는 각 단원들의 활동들에 성실하게 참여 하겠습니다. 우리의 다짐 2. 나는 나와 전체의 발전을 위해 각 멘토들의 지도에 순종하겠습니다. 3. 나는 각 단원들을 숙지함으로써 비즈니스 마인드를 함양하고 자신의.
Advertisements

손성수 라이프코치 부모 코칭 skill-up 과정. LOGO INSERT LOGO 손성수 코치 소개 AK 플라자 / 홈플러스 / 도봉여성센타 / 신세계백화점 부모코칭 번동초, 전곡초, 신곡초, 금오초, 배영초, 정자중, 금오중, 부용중, 덕정중, 영신여고, 영신간호비즈니스고.
(목) 심형석 영산대학교 부동산∙금융학과 교수 영산대학교 부동산연구소 소장
아름다운 이들의 행복한 길음안나의 집.
1. 던전 디자인 개요_1 1. ‘던전’ 룬스톤은 던전 한 층에도 여러 개가 존재하며, 각 룬스톤 마다 영향을 미치는 범위가 설정되어 있다. 룬스톤이 영향을 주는 범위에 일정시간 사용자가 위치해 있게 되면 사용자 캐릭터는 ‘유령화’ 되어 버리기 때문에, 사용자는.
Recursion SANGJI University KO Kwangman
일본 선박 개요 - 선박여행 기본정보 및 특징 - Update 2013년 5월 21일 일본 선박팀.
쉽게 배우는 알고리즘 6장. 해시 테이블Hash Table.
kHS 데이터베이스 테이블 및 인덱스 kHS.
스택(stack) SANGJI University Kwangman Ko
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 02. 프로그램의 기본구성.
해싱(hashing) Ref. C로 쉽게 풀어쓴 자료구조, 생능출판사, 2005.
Chapter 9 정렬(sorting) SANGJI University Kwangman KO
Chapter 10 그래프(graph) SANGJI University Kwangman KO
CHAP 11: 해싱 순천향대학교 하상호.
7. 자극과 반응 7-2. 신경계 3. 여러 가지 반응.
제 2 장 변수와 상수.
12 검색.
( Overview of the Course Kwangman Man ( SangJi University.
기업지원 제도 주요 내용 안산고용센터 기업지원팀.
Tree & Heap SANGJI University Kwangman Ko
CHAP 11: 해싱 순천향대학교 하상호.
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
국가대표 생애주기교육 프로그램 참여방법 안내
USB Door Lock System 공 민 표 강 정 이 권 경 곤
성희롱성폭력 온라인 예방교육 이수 방법 포스텍 학생상담센터 성희롱성폭력 상담실.
CHAP 11 : 해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
메소드와 클래스 정의 및 문제 풀이 Method and Class Define and Problem Solve
게임인공지능 제 6 장 스크립트 2008년 5월 6일.
칼빈의 생애와 개혁자로의 변모 사학과 김종식.
Chap. 1 Data Structure & Algorithms
수업 첫 날 교육B 황유미 첫 수업 계획에 대해 알아보도록 하겠습니다..
Power Point 2007년 정보화교육 원미구청 총무과 통신전산팀.
국제의료관광 관련 법, 제도.
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 09. C언어의 핵심! 함수!
연결링크 이미지를 마일리지샵 내에 기획전으로 제작하여 오픈/노출 사이즈 가로 1000/세로 상관x 배너사이즈 가로 400
해쉬함수 충돌해결법과 특징 강원대학교 컴퓨터과학과 이해원.
Chapter3 : 객체지향의 개념 3.1 객체지향(object-oriented)과
해시와 해시 함수.
7장. 해시 테이블Hash Table.
CHAP 11 : 해싱.
CHAP 11 : 해싱.
Lua script cpp서 사용하기 Lua 버전
Part 06 세상을 변화시키는 연산자 안산1대학 디지털정보통신과 임 성 국.
nauten Compiler – Report Ver.3 Mini-C (주간)
남아메리카 선교 김수정, 이하정 전희진, 장성경.
CHAPTER 04 파일 설계(FiLE Design).
C언어 응용 제 15 주 검색.
장애인단체 간담회 마스터 제목 스타일 편집 마스터 제목 스타일 편집 장애인 단체 간담회 마스터 부제목 스타일 편집
JVM의 구조와 메모리 모델 JVM의 내부 구조 클래스 파일 클래스 로더 메소드(method) 영역 힙(heap) 영역
자바 5.0 프로그래밍.
CHAPTER 9-1 한국의 사회복지정책 - 사회보험제도 -
정렬(Sorting)과 해싱(Hashing)
제 8 장 계산복잡도 개론 검색 문제 알고리즘 강의 슬라이드 8 검색 문제
6장 클래스(상속).
제 8장. 클래스의 활용 학기 프로그래밍언어및실습 (C++).
ISO규격에의 대응과 도입 Know-how ㈜드림힐
Chapter 3. Public Key Infrastructure
직장생활 예절 ① - 인사 1.내가 먼저 [인사의 5point] 2.상대방의 눈을 보고 미소지으며 3.상대방에 맞춰서
6월 1주 주간메뉴표 NEW 엄마손 조식 쉐프 삼촌 중식 참새 방앗간 석식 ◎원산지 안내 : 쌀(국내산)
컴퓨터 프로그래밍 기초 - 11th : 파일 입출력 및 구조체 -
성전기공식(안) 식 순 1. 기공미사 2. 기 공 식 3. 축 하 연 천주교 수원교구 퇴촌성당.
워드데이터 삽입 엑셀 차트의 삽입 소리와 동영상 삽입 워드 문서로 파일 저장
경청 Wisdom21 Management Consulting
국어지도 유아교육과 권수연 김아람 중등특수교육과 박수진 양한솔
▶서류관리 프로그램 1. 로그인….2 2. 서류등록 … 서류도착 서류스티커발행
‘주요기업 인사제도 운영실태’ 조사결과(요약)
Lecture 03 제어문과 메소드 Kwang-Man Ko
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 17. 포인터의 포인터.
경찰학 세미나 제 5 강 경찰관직무집행법 2조 5호의 의미 신라대학교 법경찰학부 김순석.
Presentation transcript:

Chapter 11 해쉬(Hash) SANGJI University Kwangman KO (kkman@sangji.ac.kr)

1. 해시의 기본 개념 해시(hash)의 특징 빠른 검색 방법의 일종 탐색시간을 줄이기 위함 자료가 저장되어 있는 위치에 한번에 접근할 수 있는 배열의 성질을 이용 자료 자체와 연관된 숫자를 만들어 낸 뒤 해시 테이블의 해당 위치에 자료를 저장 한 번에 테이블에 접근할 수 있으므로, 해시는 O(1)의 성능을 가짐

2. 해시 메소드 4, 8, 12, 16, 20, 24, 28, 32 해시 테이블 생성 해시 테이블 크기 설정. int hTableSize = 8; int[] hTable = new int[hTableSize]; 해시 메소드 구현 모듈러 연산자(%)를 적용하여 구성 data % hTableSize; data를 입력 받아 해시 테이블의 크기인 hTableSize로 모듈러 연산한 뒤 그 값을 반환 반환된 값 = 자료의 해시 값

삽입 해시 메소드 이용 해시 메소드에서 반환받은 해시 값을 이용해서 그 자료의 저장 위치를 판단 자료 20의 경우 해시 값은 20 % 8 = 4 자료가 저장되어야 할 위치에 이미 다른 자료가 저장되어 있는 현상을 충돌(collision) 이라고 함

충돌 감소 해시테이블의 크기를 소수(prime number)로 만들 수 있음 테이블의 크기를 소수로 구현한 해시 메소드 int hTableSize = 11; int[] hTable = new int[hTableSize]; int hFunc(int data, int hTableSize) {        return data % hTableSize; }

3. 자료를 숫자와 연관 특징 고유한 번호 주기 만약 자료가 숫자가 아니라면 ? 자료를 그와 관련된 숫자로 변환해야 함 자료와 관련된 숫자를 자료의 키(key). 고유한 번호 주기 주민등록번호나 학번과 같이 각 개체 당 고정된 크기의 고유한 번호를 부여할 수 있음 원하는 자료에 할당되어 있는 고유번호를 알아야만 그 자료에 접근할 수 있음

자료에서 숫자 추출 알파벳과 숫자 대응표 문자 숫자 a 1 j 10 s 19 b 2 k 11 t 20 c 3 l 12 u 21 d 4 m 13 v 22 e 5 n 14 w 23 f 6 o 15 x 24 g 7 p 16 y 25 h 8 q 17 z 26 i 9 r 18

호너의 방법(Horner's method) Hash 8, 1, 19, 8 이라는 숫자를 얻을 수 있음 단어에 대한 하나의 키값을 얻는 방법 8 * 263 + 1 * 262 + 19 * 261 + 8 * 260 = 141,78 숫자의 범위가 너무 커지지 않게, 모듈러(%) (8 * 263 + 1 * 262 + 19 * 261 + 8 * 260 ) % hTableSize 좀 더 효율적인 연산 (((8 * 26 + 1) * 26 + 19) * 26 + 8) % hTableSize

4. 충돌 해결 방법 개방 주소법 분리 연결법 배열로 이루어진 해시 테이블의 셀에 바로 자료를 넣는 방법 구현이 간단 충돌을 해결하는 방법이 복잡하고 충돌이 많이 일어나면 성능 저하 분리 연결법 해시 테이블의 셀을 연결 리스트의 헤더로 지정 충돌이 일어날 경우 추가되는 자료를 해당 리스트에 삽입 연결 리스트 구현, 개방 주소법에 비해서 상대적으로 복잡함

순차 탐색 순차 탐색(linear probing) 삽입 충돌이 일어나면 차례로 셀을 검사하여 빈 셀에 자료를 저장 탐색 시 원하는 자료를 찾기 힘듦 삽입 해시 테이블에 삽입할 자료를 입력받아서 hFunc() 메소드를 이용하여 해시 값을 알아낸 뒤, 그 해시 값에 해당하는 해시 테이블의 셀을 찾음 빈 셀이 없으면 다른 셀 탐색 클러스터(cluster) 비어있는 셀이 없이 값을 저장하고 있는 셀로 구성된 덩어리

탐색 자료가 원래 있어야 할 셀에서부터 시작해서 비어있는 셀이 나올 때까지 해시 테이블을 순차적으로 탐색 자료를 찾기 전에 빈 셀을 만나면 그 자료를 찾는 데 실패

삭제 탐색 방법 때문에 순차 탐색의 경우 자료를 삭제할 수 없음 실제로는 삭제하지 않고 삭제했다는 표시만 함

지수 탐색 지수 탐색(quaradic probing) 순차 탐색의 한계 클러스터의 크기가 커질 경우, 처음부터 순서대로 탐색하는 것과 비슷한 성능 빈 셀을 찾기 위해 지수적으로 빈 셀을 탐색 원하는 셀이 비어 있지 않을 경우 바로 다음 셀을 검사 4(=22)번째 셀 9(=32)번째 셀 16(=42)번째 셀 25(=52)번째 셀을 차례로 검사하는 방식 1, 4, 9 등의 숫자를 탐색 단위(step size)라고 함

지수 탐색의 단점 찾기 시작하는 셀이 같은 경우엔 탐색하는 순서가 동일함

이중 해싱 이중 해싱(double hashing) 지수탐색의 탐색 단위가 고정되어 있는 단점을 보완하기 위한 방법으로 제시 첫 번째 해싱 자료를 입력할 셀을 찾는 해싱 두 번째 해싱 첫 번째 해시 값이 충돌이 일어났을 경우에 탐색 단위를 계산하는 데 사용 탐색 단위는 절대 0이 되어서는 안됨 탐색 단위로 해시 테이블을 검색했을 때 테이블의 모든 셀에 접근할 수 있어야 함

두번째 해시 메소드 public int hFunc2(int key) { int f2val;      return f2val - (key % f2val) ; } 변수 f2val이 전체 해시 테이블 크기와 서로소일 경우 테이블의 모든 셀에 접근할 수 있음이 보장됨

이중 해싱 예 키 값 첫 번째 해시 값 두 번째 해시 메소드 23 1 5 7 - (23 % 7) 34 7 - (34 % 7) 45 4 7 - (45 % 7)

삽입 순차 검색의 insert() 메소드와 유사하며, 탐색 단위가 두 번째 해시 메소드인 hFunc2 메소드로 매 자료마다 결정됨 point 변수는 탐색 단위만큼씩 증가함 원하는 자료를 찾기 전에 해시 테이블의 크기보다 커지면 탐색 단위에 맞추어 해시 테이블의 처음 부분으로 돌아가 검사를 계속함 빈 셀이나 삭제 표시가 있는 셀을 발견하면, 그 자리에 자료를 삽입

탐색 삭제 탐색 단위가 각 자료마다 다르다는 것을 제외하고는 순차 탐색과 동일 순차 탐색에서 다음 부분을 변경 point++;    =>    point += hFunc2(key); 삭제 순차 탐색의 삭제 방법과 동일

분리 연결법 분리 연결법(separate chaining) 연결 리스트를 이용하므로 별도의 충돌 해결 방법을 갖지 않음 충돌이 일어나면 충돌이 일어난 셀의 리스트에 링크 추가 리스트의 마지막에 링크를 삽입하는 방법은 원하는 자료를 찾기위해 한 셀의 모든 리스트 검색 링크를 삽입할 때 리스트의 정렬을 유지하는 자리에 링크를 삽입하여 성능을 유지함

탐색 링크 자신의 키 값 보다 큰 값을 발견하거나 리스트의 끝에 도달했을 경우에 탐색에 실패함

삭제 링크 앞에 연결되어 있는 주소를 다른 링크의 주소로 변경