《 데이터 구 조 》 학습 - Hash (1) -- Hash 소개

Hash Table 해시 표 의 장단 점

해시 테이블 개관

Practical Hash Table

1 해시 테이블 요소

2 Hash Function

21 Hash Function 은 어떻게 선택 합 니까

22 상용 Hash Function

총화

이 시 리 즈 는 (Data Structures and Algorithm Analysis in C, 작가 Mark Weiss) 라 는 책의 학습 노트 입 니 다. 제 가 cc 150 을 할 때 어떤 지식 을 보충 해 야 할 때 이 책 을 꺼 내 서 공부 하고 공유 하 겠 습 니 다. 질문 과 건의 가 있 으 면 저 와 공유 하고 싶 습 니 다.
1. 해시 테이블 의 장단 점
장점: 평균 상수 시간 (constant average time) 내 삽입, 삭제, 찾기 (insert, delete, find) 작업 이 완료 되 었 습 니 다.단점: 그 어떠한 순서 정보 (order information) 도 유효 하 게 기록 되 지 않 기 때문에 findMax, findMin 또는 순서대로 전체 표를 인쇄 해도 선형 시간 내 에 완성 할 수 없습니다.
2. 해시 테이블 개관
가장 간단 한 Hash Table 예 는 하나의 (매우 큰) 배열 이다.예 를 들 어 입력 데이터 가 [0, 999] 범위 내의 정수 라 는 것 을 알 고 있다 면 우 리 는 길이 가 1000 int 인 배열 을 만 들 면 하나의 데 이 터 를 삽입 (해당 배열 의 위 치 를 1) 하고 데 이 터 를 찾 아 (배열 의 위치 가 1 인지 판단) 한 데 이 터 를 삭제 (배열 의 위 치 를 0 으로 설정) 하 는 것 이 매우 쉽다.
3. Practical Hash Table
물론 실제 우리 의 입력 데 이 터 는 범위 가 매우 넓 어서 그렇게 큰 배열 을 만 들 수 없 거나 입력 데 이 터 는 정수 가 아니 라 문자열, 부동 소수점 또는 사용자 정의 형식 에 사용 할 수 있 습 니 다.따라서 직접 맵, 순수 배열 방식 으로 구 성 된 Hash Table 은 우리 의 모든 수 요 를 만족 시 킬 수 없습니다.
3.1 해시 테이블 요소
실 용적 인 Hash Table 을 구성 하려 면 몇 가지 요소 가 있 습 니 다.

Hash 표 주체 Hash 표 의 주 체 는 일반적으로 입력 데이터 와 같은 데이터 구조 로 구 성 된 배열 이다.예 를 들 어 입력 데이터 가 int 이면 int 배열 이 고 입력 데이터 가 string 이면 string 배열 이다.

Hash 표 의 크기 는 일반적으로 Hash 표 의 크기 는 하나의 질 수 이 고 표 의 크기 와 충전 내용 의 다소 도 관련 이 있다.(다음 장 에서 상세 하 게 소개)

Hash Function 은 입력 데 이 터 를 정수 에 비 추어 Hash 표 에 놓 아야 할 위 치 를 찾 습 니 다.

충돌 해결 방안 (Collision Resolution) 은 실제 적 으로 Hash 의 크기 가 입력 데이터 범위 가 크 지 않 을 수도 있 고 Hash Function 이 모든 입력 데이터 가 서로 다른 위치 에 비 치 는 것 을 보장 할 수 없 기 때문에 두 개의 서로 다른 입력 데이터 가 같은 Hash 표 위치 에 배분 되 는 것 은 흔 한 일이 기 때문에 이러한 충돌 을 어떻게 해결 하 느 냐 가 매우 중요 하 다.(다음 장 에서 상세 하 게 소개)

3.2 Hash Function
위 에서 말 한 바 와 같이 Hash Function 은 입력 데 이 터 를 다른 Hash 표 위치 에 비 추 는 역할 을 합 니 다.예 를 들 어 Hash 표 의 크기 가 10 이 고 입력 데이터 가 정수 라면 우 리 는 입력 데이터 모델 10 이후 의 결 과 를 Hash 표 위치 로 하여 모든 데이터 에 대응 하 는 합 법 적 인 위치 가 존재 하도록 보장 할 수 있다.
3.2.1 Hash Function 은 어떻게 선택 합 니까?
답 은 확실 하지 않다.구체 적 인 상황 을 구체 적 으로 분석 하 다.그러나 몇 가지 주요 참고 요소 가 있다.

충돌 을 최대한 줄인다.만약 당신 의 Hash 표 크기 가 10 이 고 입력 데이터 가 10 의 배수 라면, 모드 10 을 Hash Function 으로 사용 하 는 것 은 분명히 매우 어 리 석 습 니 다.

가능 한 한 고 르 게 분포 한다.만약 당신 의 Hash 표 크기 가 10000 이 고 입력 데이터 범위 가 [0, 100] 이 라면, 모드 10000 을 Hash Function 으로 사용 하 는 것 은 분명히 매우 어 리 석 습 니 다.

3.2.2 자주 사용 하 는 Hash Function

가장 많이 사용 되 는 Hash Function 은 데이터 모델 Hash 표 의 크기 입 니 다.

문자열 데이터 라면 자주 사용 하 는 동작 은 Position = ∑ DataSize − 1i = 0Data [DataSize − i − 1] ⋅ 32i 문자열 에서 구체 적 으로 실현 되 는 것 은 (data 가 입력 문자열 의 첫 글자 라 고 가정)

unsigned Position=0;
while(*data!='\0')
Position=(Position<<5) + *data++;
return Position % TableSize;

4. 총화
Gayle McDowell (Cracking the coding interview 저자) 에 따 르 면 Hash 표 는 면접 에서 가장 많이 사용 되 는 데이터 구조 중 하나 이 므 로 튼튼 하 게 파악 해 야 한다.이상 은 Hash Table 의 가장 기본 적 인 개념 입 니 다. 실제 사용 가능 한 Hash 표를 만 들 기 에는 부족 합 니 다.그렇다면 세부 사항 을 구체 적 으로 실현 하려 면 어떻게 해 야 할 까?충돌 해결 방안 에는 어떤 전형 적 인 방법 이 있 습 니까?다음 편 '데이터 구조 학습' - Hash (2) – Separate Chaining '을 기대 해 보 세 요!