자료구조 Hash

정의

해시 테이블은 연관배열 구조를 이용하여 key에 value를 저장하는 자료구조 이

다.

특징

• data의 검색과 저장이 빠르다. O(1)
• 암호화에 사용된다. 입력받은 데이터를 다른 형태로 변환한다. 
• 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다.

->해시 테이블은 기본적으로 많은 공간(메모리)를 이용해 시간을 단축시킨 원리이다.

해시함수

데이터의 value 값을 배열의 인덱스 정수로 변환하는 과정이 필요하고 이때 해시함수를 이용한다.

해시함수는 임의의 크기를 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

key -> mapping(hashing) -> hash value

1) 나눗셈법

해시함수 중에서 가장 간단한 알고리즘에 속한다. 입력 값을 테이블의 크기로 나누고

그 '나머지'를 테이블의 주소로 이용한다.

주소 = 입력값 % 테이블의 크기

나눗셈법은 같은 주소에 다른 데이터가 충돌할 가능성이 있다.

이를 해결하기 위한 가장 기본적인 두가지 방법을 소개하겠다. 

 

1) 개방 주소법 open addressing

주어진 테이블 공간 안에서 문제를 해결하는 폐쇄 해싱

• 선형 탐색 Linear probing

가장 간단한 탐사 방법으로 해시 함수로 얻어낸 주소에 이미 데이터가 있는 경우 그 주소에서

고정된 폭으로 다음 주소로 이동한다. 그곳에도 데이터가 있는 경우 역시 반복하여 비어 있는

주소를 발견하면 그 곳에 데이터를 저장한다.

• 제곱 탐색 Qudratic probing

선형 탐색과 비슷한 방법이지만 고정된 폭으로 이동하는 것이 아니라 

1, 4, 9, 16 처럼 제곱수로 늘어나며 이동한다.

 

2) 체이닝

해시 테이블 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 개방 해싱이다.

채이닝은 해시 함수로 서로 다른 키에 대해 같은 주소값을 반환해서 충돌이 발생하면 각 데이터를

해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법이다. 체이닝 기반의 해시 테이블은

데이터 대신 링크드 리스트에 대한 포인터를 관리한다.

-채이닝 기반 해시 테이블의 탐색

• 찾고자 하는 목표값을 해싱하여 링크드 리스트가 저장되어 있는 주소를 찾는다.
• 이 주소를 이용하여 해시 테이블에 저장되어 있는 링크드 리스트에 대한 포인터를 생성한다.
• 링크드 리스트의 앞에서부터 뒤 까지 차례대로 이동하며 목표값이 저장되어 있는지 비교한다.

-채이닝 기반 해시 테이블의 삽입

• 해시 함수를 이용해 데이터가 삽입될 링크드 리스트의 주소를 얻어낸다
• 링크드 리스트가 비어 있는 경우에는 데이터를 바로 삽입한다
• 그렇지 않은 경우에는 링크드 리스트의 헤드 앞에 삽입한다.