해시

해시 (Hash)

특징

• 해시를 이용하면 메모리를 많이 소요하지만 최대 빠른 속도로 관리할 수 있다.
• DB 소프트웨어에서 많이 사용된다.
• 수학적 연산을 통한 키를 이용하여 값에 접근한다.
  • 나머지를 사용하는 방법이 보편적이다.
  • 테이블 크기를 소수로 설정하여야 충돌 확률이 낮다.
• 키가 중복이 생길 경우 충돌이 생긴다고 표현하는데 이를 해결하는 방법에는 2가지가 있다.

충돌 해결

충돌 시 다른 위치에 저장하기

1. 선형 조사법

• 키가 중복이 생기면 해당 키의 다음 인덱스에 데이터를 저장한다.
• 다시 중복이 생기면 인덱스+1을 해나가며 저장한다.
• 단점
  • 충돌이 발생하기 시작하면 유사한 값을 가지는 데이터가 밀집되는 집중 결합 문제가 발생한다.
  • 테이블의 크기가 매우 크면, 충돌은 적어지고, 데이터에 빠르게 접근할 수 있다.

2. 이차 조사법

• 키 값이 중복되면 완전 제곱수를 더해 나가며 저장한다.
• 인덱스+1, 인덱스+4 …

선형 조사법 및 이차 조사법에서 데이터의 수가 테이블 인덱스를 초과하게 되면 크기를 확장하여 유지할 수 있도록 설정하여야 한다.

충돌 시 하나의 bucket에 여러 데이터 저장하기

1. 체이닝 기법

• 연결리스트를 활용하여 동일한 키를 가지는 인덱스들을 연결하여 저장한다.
• 연결리스트를 사용하기 때문에 삽입 삭제가 용이하다.
• 테이블 크기는 동적 메모리할당을 통해 해결이 가능하지만 추가적인 메모리 공간이 요구된다.