[java] HashTable은 충돌을 어떻게 처리합니까?
나는 학위 수업에서 HashTable 에서 새 키 항목이 다른 항목과 충돌하면 ‘다음 사용 가능’버킷에 새 항목을 넣는다 .
HashTable충돌 키로 다시 호출 할 때이 충돌이 발생하면 어떻게 올바른 값을 반환할까요?
나는 유형 Keys이 있다고 가정하고 Java가 생성 한 기본값을 반환합니다.StringhashCode()
자체 해싱 함수를 구현하고 조회 테이블 (예 : a HashMap또는 Dictionary)의 일부로 사용하는 경우 충돌을 처리하기위한 전략은 무엇입니까?
소수와 관련된 메모도 보았습니다! Google 검색에서 정보가 명확하지 않습니다.
답변
해시 테이블은 두 가지 방법 중 하나로 충돌을 처리합니다.
옵션 1 : 각 버킷에 해당 버킷에 해시 된 요소의 링크 된 목록이 포함되도록합니다. 이것이 잘못된 해시 함수가 해시 테이블에서 조회를 매우 느리게 만들 수있는 이유입니다.
옵션 2 : 해시 테이블 항목이 모두 가득 차면 해시 테이블이 보유한 버킷 수를 늘린 다음 테이블의 모든 요소를 재배포 할 수 있습니다. 해시 함수는 정수를 반환하고 해시 테이블은 해시 함수의 결과를 가져 와서 버킷에 도달 할 수 있도록 테이블의 크기에 맞게 수정해야합니다. 따라서 크기를 늘리면 운이 좋으면 객체를 다른 버킷으로 보낼 수있는 모듈로 계산을 다시 해시하고 실행합니다.
Java는 해시 테이블 구현에서 옵션 1과 2를 모두 사용합니다.
답변
“새 키 항목이 다른 항목과 충돌하면 해시 테이블이 ‘다음 사용 가능한’버킷에 새 항목을 배치합니다.”에 대해 이야기 할 때 해시 테이블 충돌 해결의 개방 주소 지정 전략 에 대해 이야기하고 있습니다.
충돌을 해결하기 위해 해시 테이블에 대한 몇 가지 전략이 있습니다.
첫 번째 종류의 큰 방법은 키 (또는 그에 대한 포인터)를 관련 값과 함께 테이블에 저장해야하며, 여기에는 다음이 추가로 포함됩니다.
- 별도의 체인
- 개방 주소 지정
- 통합 해싱
- 뻐꾸기 해싱
- Robin Hood 해싱
- 2-choice 해싱
- Hopscotch 해싱
충돌을 처리하는 또 다른 중요한 방법은 Dynamic resizing 이며, 여기에는 여러 가지 방법이 있습니다.
- 모든 항목을 복사하여 크기 조정
- 증분 크기 조정
- 단조로운 키
편집 : 위의 내용은 wiki_hash_table 에서 빌려 왔으며 더 많은 정보를 얻으려면 가야합니다.
답변
충돌을 처리하는 데 사용할 수있는 여러 기술이 있습니다. 그들 중 일부를 설명하겠습니다
연결 : 연결
에서는 배열 인덱스를 사용하여 값을 저장합니다. 두 번째 값의 해시 코드도 동일한 인덱스를 가리키면 해당 인덱스 값을 연결된 목록으로 바꾸고 해당 인덱스를 가리키는 모든 값은 연결된 목록에 저장되고 실제 배열 인덱스는 연결된 목록의 머리를 가리 킵니다. 그러나 배열의 인덱스를 가리키는 해시 코드가 하나만있는 경우 값은 해당 인덱스에 직접 저장됩니다. 값을 검색하는 동안 동일한 논리가 적용됩니다. 충돌을 피하기 위해 Java HashMap / Hashtable에서 사용됩니다.
선형 프로빙 : 이 기술은 저장할 값보다 테이블에 더 많은 인덱스가있을 때 사용됩니다. 선형 프로빙 기술은 빈 슬롯을 찾을 때까지 계속 증가한다는 개념에서 작동합니다. 의사 코드는 다음과 같습니다.
index = h(k)
while( val(index) is occupied)
index = (index+1) mod n이중 해싱 기술 : 이 기술에서는 두 개의 해싱 함수 h1 (k) 및 h2 (k)를 사용합니다. h1 (k)의 슬롯이 점유되면 두 번째 해싱 함수 h2 (k)가 인덱스를 증가시키는 데 사용됩니다. 의사 코드는 다음과 같습니다.
index = h1(k)
while( val(index) is occupied)
index = (index + h2(k)) mod n선형 프로빙 및 이중 해싱 기술은 개방형 주소 지정 기술의 일부이며 사용 가능한 슬롯이 추가 할 항목 수보다 많은 경우에만 사용할 수 있습니다. 여기에 추가 구조가 사용되지 않기 때문에 체이닝보다 메모리가 덜 사용되지만 빈 슬롯을 찾을 때까지 많은 움직임이 발생하기 때문에 느립니다. 또한 개방형 주소 지정 기술에서 항목이 슬롯에서 제거 될 때 항목이 여기에서 제거되었음을 나타내는 삭제 표시를 두어 비어있는 이유입니다.
자세한 내용은 이 사이트를 참조하십시오 .
답변
최근 HackerNews에 게재 된이 블로그 게시물을 읽어 보시기 바랍니다.
Java에서 HashMap이 작동하는 방법
간단히 말해서 대답은
두 개의 서로 다른 HashMap 키 객체가 동일한 해시 코드를 갖는 경우 어떻게됩니까?
동일한 버킷에 저장되지만 연결 목록의 다음 노드는 없습니다. 그리고 keys equals () 메소드는 HashMap에서 올바른 키 값 쌍을 식별하는 데 사용됩니다.
답변
학위 수업에서 새 키 항목이 다른 항목과 충돌하면 HashTable이 ‘다음 사용 가능한’버킷에 새 항목을 배치한다고 들었습니다.
이것은 오라클 JDK에 대한 최소한 (이것은 실제로 사실이 아니다 이다 API를 다른 구현에 따라서 다릅니다 수있는 구현 세부 사항). 대신 각 버킷에는 Java 8 이전의 연결된 항목 목록과 Java 8 이상의 균형 잡힌 트리가 포함됩니다.
그러면 충돌 키로 다시 호출 할 때이 충돌이 발생하면 HashTable이 올바른 값을 어떻게 반환합니까?
를 사용하여 equals()실제로 일치하는 항목을 찾습니다.
자체 해싱 함수를 구현하고 조회 테이블 (예 : HashMap 또는 사전)의 일부로 사용하는 경우 충돌을 처리하기위한 전략은 무엇입니까?
장점과 단점이 다른 다양한 충돌 처리 전략이 있습니다.
해시 테이블에 대한 Wikipedia 항목 은 좋은 개요를 제공합니다.
답변
Java 8 이후 업데이트 : Java 8은 충돌 처리를 위해 자체 균형 트리를 사용하여 조회를위한 최악의 경우를 O (n)에서 O (log n)로 개선합니다. 자체 균형 트리의 사용은 연결 목록을 사용하고 조회에 대해 최악의 경우 O (n)을 갖는 체인 (Java 7까지 사용)에 대한 개선으로 Java 8에서 도입되었습니다 목록)
질문의 두 번째 부분에 답하기 위해 삽입은 주어진 요소를 해시 맵의 기본 배열에있는 지정된 인덱스에 매핑하여 수행되지만 충돌이 발생하면 모든 요소가 여전히 보존되어야합니다 (보조 데이터 구조에 저장 됨). , 기본 배열에서만 교체되지 않음). 이는 일반적으로 각 배열 구성 요소 (슬롯)를 보조 데이터 구조 (일명 버킷)로 만들고 요소가 지정된 배열 색인에있는 버킷에 추가됩니다 (키가 버킷에 아직 존재하지 않는 경우 대체되는 경우).
조회하는 동안 키는 해당 배열 인덱스로 해시되고 지정된 버킷의 (정확한) 키와 일치하는 요소에 대한 검색이 수행됩니다. 버킷이 충돌을 처리 할 필요가 없기 때문에 (키를 직접 비교) 충돌 문제는 해결되지만 보조 데이터 구조에서 삽입 및 조회를 수행해야하는 비용이 발생합니다. 요점은 해시 맵에서 키와 값이 모두 저장되므로 해시가 충돌하더라도 키가 버킷에서 동일한 지 직접 비교되어 버킷에서 고유하게 식별 될 수 있다는 것입니다.
충돌 처리는 충돌 처리가없는 경우 O (1)에서 연결 (연결된 목록이 보조 데이터 구조로 사용됨) 및 O (log n)에 대한 O (n)으로 삽입 및 조회의 최악의 경우 성능을 제공합니다. 균형 잡힌 나무를 위해.
참조 :
Java 8에는 충돌이 심한 경우 HashMap 객체가 다음과 같이 개선 / 변경되었습니다.
Java 7에 추가 된 대체 문자열 해시 함수가 제거되었습니다.
충돌하는 키가 많은 버킷은 특정 임계 값에 도달 한 후 연결 목록 대신 균형 잡힌 트리에 항목을 저장합니다.
위의 변경 사항은 최악의 시나리오에서 O (log (n)) 성능을 보장합니다 ( https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 )
답변
equals 메소드를 사용하여 키가 짝수인지, 특히 동일한 버킷에 둘 이상의 요소가 있는지 확인합니다.
