해시 표 충돌 처리 방안 -- python 버 전

면접 은 나 를 수천 번 학대 하고, 나 는 면접 을 첫사랑 처럼 기다린다!면접 안 보 러 가 는데 물이 얼마나 많은 지 모 르 겠 어 요.
해시 시계
해시 표 는 데이터 구조 로 python 의 dict 류 는 해시 표를 통 해 이 루어 집 니 다.해시 표 에서 매 핑 관 계 는 키 를 색인 으로 사용 하 는 추상 적 인 것 을 지원 합 니 다. 한 매 핑 에 n n 개의 원 그룹 이 포함 되 어 있다 고 가정 하고 N ≥ n N \ \ geq n N ≥ n 상황 에 대해 사용 범 위 는 (0, N - 1) (0, N - 1) 의 정 수 를 키 로 하기 때문에 길이 가 N N N N 인 검색 표를 사용 하여 이 매 핑 을 표시 할 수 있 습 니 다.해시 표 __getitem__, __setitem__, __delitem__ 등 기본 맵 작업 은 모두 최 악의 경우 O (1) O (1) O (1) O (1) O (1) 의 시간 복잡 도로 완성 할 수 있다.
해시 함수
해시 표 에 서 는 해시 함 수 를 사용 하여 모든 일반적인 키 를 표 의 해당 색인 에 표시 합 니 다.이상 적 인 상황 에서 키 는 해시 함수 에서 0 에서 N - 1 까지 의 범위 내 에 분포 되 지만 실천 에서 두 개 이상 의 서로 다른 키 가 같은 색인 에 매 핑 될 수 있 습 니 다. 이것 은 바로 우리 가 잠시 후에 토론 할 해시 표 충돌 입 니 다.따라서 우 리 는 표를 통 배열 로 개념화 시 켰 다. 그 중에서 모든 통 은 하나의 원 그룹 집합 을 관리 하고 이 원 그룹 들 은 해시 함 수 를 통 해 구체 적 인 색인 으로 보 냈 다.
해시 함수 h h 의 목 표 는 각 키 k k 를 [0, N - 1] [0, N - 1] [0, N - 1] 구간 내의 정수 에 투사 하 는 것 이다. 그 중에서 N N N 은 해시 표 의 통 배열 의 용량 이다.해시 함수 h (k) h (k) h (k) 는 두 부분 으로 구성 되 어 있 습 니 다. 하나의 해시 코드 는 하나의 키 를 하나의 정수 에 투사 합 니 다.하나의 압축 함수 로 해시 코드 를 통 배열 의 색인 에 표시 합 니 다. 이 색인 은 범위 가 구간 [0, N - 1] 의 정수 입 니 다.여기 서 해시 코드 와 압축 함수 에 대해 간단하게 몇 마디 하 겠 습 니 다. 해시 코드 가 자주 사용 하 는 방법 은 위 치 를 정수 처리 (수치 형 데이터 형식 만 유효), 여러 가지 해시 코드 (문자열 의 위 치 를 고려 해 야 함) 와 순환 시 키 는 해시 코드 가 있 습 니 다.압축 함수 상용 방법 구분 방법 (i)  m o d   N ​ i\ mod\ N​ i mod N) 과 MAD 방법 (Multiply - Add - and - Divide).
충돌 처리 방안
위 에서 언급 한 해시 표 의 주요 사상 은 하나의 해시 통 배열 A A 와 하나의 해시 함수 h h 를 사용 하고 이 를 통 해 통 A [h (k)] A [h (k)] A [h (k)] 에 저 장 된 모든 메타 그룹 (k, v) (k, v) (k, v) 을 정렬 하여 매 핑 하 는 것 이다.하지만 때로는 두 개의 서로 다른 키워드 k 1k1 k1 과 k 2 k2 k2 는 h (k 1) = h (k 2) h (k 1) = h (k 2) h (k1) = h (k2) 의 현상, 즉 충돌 이 발생 한다.자주 사용 하 는 해결 방법 은 링크 분리 와 주소 지정 개방 을 포함한다.
분리 링크
충돌 을 처리 하 는 간단 하고 효과 적 인 방법 은 모든 통 A [j] A [j] A [j] 가 자신의 2 급 용 기 를 저장 하고 용기 저장 모듈 (k, v) (k, v) (k, v) (k, v) 을 저장 하 는 것 이다. 이러한 충돌 을 해결 하 는 방법 을 분리 링크 라 고 한다.링크 를 분리 하면 맵 작업 에 간단 한 실현 을 제공 할 수 있 지만 작은 부족 함 이 있 습 니 다. 링크 를 보조 적 인 데이터 구조 로 키 값 이 충돌 하 는 원 그룹 을 저장 해 야 합 니 다. 공간 이 매우 귀중 한 상황 에서 바람 직 하지 않 습 니 다.
오픈 주소 지정
충돌 하 는 원 조 를 해시 통 배열 의 빈 위치 에 직접 저장 하면 공간 을 절약 할 수 있 지만 이것 은 더욱 복잡 한 메커니즘 이다.
선형 탐지 및 변종
열 린 주소 지정 으로 충돌 을 처리 하 는 간단 한 방법 은 선형 탐지 이다.이 방법 을 사용 할 때 만약 에 우리 가 하나의 원 그룹 (k, v) (k, v) (k, v) 을 통 A [j] A [j] A [j] A [j] 곳 (여기 j = h (k) j = h (k) j = h (k)) 에 삽입 하려 고 한다 면 A [j] A [j] A [j] 가 점용 되 었 다 면 우 리 는 A [(j + 1) 를 삽입 하려 고 시도 할 것 이다.  m o d   N ] A[(j+1)\ mod\ N] A[(j+1) mod N], 만약 A [(j + 1)  m o d   N ] A[(j+1)\ mod\ N] A[(j+1) mod N] 도 점용 되 었 으 니 A [(j + 2) 를 사용 해 보 겠 습 니 다.  m o d   N ] A[(j+2)\ mod\ N] A[(j+2) mod N] 새 메타 그룹 을 받 아들 일 수 있 는 빈 통 을 찾 을 때 까지 반복 합 니 다.
선형 탐 사 는 공간 을 절약 할 수 있 지만 존재 하 는 문 제 는 선형 탐 사 는 매 핑 된 요 소 를 집중 적 으로 저장 하 는 경향 이 있 는데 이런 연속 적 인 해시 단원 의 운행 방식 을 사용 하면 검색 속도 가 크게 떨어진다 는 것 이다.
이차 탐지
또 다른 오픈 주소 지정 전략 은 2 차 탐지 라 고 하 는데, 반복 탐지 통 A [(h (k) + f (i)))  m o d   N ] ,   i = 0 , 1 , 2 , . . . A[(h(k)+f(i))\ mod\ N],\ i=0,1,2,... A[(h(k)+f(i)) mod N], i = 0, 1, 2, 그 중 f (i) = i 2 f (i) = i ^ 2 f (i) = i2, 빈 통 이 발 견 될 때 까지.선형 탐지 와 마찬가지 로 2 차 탐 사 는 삭제 작업 을 더욱 복잡 하 게 하지만 선형 탐지 에서 발생 하 는 집적 모델 을 피 할 수 있다.
반복 탐지
모 이 는 것 을 피 하 는 또 다른 개방 주소 지정 방법 은 반복 적 으로 통 A [(h (k) + f (i) 를 탐지 하 는 것 이다.  m o d   N ] A[(h(k)+f(i))\ mod\ N] A[(h(k)+f(i)) mod N], 여기 f (i) f (i) f (i) 는 위조 난수 생 성기 기반 함수 로 원시 해시 코드 위 치 를 기반 으로 중복 가능 하지만 무 작위 적 이 고 연속 적 인 주소 탐지 서열 을 제공 합 니 다.python 의 사전 류 는 현재 이런 방법 을 사용 하고 있 습 니 다.
참고 자료:
《 데이터 구조 와 알고리즘 – Python 언어 실현 》