왜 그리고 어디에서 해시를 사용합니까?

Question

검색에 해싱을 사용하는 이유는 무엇입니까? 바이너리 검색 트리보다 해시를 사용하면 어떤 점이 좋은가요? , 삽입 일반적으로 느린 속도 나무보다 읽

http://en.wikipedia.org/wiki/Hash_table#Features

요약 :

Answer 1

위키 백과가 잘 설명합니다.

Java의 경우 : 많이 읽거나 자주 쓰지 않고 모든 것이 쉽게 RAM에 들어가는 키/값 쌍이 있으면 언제든지 HashTable을 사용하여 빠른 읽기 액세스와 놀라운 코드 유지 관리가 가능합니다.

Answer 2

해싱은 일반적으로 일정 시간 작업이지만 이진 트리는 로그 시간 복잡성을 갖습니다.

해시는 컬렉션의 항목 수를 기반으로 계산되지 않고 검색중인 항목에 따라 계산되므로 컬렉션 크기는 항목을 찾는 데 걸리는 시간과 관련이 없습니다. 그러나 대부분의 해시 알고리즘에는 충돌이 발생하여 시간 복잡성이 높아 지므로 완벽한 일정 시간 조회가 불가능합니다.

이진 트리를 사용하면 log2N 비교를 수행해야 항목을 찾을 수 있습니다.

Answer 3

해싱 일부 대표 정수 값 오브젝트 데이터를 매핑하는 일부 기능 또는 알고리즘을 사용 의미한다. 이 소위 해시 코드 (또는 단순히 해시) 은 항목을 찾을 때 Google 검색 결과를 개로 좁히는 방법으로 사용할 수 있습니다.

필요는 해시 테이블 사용하기에 가장 적합한 알고리즘 입니다 다음 필요한 정보 를 찾고에 대한 빠른 알고리즘, 로 단순히 키 객체의 해시를 생성하고 사용을 사용하는 경우 대상 데이터 인 에 액세스하려면 O (1)입니다. 다른 사람은 O (N)입니다 (연결된 목록의 크기는 입니다. 목록을 한 번에 하나씩 반복해야합니다. N/2는 번) O (log N) (이진 트리 - 너 각각 반복으로 검색 공간을 절반으로 줄이십시오 - 트리가 일 경우에만 구현에 따라 다르므로 불균형 트리를 사용하면 의 성능이 크게 떨어질 수 있습니다.

Answer 4

해시 테이블은 삽입량이 낮고 균일 한 슬롯 배포가있는 경우 검색 (=)에 가장 적합합니다. 시간 복잡도는 O (n + k) - 선형입니다.

당신이 비교 연산 수행하려는 경우 그들은 (<를>)