해싱

해싱은 매우 효율적입니다. 해싱을 사용하여 요소를 검색, 삽입 및 삭제하는 데 O(1) 시간이 걸립니다. 균형 잡힌 검색 트리에서는 O(log n) 시간 안에 요소를 찾을 수 있습니다. 컨테이너에서 요소를 검색하는 더 효율적인 방법이 있습니까? 이 장에서는 해싱이라는 기술을 소개합니다. 해싱을 사용하면 O(1) 시간 안에 요소를 검색, 삽입, 삭제하는 맵이나 집합을 구현할 수 있습니다.

해싱이란 무엇입니까?

해싱은 해싱 함수를 사용하여 키를 인덱스에 매핑합니다. 해싱을 소개하기에 앞서 해싱을 이용해 구현한 자료구조인 맵에 대해 살펴보겠습니다. 맵(섹션에 소개됨)은 항목을 저장하는 컨테이너 개체라는 점을 기억하세요. 각 항목에는 키와 값이라는 두 부분이 포함되어 있습니다. 검색 키라고도 하는 이 키는 해당 값을 검색하는 데 사용됩니다. 예를 들어 사전은 단어가 키이고 단어의 정의가 값인 맵에 저장될 수 있습니다.

지도는 사전, 해시 테이블 또는 연관 배열이라고도 합니다.

Java 컬렉션 프레임워크는 지도 모델링을 위한 java.util.Map 인터페이스를 정의합니다. 세 가지 구체적인 구현은 java.util.HashMap, java.util.LinkedHashMap 및 java.util.TreeMap입니다. java.util.HashMap은 해싱을 사용하여 구현되고, java.util.LinkedHashMap은 LinkedList을 사용하고, java.util.TreeMap은 빨간색을 사용하여 구현됩니다. -검은나무.

배열에 있는 요소의 인덱스를 알고 있는 경우 O(1) 시간 내에 인덱스를 사용하여 요소를 검색할 수 있습니다. 그렇다면 값을 배열에 저장하고 키를 인덱스로 사용하여 값을 찾을 수 있다는 뜻인가요? 대답은 '예'입니다. 키를 인덱스에 매핑할 수 있다면 그렇습니다. 값을 저장하는 배열을 해시 테이블이라고 합니다. 해시 테이블의 인덱스에 키를 매핑하는 함수를 해시 함수라고 합니다. 아래 그림에 표시된 것처럼 해시 함수는 키에서 인덱스를 얻고 이 인덱스를 사용하여 키 값을 검색합니다. 해싱은 검색을 하지 않고 키에서 얻은 인덱스를 이용하여 값을 찾아내는 기술이다.

키에서 인덱스를 생성하는 해시 함수를 어떻게 설계합니까? 이상적으로는 각 검색 키를 해시 테이블의 다른 인덱스에 매핑하는 함수를 설계하고 싶습니다. 이러한 함수를 완벽한 해시 함수라고 합니다. 그러나 완벽한 해시 함수를 찾는 것은 어렵습니다. 두 개 이상의 키가 동일한 해시 값에 매핑되면 충돌이 발생했다고 말합니다. 이 장의 뒷부분에서 충돌을 처리하는 방법이 있지만, 우선 충돌을 피하는 것이 좋습니다. 따라서 충돌을 최소화하는 빠르고 계산하기 쉬운 해시 함수를 설계해야 합니다.

위 내용은 해싱의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!