해싱

해싱이란 키 해싱 키값의 산술적인 연산을 통해서 인덱스를 계산하는 방법이다.

해싱에서 킷값으로부터 레코드가 저장될 위치를 계산하는 함수를 해시함수

계산된 위치에 레코드를 저장한 테이블을 해시태이블

해시테이블이 충뿐히커서 몯 담을 수 있는 인덱스를 부여받는다면 탐색에 걸리는 연산은 O(1)이다

저장하고 있는 데이터의 크기가 크거나 문자열일 경우에는 문제가 발생한다.

다른 키값에 대해서 같은 헤시 주소가 부과되고 이때문에 충돌이 발생하면 저장할수 있는 슬롯의 크기 보다 더 커지는 오버플로우가 발생하는 이경우를 대비하기 위해서 담과 같은 연산이 존재한다.

• 선형조사
  • 오버플로가 발생한 버킷의 옆버킷에 오버플로우가 발생한 데이터를 삽입한다.
  • 데이터가 일부에 몰빵되는 군집화 현상이 발생할 수 있다.
  • 탐색과정에서 오버플로우가 발생했다고 가정하고 해당헤시 주소로 진입한 뒤 옆으로 이동하면서 탐색을 진행하는데 이때 옆 공간이 비어 있으면 탐색에 실패한것으로 가정한다.
  • 삭제연산을 실행할때 문제가 발생하는데 공간이 비어있으면 탐색에 실패한것으로 간주하기 때문에 오류가 발생할 수 있다 이를 해결하기 위해서 삭제연산 후 비어있는 공간을 다른 데이터로 체워서 오류가 발생하지 않게 만들어준다,
• 이차 조사방법
  • 이를 하기위해서 해싱해서 중복이 발생하면 순차적으로 적용되는 해시 함수에 따라서 해싱이 진행되는 방식이다.
• 이중해싱방법
  • 재해싱 충돌이 발생하면 다른 해싱함수를 사용해서 몰빵을 막는다.
• 체이닝
  • 중복이 발생한 해싱주소에 노드를 생성해서 주소값에 있는 데이터와 링크로 연결한다
  • 내가 봤을 땐 이게 제일 베스트이다.

해시함수

• 제산함수 나머지 연산을 이용함
  • 주로 나누는 수를 소수로 이용한다.
• 폴딩함수
  • 키값의 영영을 나누어서 사용하는 함수
  • 이동폴딩 영역들의 합을 구해서 반환해서 해싱함
  • 경계폴딩 일부영역을 뒤집어서 연산함
• 중간제곱함수
  • 키값의 제곱을 실행하고 이의 이 비트의 중간값을 사용해서 해싱을 하는데 중깐값은 모든숫자와 연관이 높기 때문에 사용한다.
  • a2 + 2ab + b2
• 비트 추출 임의로 비트를 추출해서 사용하는 방법이다
• 숫자분석 그냥 숫자 분석해서 사용하는방법이다
• 문자열인 경우에는 문자열의 글자를 ord()함수를 이용해서 정수로변환하고 이를 연산해서 사용한다,