Hashing vs Indexing

2014-11-24 Hashing vs Indexing

hashing 끝판왕

http://www.slideshare.net/KimKyungKun/hashing-10748635

 

 

해싱은 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것.

 

 해싱(hashing)이란 한마디로 말해서 많은 양의 데이터(data)들을 그보다는 작은 크기의 테이블(table)로 대응(mapping)시켜 저장할 수 있도록 하는 일종의 데이터 관리 기법이다.

데이터들을 저장하거나 찾을 때 해쉬함수(hash function)를 사용하여 일정한 시간 내에 데이터들을 효과적으로 찾을 수 있도록 해주는 것이 바로 해싱이다. 

 따라서 데이터들은 순차적으로 저장되는 것이 아니라 테이블 전 영역에 걸쳐서 고루 분포하게 되며, 저장된 데이터를 찾을 때에도 해쉬함수를 사용하면 곧바로 그 위치를 알 수가 있기 때문에 빠르게 데이터를 검색할 수가 있게 된다.

 

Hashing is a specific case of indexing:

Indexing is a general name for a process of partitioning intended at speeding up data look-ups. Indexing can partition the data set based on a value of a field or a combination of fields. It can also partition the data set based on a value of a function, called hash function, computed from the data in a field or a combination of fields. In this specific case, indexing is called data hashing.

http://stackoverflow.com/questions/20621222/hashing-vs-indexing

 

인덱스란, 간단하게 말해 빠른 검색을 하기위해 사용하는 독립된 객체

 ex) 카카오톡 초성검색

인덱스의 종류는 B-tree, 해시(Hash) 등등 여러가지가 있지만 오늘은 해시(Hash)인덱스에 대하여 배워보도록 하겠다. 해시(Hash)인덱스는 검색하고자하는 값을 주면 해시 함수를 거쳐 찾고자하는 키 값이 포함된 버켓을 찾아낸다 

*버킷이란, 인덱스 각 키값과 레코드의 주소값등의 정보를 두는 공간이다.

 

 

 

What is indexing?

Indexing is a way of sorting a number of records on multiple fields. Creating an index on a field in a table creates another data structure which holds the field value, and pointer to the record it relates to. This index structure is then sorted, allowing Binary Searches to be performed on it.

 

What is hashing?

Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find the item using the shorter hashed key than to find it using the original value.

http://stackoverflow.com/questions/13470688/what-is-the-difference-between-hashing-and-indexing

 

Hash is sort of an index: it can be used to locate a record based on a key -- but it doesn't preserve any order of records. Based on hash, one can't iterate to the succeeding or preceding element. This is however, what index does (in the context of databases.)

 

짧은 해시 키를 사용하여 항목을 찾으면 원래의 값을 이용하여 찾는 것보다 더 빠르기 때문에, 해싱은 데이터베이스 내의 항목들을 색인하고 검색하는데 사용된다. 

 

예제.

key   value

7864 Abernathy, Sara 

9802 Epperdingle, Roscoe 

1990 Moore, Wilfred 

8822 Smith, David 

 

각 문자가 26개의 경우를 갖는 예측할 수 없는 값의 길이에서 찾는 것보다, 각각이 오직 9개의 경우를 갖는 네 자리 수에서 일치하는 것을 찾는 것이 더 빠르다. 

 

해싱 알고리즘을 해시 함수라고 부른다. 해싱은 빠른 속도의 데이터 검색 외에도, 전자서명을 암호화하고 복호화하는 데에도 사용된다. 

 

가장 이상적인 해싱 함수

 키 집합의 한 레코드와 버켓 주소 집합의 한 레코드가 1:1 대응. (가급적 중복제외)

 충돌이 적어야 한다.

 

2.1. 완전 해싱 (Perfect Hashing)

- 완전 해싱은 나중에 좋은 해싱 기법으로 언급될 simple uniform 해싱을 의미한다. 즉 서로 다른 키(key)값이 해싱에 의해 주소값을 할당받을 때, 주소값이 절대로 겹치지 않는 이상적인 해싱을 의미한다. 물론 이런 방식은 일대일대응 이외에는 존재하지 않는 방식으로 이상적인 것이다.

2.2. 정형 해싱 (Conventional Hashing)

- 데이타 개수를 이미 알고 있어서, 데이타들이 저장될 주소 범위를 미리 데이타 개수만큼 지정해 두는 방식을 의미한다. 즉, 필요한 메모리의 크기는 미리 측정되고 미리 할당받아야 한다.

2.3. 동적 해싱 (Dynamic Hashing)

- 정형 해싱의 문제점은 데이타를 입력하기 이전에 데이타 개수에 대한 정보가 있어서 메모리를 미리 할당받아야 한다는 점이다. 일반적으로 시간이 지남에 따라서 데이터의 양의 증가하게 되므로 잘못된 측정으로 데이터가 메모리의 범위를 넘게 되면, 더 큰 메모리 크기를 잡고 다시 해싱을 해야 하는 시간적, 자원적 낭비가 일어나게 된다. 동적 해싱은 이러한 데이터의 증감에 적응하기 위해서 나타난 것으로, 동적으로 메모리의 크기를 변화시키는 해싱 기법을 의미한다.