[데이터 구조 와 알고리즘] Hash Table

계속 하 다
Hash Table：
1. 무엇이?
2. 무슨 문제 에 쓰 입 니까?
3. 어떻게 사용 하나 요?
4. 실제 응용? 
5. 실제 코드? 
6. 문 제 를 생각한다?
1. 무엇이?
참고:
http://www.cnblogs.com/vamei/archive/2013/03/24/2970339.html
해시 표 (hash table) 는 하나의 집합 A 에서 다른 집합 B 로 의 맵 (mapping) 입 니 다.
상기 대응 과정 을 hashing 이 라 고 합 니 다.A 의 요소 a 는 B 의 요소 b 에 대응 하고 a 는 키 값 (key) 이 라 고 불 리 며 b 는 a 의 hash 값 (hash value) 이 라 고 불 린 다.
해시 표 의 핵심 은 해시 함수 (hash function) 입 니 다. 이 함 수 는 집합 A 중의 요소 가 집합 B 중의 요소 에 어떻게 대응 하 는 지 규정 합 니 다.
4. 실제 응용?
참고:
http://www.cnblogs.com/vamei/archive/2013/03/24/2970339.html
Ethernet 의 FCS: 스피커 를 보고 방송 을 시작 합 니 다 (이 더 넷 과 와 이 파이 프로 토 콜)
IP 프로 토 콜 의 checksum: 최선 을 다 하 는 것 을 참조 하 십시오 (IP 프로 토 콜 상세 설명)
git 의 hash 값: 버 전 관리 3 국 지 참조
로그 인 비밀번호:
MD5, SHA 또는 기타 알고리즘 을 hash 함수 로 사용 합 니 다: 암호 문자열 － hash 값
효과: 사용 하 는 hash 함 수 는 단 방향 성 이 좋 습 니 다. hash 값 으로 키 값 을 추측 하기 어렵 습 니 다.
HASH 와 검색:
hash 함수: 검색 대상 － － 저장 위치
효과: 한 번 hash, 대상 이 있 는 위 치 를 찾 습 니 다.
프로 세 스:
인명 (문자열) 을 키 로 하고, 그룹 아래 에 hash 값 을 표시 합 니 다.각 배열 요소 에는 지침 이 저장 되 어 있 으 며, 가리 키 는 기록 (인명 과 전화번호) 이 있 습 니 다.
"Vamei" 의 기록 을 검색 할 때 hash 를 거 쳐 hash 값 498 을 얻 고 records [498] 를 직접 읽 으 면 기록 을 읽 을 수 있 습 니 다.
배열 records 의 크기 는 HASHSIZE 이 고 HASHSIZE 는 질 수로 선택 되 어 hash 값 이 더욱 고 르 게 분 포 될 수 있 도록 합 니 다.
Python: Hashing

a = 'Obama'
value = 0

for i in a:
	value+=ord(i)
	
print ('Hash value of %r is %r') %(a,value)

<p class="p1"><span class="s1">Hash value of 'Obama' is 480</span></p>

비교:
hash 를 사용 하지 않 고 한 배열 에서 만 검색 할 경우 목표 기록 을 찾 을 때 까지 순서대로 방문 해 야 합 니 다. 알고리즘 복잡 도 는 n 입 니 다.
키 와 hash 함 수 를 이용 하여 적당 한 아래 표 시 를 선택 하여 검색 합 니 다.hash 충돌 이 없 는 전제 에서 우 리 는 한 번 만 선택 하면 아래 표 시 된 요소 가 우리 가 원 하 는 요소 임 을 보증 할 수 있 습 니 다.
배열 은 배열 아래 표시 에 따라 무 작위 접근 (random access, 알고리즘 복잡 도 1) 을 할 수 있 기 때문에 검색 작업 은 hash 함수 의 복잡 도 에 달 려 있 습 니 다.
6. 문 제 를 생각한다?
hash 충돌: 위의 hash 함수 에서 "Obama" 와 "oaamb" 는 같은 hash 값 을 가지 고 있 습 니 다.
충돌 이 발생 한 기록 을 링크 로 저장 하여 hash 값 이 이 링크 를 가리 키 도록 하 는 방안 입 니 다. 이것 은 open hashing 이 라 고 합 니 다.
먼저 hash 값 에 따라 링크 를 찾 은 다음 키 값 에 따라 링크 를 검색 하여 기록 을 찾 을 때 까지 검색 합 니 다.
open hashing 은 지침 을 사용 해 야 합 니 다.우 리 는 때때로 랜 덤 저장 의 장점 을 유지 하기 위해 지침 을 사용 하 는 것 을 피하 기 위해 closed hashing 방식 으로 충돌 을 해결한다.
충돌 기록 을 배열 에 방치 한 위치 에 두 고,
예 를 들 어 그림 에서 Obama 가 삽입 되면 그 다음 에 Oaam b 도 hash 에서 480 위치 로 이동 합 니 다.그러나 480 이 차지 되 었 기 때문에 oaamb 는 다음 유 휴 위 치 를 탐지 하고 (hash 값 을 1 로 추가) 기록 합 니 다.
closed hashing 의 관건 은 다음 위 치 를 어떻게 탐지 하 느 냐 에 있다.
i 번 째 때, 우 리 는 POSITION (i) = (h (x) + f (i)% HASHSIZE 의 위 치 를 탐지 해 야 한다.
위 에서 hash 값 을 1 로 추가 하 는 방식 은 f (i) = 1 을 설정 하 는 것 과 같 습 니 다.우리 가 검색 할 때 POSITION (i) 을 이용 하여 기록 이 나 올 수 있 는 위 치 를 차례대로 탐지 하여 기록 을 찾 을 때 까지 할 수 있다.
f (i) 의 선택 은 서로 다른 결 과 를 가 져 올 수 있다.
배열 이 가득 차 면 closed hashing 은 여러 번 탐지 해 야 빈 자 리 를 찾 을 수 있 습 니 다.이렇게 하면 삽입 과 검색 의 효율 을 크게 줄 일 것 이다.
이 경우 HASHSIZE 를 확대 하고 기 존 기록 을 새로운 비교적 큰 배열 에 넣 어야 한다.이런 조작 을 리 하 싱 이 라 고 한다.
기타 참고:
http://blog.csdn.net/liufei_learning/article/details/19220391
kernel 의 hash table 구현 http://blog.csdn.net/zdl1016/article/details/8882083
http://www.importnew.com/16138.html
처음부터 끝까지 해시 표 알고리즘 을 철저히 해석 합 니 다. http://kb.cnblogs.com/page/189480/