해시와 해시 테이블 Hash Table <1>

해시 Hash

 

해시란? Hash~

* 해시는 해시 함수와 함수에서 나온 해시 값이 있다.

  해시 함수에 매개변수로 들어가는 값은 크기와 자료형에 구애를 받지 않는다.

  반환되는 해시 값은 의도적으로 고정된 길이의 데이터로 바뀐다.

 

* 부동소수점형이나 길이가 고정되지 않은 문자열 등을 언제나 정수형으로 바꾸는 함수를

  해시함수라고 할 수 있다.

 

* 데이터 → 해시 함수 → 해시 값

 

* 해시 함수는 특정 값을 넣으면 언제나 같은 값을 반환한다.

   a를 넣어서 b가 나온다면, a를 몇 번을 넣어도 언제나 b가 나온다.

 

* 하지만 a를 넣어도 b가 c를 넣어도 b가 나올 수 있다.

  이는 매개변수의 폭은 넓은데 반환값은 고정된 크기로 바뀌는 데에서 기인한다.

 

 

해시를 사용해서 좋은 점

* 해시 함수를 사용하여 임의의 데이터를 배열의 인덱스에 적용할 수 있어서,

  해시 값을 만든다면 검색이 O(1)인 구조를 만들 수 있다.

 

* 해시 함수는 데이터를 전혀 연관성 없어 보이는 값으로 바꾸어준다. 

  이는 암호화 역할을 할 수 있다.

 

* 해시 함수는 넓은 범위의 데이터를 축약할 수 있다. 

  잘 사용한다면 기존의 큰 값을 대신해 해시 값을 사용함으로써 효율을 이끌어낼 수 있다.

 

* 블록체인에서 사용자끼리 해시 값을 비교하여 보안을 유지한다.

 

 

 

 

 

해시 테이블 Hash Table

 

이게 먼데 필요하지?

* 해시 테이블은 보통 삽입, 삭제, 검색이 전부 O(1)이다.

* 하지만 평균이 O(1)이고, 최악의 경우 삽입, 삭제, 검색 모두 O(n)이 나올 수 있다.

* 삽입, 삭제가 O(1) 인건 쉽게 생각할 수 있지만 검색이 O(1)이라니?

  쉽게 생각하기 어렵고, 단점을 커버하는 구조는 생각하기 더욱 어렵다.

 

 

검색이 O(1)인 구조란?

<배열의 인덱스와 값이 같은 경우>

* 익덱스 = 값이므로 값의 유무를 한 번에 확인할 수 있다.

* 값에 순서라는 특징을 넣을 수 없다.

* 값이 매우 크다면 배열의 크기 또한 크게 잡아야 한다.

  (값이 20000이라 해서 배열을 20000까지 잡을 수는 없자나)

* 그냥 예시일 뿐 비효율적인 구조이다.

 

 

좀 더 좋은 방법

* 위에 방법의 단점인 값이 매우 크거나 값의 분포의 폭이 클 때 배열을 크기가 매우 커진다.

  를! 커버할 수 있는 간단한 방법이 있다.

 

* (값의 개수) *2 보다 큰 소수 = X라고 하자.

1. 배열의 크기를 X로 잡는다.

2. 값 % X를 인덱스로 잡는다.

 

* 단점이 사라졌다?! and 새로운 단점이 생겼다...

* 1%11= 1이지만 12%11= 1이다!? (중복이 생겼다)

 

* 크기를 왜 2배로 잡는 거지? = 중복을 최대한 피하기 위해

* 왜 X를 소수로 잡는 거지? = 중복을 최대한 피하기 위해

 

즉, 자료들의 검색을 O(1)로 하기 위해 값을 인덱스로 활용하고 싶지만

값이 매우 크거나 값의 분포의 폭이 클 때 배열을 크기가 매우 커진다는 단점을

보완하기 위해 자료→특정 값으로 바꾼다. 바꾼 값은 위에 단점을 없앨 수 있지만

값의 중복이라는 새로운 단점이 생겼다.

 

 

 

 

 

 

 

2편으로 이어집니다......

 

 

 

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.