<div id="readability-page-1" class="page"><div id="root"><div><h2 id="해싱이란">해싱이란</h2>
<p><img src="https://velog.velcdn.com/images/jwlee010523/post/efd6bdaf-e72a-4e8e-8ce6-372c90b7633b/image.png"></p>
<ul>
<li>대부분의 탐색 방법들은 키 값 비교로써 탐색하고자 하는 항목에 접근</li>
<li>해싱(hashing): 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근</li>
<li>해시 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 구조</li>
</ul>
<h2 id="추상-자료형-사전">추상 자료형, 사전</h2>
<h2 id="사전구조dictionary">사전구조(dictionary)</h2>
<ul>
<li>맵(map) 또는 테이블(table)로 불리움</li>
<li>탐색 키와 관련된 값의 2가지 필드로 구성<ul>
<li>영어 단어나 사람의 이름 같은 탐색 키(search key)</li>
<li>단어의 정의나 주소 또는 전화 번호 같은 탐색 키와 관련된 값(value)</li>
</ul></li>
</ul>
<h2 id="해싱의-구조">해싱의 구조</h2>
<h2 id="해시-함수hash-function">해시 함수(hash function)</h2>
<p><img src="https://velog.velcdn.com/images/jwlee010523/post/977b32ab-fc62-4be2-98ea-01b524704b9f/image.png"></p>
<ul>
<li>탐색키를 입력받아 해시 주소(hash address) 생성</li>
<li>이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스</li>
<li>해시 함수 설계 시 충돌 발생하는 경우를 주의해야 함<br>
→ 슬롯으로 간접적으로 해결</li>
</ul>
<h3 id="좋은-해시-함수의-조건">좋은 해시 함수의 조건</h3>
<p><img src="https://velog.velcdn.com/images/jwlee010523/post/aeb0aed9-55fe-4c84-8fa4-747e8a9ca572/image.png"></p>
<ul>
<li>충돌이 적어야 한다</li>
<li>해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 한다</li>
<li>계산이 빨라야 한다</li>
</ul>
<h3 id="제산-함수">제산 함수</h3>
<ul>
<li>나머지 연산자(mod)를 사용하여 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법<br>
<span><span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>h</mi><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo><mo>=</mo><mi>k</mi><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow></mo><mtext> </mtext><mi>M</mi></mrow><annotation encoding="application/x-tex">h(k) = k \bmod M</annotation></semantics></math></span></span></span></li>
<li>해시 테이블의 크기 M은 소수(prime number) 선택</li>
</ul>
<h3 id="폴딩-함수">폴딩 함수</h3>
<ul>
<li>이동 폴딩(shift folding)과 경계 폴딩(boundary folding)<br>
</li>
</ul>
<p><img src="https://velog.velcdn.com/images/jwlee010523/post/340f356e-62cd-47fb-8023-ec696549da77/image.png"></p>
<h2 id="해시-테이블">해시 테이블</h2>
<p><img src="https://velog.velcdn.com/images/jwlee010523/post/c297ec42-d910-4a25-b4f7-5256b7de1bb8/image.png"></p>
<ul>
<li>M개의 버킷(bucket)으로 구성된 테이블</li>
<li>ht[0], ht[1], … , ht[M-1]의 원소를 가짐</li>
<li>하나의 버킷에 s개의 슬롯(slot) 가능</li>
</ul>
<h2 id="충돌collision">충돌(collision)</h2>
<ul>
<li>서로 다른 두 개의 탐색키 k1과 k2에 대하여 같은 해시값 주소를 가져 h(k1) = h(k2)가 되는 경우</li>
<li>충돌이 발생하면 해시 테이블에 항목 저장 불가능</li>
<li>충돌을 효과적으로 해결하는 방법 반드시 필요(선형 조사법, 체이닝)</li>
</ul>
<h3 id="선형-조사법">선형 조사법</h3>
<p><img src="https://velog.velcdn.com/images/jwlee010523/post/56e4dbcc-4a06-4710-b6d0-1afd7a73794c/image.png"></p>
<ul>
<li>충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장</li>
<li>과정<ol>
<li>충돌이 ht[k]에서 발생했다면, ht[k+1]이 비어 있는지 조사</li>
<li>만약 비어있지 않다면, ht[k+2] 조사</li>
<li>비어있는 공간이 나올 때까지 계속 조사</li>
<li>테이블의 끝에 도달하게 되면 다시 테이블의 처음부터 조사</li>
<li>조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 찬거임</li>
<li>조사되는 위치: h(k), h(k) + 1, h(k) + 2, …</li>
</ol></li>
<li>군집화(clustering)과 결합(Coalescing) 문제 발생</li>
</ul>
<h3 id="체이닝">체이닝</h3>
<p><img src="https://velog.velcdn.com/images/jwlee010523/post/6167c302-b391-45e3-b2dc-734fa491cf6d/image.png"></p>
<ul>
<li>각 버킷에 고정된 슬롯이 할당되어 있지 않음</li>
<li>각 버킷에 삽입과 삭제가 용이한 연결 리스트 할당</li>
<li>버킷 내에서는 연결 리스트 순차 탐색</li>
</ul>
<h2 id="오버플로우overflow">오버플로우(overflow)</h2>
<ul>
<li>충돌이 버킷에 할당된 슬롯 수보다 많이 발생하는 것</li>
<li>오버블로우 해결 방법 반드시 필요</li>
</ul>
<h2 id="이상적인-해싱">이상적인 해싱</h2>
<h3 id="학생-정보-저장-및-탐색">학생 정보 저장 및 탐색</h3>
<p><img src="https://velog.velcdn.com/images/jwlee010523/post/fb399dce-10dc-4cf9-91bd-f508b2f1c8f1/image.png"></p>
<ul>
<li>5자리 학번 중에 앞 2자리가 학과 번호, 뒤 3자리가 각 학과의 학생 번호</li>
<li>같은 학과 학생들만 가정하면 뒤의 3자리만 사용해서 탐색 가능</li>
<li>학번이 00023이라면 이 학생의 인적사항은 해시테이블 ht[23]에 저장</li>
<li>만약 해시테이블이 1000개의 공간을 가지고 있다면 탐색 시간이 O(1)이 되므로 이상적임</li>
</ul>
<blockquote>
<p>출처<br>
C언어로 쉽게 풀어쓴 자료구조 - 천인구</p>
</blockquote></div><div><p><a href="https://velog.io/@jwlee010523/posts"><img src="https://velog.velcdn.com/images/jwlee010523/profile/7c945279-cb49-457d-88a8-7134a81936c6/image.jpeg" alt="profile"></a></p></div><div><h4>0개의 댓글</h4></div></div></div>

jwlee010523.log

해싱이란
대부분의 탐색 방법들은 키 값 비교로써 탐색하고자 하는 항목에 접근
해싱(hashing): 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근
해시 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 구조
추상 자료형, 사전
사전구조(dictionary)
맵(map) 또는 테이블(table)로 불리움
탐색 키와 관련된 값의 2가지 필드로 구성
영어 단어나 사람의 이름 같은 탐색 키(search key)
단어의 정의나 주소 또는 전화 번호 같은 탐색 키와 관련된 값(value)
해싱의 구조
해시 함수(hash function)
탐색키를 입력받아 해시 주소(hash address) 생성
이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스
해시 함수 설계 시 충돌 발생하는 경우를 주의해야 함
→ 슬롯으로 간접적으로 해결
좋은 해시 함수의 조건
충돌이 적어야 한다
해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 한다
계산이 빨라야 한다
제산 함수
나머지 연산자(mod)를 사용하여 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법
$h(k) = k \bmod M$
해시 테이블의 크기 M은 소수(prime number) 선택
폴딩 함수
이동 폴딩(shift folding)과 경계 폴딩(boundary folding)
해시 테이블
M개의 버킷(bucket)으로 구성된 테이블
ht[0], ht[1], … , ht[M-1]의 원소를 가짐
하나의 버킷에 s개의 슬롯(slot) 가능
충돌(collision)
서로 다른 두 개의 탐색키 k1과 k2에 대하여 같은 해시값 주소를 가져 h(k1) = h(k2)가 되는 경우
충돌이 발생하면 해시 테이블에 항목 저장 불가능
충돌을 효과적으로 해결하는 방법 반드시 필요(선형 조사법, 체이닝)
선형 조사법
충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
과정
충돌이 ht[k]에서 발생했다면, ht[k+1]이 비어 있는지 조사
만약 비어있지 않다면, ht[k+2] 조사
비어있는 공간이 나올 때까지 계속 조사
테이블의 끝에 도달하게 되면 다시 테이블의 처음부터 조사
조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 찬거임
조사되는 위치: h(k), h(k) + 1, h(k) + 2, …
군집화(clustering)과 결합(Coalescing) 문제 발생
체이닝
각 버킷에 고정된 슬롯이 할당되어 있지 않음
각 버킷에 삽입과 삭제가 용이한 연결 리스트 할당
버킷 내에서는 연결 리스트 순차 탐색
오버플로우(overflow)
충돌이 버킷에 할당된 슬롯 수보다 많이 발생하는 것
오버블로우 해결 방법 반드시 필요
이상적인 해싱
학생 정보 저장 및 탐색
5자리 학번 중에 앞 2자리가 학과 번호, 뒤 3자리가 각 학과의 학생 번호
같은 학과 학생들만 가정하면 뒤의 3자리만 사용해서 탐색 가능
학번이 00023이라면 이 학생의 인적사항은 해시테이블 ht[23]에 저장
만약 해시테이블이 1000개의 공간을 가지고 있다면 탐색 시간이 O(1)이 되므로 이상적임
출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구

알고리즘 - 해싱(Hashing)

댓글