An Introduction to Hashing

An Introduction to Hashing

Namgoong Jae-chang
Dept. of Computer Science and Engneering, POSTECH

---

이 문서는 데이터베이스(database) 분야에서 널리 쓰이는 데이터 관리 기법 중에 하나인 해슁(hashing)에 대하여 설명하고 있다. 따라서 이 문서에서 설명하고 있는 해슁은 자료구조(data structure) 분야에서 다루는 것과는 다소 다른 관점에서 설명하고 있다는 점을 우선 인식하기 바란다. 해슁에 관한 분류가 책마다 다른 관계로 이 문서에서는 필자 나름대로의 분류법에 따랐음도 미리 밝히는 바이다.

1 해슁(Hashing)이란 무엇인가?

2 해슁(Hashing)의 필요성

3 해슁 알고리즘 (Hashing Algorithm)

4 해쉬함수 (Hash Function)

4.1 좋은 해쉬함수

4.2 해쉬함수의 몇 가지 예

5 충돌해결전략 (Collision Resolution Strategy)

6 Open Addressing

6.1 Linear Probing

6.2 Qudratic Probing

6.3 Double Hashing

7 Closed Addressing

7.1 Chaining with Coalescing Lists

7.2 Chanining with Separate Overflow Area

7.3 Using Buckets

8 동적 해슁 (Dynamic Hashing)

8.1 확장 해슁 (Extendible Hashing)

8.2 동적 해슁의 장단점

8.2.1 장점

8.2.2 단점

9 External Searching

9.1 Chaining with Separate Lists

9.2 Open Addressing

10 해슁(Hashing)과 데이터베이스(Database)

References

Footnotes

---

이 문서는 파일 및 데이터베이스 (CS421) 과목을 수강하면서 작성한 보고서 중 하나로, 기본적으로 Otfried Cheong 교수의 Hyperlatex을 이용하여 HTML 문서로 변환되었습니다. 아무쪼록 무단으로 복제하는 일 등은 삼가해 주세요.