해시 테이블이란?

IT/Database

swhwang 2019. 1. 18. 13:48

해시 테이블은 보통 여러가지 이름으로 나오기도 합니다만, 예를 들면 python/swift의 dictionary, JSON, PHP의 배열, java/c++의 hashmap등

이것은 컴퓨터안에서 어떻게 실현했는지 설명하고자 합니다.

해시테이블의 특징

1개의 값에 대해서 유일한 키

응? 반대아니야? 라고 생각하는 사람 있을지 모르지만, 사실은 해시테이블을 만들었을때 다른 값을 같은 키로 나누어 버리는 경우도 있는데, 이것을 '충돌'이라고 부른다.

추가라고 부르는 것이 빠르다.

해시테이블도 배열계의 데이터구조의 한 종류로써, 다른 두가지는 배열과 링크리스트가 된다.

배열은 값을 부를때 주소가 있으면 한순간에 끝나지만, 1개의 값을 추가, 삭제하면, 다른 값도 채워지고, 이사하지 않으면 안된다.

링크 리스트는 추가가 빠르지만 (마지막에 들어가기 때문에), 호출 할 때 들어가있는 데이터를 하나씩 확인하지 않으면 안된다.

해시 테이블은 추가 할 때 해시 함수를 돌려 키에서 주소를 얻고 다른 값에 영향을주지 않는쪽으로 호출 할때 키 만 있으면 주소도 키에서 알게 즉시 값을 질문한다.

원리

이것으 흐름이다.

해시 함수

그러면 해시 함수는 어떤 것일까

간단하게 말하면 : 어떤 키가 와도 우선 고유 한 숫자로 변환하는 메서드

예 :

input = [23, 7, 11, 4, 10 (키)

이것은 분명히 5를 나누어 그 나머지를 가지고가는 경우에 중복이 없을 것

Hash 함수 h (key) = n mod 5

Hash 후 [3, 2, 1, 4, 0 (H (key))

해시 테이블에 사용하는 해시 함수는이 세 가지를 요구하고있다

알기 쉬울것

주소를 평균적으로 배부

키의 중복을 피할것

자주 사용되는 해시 함수

1.키가 숫자의 경우 일차 방정식을 취할 : H (key) = a · key + b

2.키가 숫자 인 경우 그 키는 징계 여부를 찾는 중복이 적은 일부를 가지고

3.키가 숫자의 경우, 그리고 징계도 없을 것 같고, 키를 제곱을 복용 제곱 한 결과 가운데 일부를 취한다. (제곱 한 결과 중간 부분은 숫자 전체와 관계 있기 때문에 중복을 피할 수)

4.키를 몇 등분하여 그것을 전부 더한다.

5.난수 함수를 사용

6.테이블의 길이를 나누어 나머지를 구한다.

다양한 소개했다고 생각하지만, 실제로 사용할 때 해시 함수는 중복없이 없으면 어느것이라도 좋다.

해시 테이블의 예

데이터:

이름	손오공	크리닝	피콜로
성적	76	78	66

이것을 이름 -> 성적의 형태로 해시테이블을 만들면

이름의 생략어의 알파벳순이라는 해시함수를 사용하자.

이런 느낌