해시(Hash)

해시(Hash)

적은 자원으로 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것이다.

• 해시 함수를 사용하여 저장할 데이터와 연관된 고유한 숫자를 만든 뒤 이를 인덱스로 사용한다.
• 내부적으로 배열을 이용하여 데이터를 저장하기 때문에 빠른 검색 속도(O(1))를 갖는다.

 

1. 해시 함수(Hash Function)

• 저장할 데이터와 연관된 고유한 숫자(Hash Code)를 만든다.
• 저장되는 값들의 key 값을 해시 함수를 통해 작은 범위의 값들로 바꾼다.

 

해시 함수

 

2. 해시 테이블

해시 테이블은 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조로 임의의 원소를 해시 테이블에 저장하려면 해시 함수를 통해 해시 값을 계산하고 해시 값에 따라 저장한다.

 

3. 충돌(Collision) 현상 해결

충돌이란 해시 테이블 내의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것을 말한다.

 

1) 체이닝(Chaining)

연결 리스트로 노드를 계속 추가해나가는 방식이다.

 

체이닝

 

2) 개방 주소(Open Addressing)

해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용한다.

• 선형 탐사: 충돌이 일어난 다음 자리를 계속해서 탐색.
• 이차원 탐사: 다음 자리를 보는 대신 이차 함수(i^2)에 의해 탐색.

 

개방 주소 방식 중 선형 탐사