해시 알고리즘 원리

       uthash     

4. 567917. 응용 배경 은 모두 가 알 고 있 듯 이 배열 의 특징 은 무 작위 로 방문 할 수 있다 는 것 이다. 즉, 주 소 를 찾기 쉽 지만 삽입 과 삭제 가 어렵다.링크 의 특징 은 무 작위 접근, 즉 주소 찾기 가 어렵 지만 삽입 과 삭제 가 쉽다 는 것 이다.해시 구 조 는 배열 과 링크 의 특성 을 종합 하기 위해 디자인 된 데이터 구조 로 주소 찾기 가 쉽 고 삽입 과 삭제 가 편리 한 특성 을 동시에 만족 시 키 는 것 이다
4. 567917. 해시 원리 해시 표 (또는 산 목록) 를 도입 할 때 가장 효과 적 인 검색 방법: 해시 방법 이다.본질 적 으로 해시 표 는 하나의 배열 로 특수 한 색인 값 을 통 해 배열 의 요 소 를 방문 합 니 다. 키워드 값 을 입력 하고 해시 함 수 를 통 해 이 키워드 값 에 대응 하 는 요소 가 해시 표 에 저 장 된 단원 의 주 소 를 계산 하여 빠 른 접근 요 소 를 실현 합 니 다.다음 과 같이 해시 함수 (hash 함수): f (키워드 값 K) - - - - > 산 목록 에 있 는 K 를 키워드 로 하 는 요소 의 저장 주 소 는 위 와 같 습 니 다. 해시 함수 의 입력 은 – 키워드 값 이 고 출력 은 – 키워드 값 에 대응 하 는 요소 의 저장 장치 의 주소 입 니 다. 산 목록 에서 해당 하 는 요 소 를 직접 방문 할 수 있 기 때문에 해시 표 의 가장 큰 특징 은...해시 함수 의 계산 과 배열 의 색인 을 통 해 상수 의 고정 시간 만 소모 하여 요소 에 빠르게 접근 하 는 목적 을 실현 합 니 다.산열 방법의 핵심 은 산열 함수 와 충돌 해소 방법 이다. 좋 은 함 수 를 얻 기 위해 서 는 함수 f 가 키워드 K 를 구성 하 는 모든 기호 와 관련 이 있어 야 한다. 만약 에 K 가 키워드 집합 에서 무 작위 로 선택 한 것 이 라면 f (K) 가 등 확률 로 구간 [0, M - 1] 중의 모든 값 을 취하 고 이 성질 을 만족 시 키 는 산열 함수 가 균일 하 다 는 것 을 실험 적 으로 증명 한다.두 가지 해시 함수 가 상당히 좋 습 니 다. 하 나 는 나눗셈 을 바탕 으로 하 는 것 이 고 다른 하 나 는 곱셈 을 바탕 으로 하 는 해시 함수 가 키워드 값 으로 해시 인 코딩 을 계산 할 때 두 개의 서로 다른 키워드 값 으로 계산 한 해시 인 코딩 이 같은 상황 이 발생 할 수 있 습 니 다. 이때 충돌 이 발생 했 습 니 다. 좋 은 해시 함 수 는 충돌 을 최대한 줄 일 수 있 습 니 다.그러나 충돌 이 완전히 없어 질 수 없고 충돌 을 해결 하 는 것 도 넘 치 는 처리 기술 이 된다. 흔히 볼 수 있 는 충돌 을 해결 하 는 방법 은 지퍼 법 과 주소 법 이다
4. 567917. 자주 사용 하 는 해시 방법 은 지퍼 법 과 주소 법 이 있다.(1). 지퍼 법 은 해시 함수 의 값 영역 [0, M - 1] 의 모든 값 이 하나의 노드 가 아 닌 하나의 체인 을 유지 하고 특정한 해시 주 소 를 여러 개의 관건 적 인 값 으로 공유 할 수 있 습 니 다. 즉, 모든 체인 에 키워드 가 서로 충돌 하 는 요소 가 존재 합 니 다. 모든 링크 는 하나의 통 으로 볼 수 있 고 요 소 를 삽입 할 때해시 함 수 를 통 해 먼저 요소 가 그 통 에 속 하 는 지 계산 한 다음 에 해당 하 는 체인 헤더 에 요 소 를 삽입 하고 요 소 를 찾 거나 삭제 할 때 어느 통 인지 확인 한 다음 에 해당 하 는 통 을 옮 겨 다 니 며 찾 으 려 는 요 소 를 발견 할 때 까지 합 니 다.모든 통 은 하나의 링크 로 요 소 를 포함 하 는 개 수 를 제한 하지 않 지만 크게 변 하면 성능 이 떨어진다.N 개의 요소 M 개의 값 이 있 는 해시 표 에 대해 각 체인 의 평균 길 이 는 N / M 이 고 해시 기술 은 순서대로 검색 하 는 데 걸 리 는 시간 보다 M - 1 배 단축 되 었 다.또한 요소 의 수량 이 적 을 때 공간 을 절약 하기 위해 지퍼 기술 을 개선 할 수 있 습 니 다. 방법 은 당직 구역 의 모든 값 을 유지 할 때 하나의 체인 이 아 닌 추가 지침 을 가 진 노드 입 니 다.이 체인 은 이 값 이 충돌 할 때 다음 키워드 에 대응 하 는 요소 가 해시 표 에 저장 해 야 할 위 치 를 가리 키 는 데 사 용 됩 니 다. 이 위 치 는 해시 표 꼬리 에서 역순 으로 위로 찾 은 첫 번 째 빈 값 영역 노드 입 니 다.이렇게 하면 M 개 요소 와 M 개 연결 (포인터) 에 만 저장 공간 을 제공 하고 N 개 요소 의 M + N 개 연결 에 만 저장 공간 을 제공 합 니 다.그리고 개 선 된 후에 요 소 는 표 에 삽입 되면 이동 할 필요 가 없습니다.(단, 제한 은 N (2) 입 니 다. 주소 법 을 여 는 방법 은 링크 를 만 들 필요 가 없습니다. 산 목록 의 길 이 를 M 이 라 고 가정 하고 빈 표 부터 표 에 새 요 소 를 삽입 하여 목록 을 만 듭 니 다. 관건 값 이 K 인 요 소 를 삽입 하 는 방법 은 특정한 순서에 따라 새로운 요 소 를 삽입 할 수 있 는 빈 위 치 를 탐색 하 는 것 입 니 다. 주소 f (K) 를 기본 주소 라 고 부 릅 니 다. 만약 f (K)이미 점용 되 었 습 니 다. 충돌 을 해결 하 는 방법 은 특정한 순서 로 표 의 항목 을 검색 하 는 것 입 니 다. 키 워드 를 찾 을 때 까지 주어진 K 와 같 거나 빈 자 리 를 찾 을 때 까지 이 요 소 를 삽입 하 는 것 입 니 다. 선형 탐사 법 은 충돌 시의 탐사 순 서 를 순서대로 아래로 내 리 는 것 입 니 다. 끝까지 빈 자 리 를 찾 지 못 하면 표 시작 부분 으로 순환 하여 계속 아래로 탐색 하 는 것 입 니 다. 선형 탐사 법의 단점 은많은 요 소 를 하나 로 연결 시 켜 '집적' 현상 을 일 으 킬 수 있 습 니 다. 개 선 된 방법 은 충돌 할 때 위 랜 덤 발생 기 를 사용 하여 다음 탐사 의 위 치 를 계산 하 는 것 입 니 다. 위 랜 덤 발생 기 는 간단 한 함수 로 이 루어 질 수 있 습 니 다. 또한 선형 탐사 법 이 가 져 온 '집적' 을 없 애기 위해 서 입 니 다.현상, 개 선 된 선형 탐사 알고리즘 은 2 차 탐사, 이중 산열 법 등 해시 방법 도 있다. 그 원 리 는 곱셈 산열 을 이용 하여 나눗셈 산열 이 도입 한 군집 현상 을 깨 뜨리 는 것 이다.