Java의 해시 테이블에 대한 자세한 소개

해시 테이블이란 무엇인가요?

해시 테이블이라고도 불리는 해시 테이블은 키와 값 간의 매핑 관계를 제공하는 데이터 구조입니다. 일치하는 값을 효율적으로 찾고 시간 복잡도는 O(1)에 가깝습니다.

온라인 학습 동영상 추천: java 동영상

해시 테이블 작동 방식

해시 테이블은 본질적으로 배열입니다. 우리는 a[0], a[1], a[2], a[3], a[4]와 같은 첨자를 기반으로 배열에 무작위로 액세스할 수 있다는 것을 알고 있습니다. 이러한 방식으로 쿼리 효율성이 매우 높습니다. 해시 테이블에서는 키를 제공하면 해당 값을 즉시 쿼리할 수 있습니다. 이때 키와 배열 첨자를 어떤 식으로든 변환하기 위한 '전송 스테이션'이 필요하며, 이 전송 스테이션이 해시 함수이다.

다른 언어에서는 해시 함수가 다른 방식으로 구현됩니다. Java에서 사용되는 것은 HashMap입니다. HashMap。

在Java及大多数的面向对象的语言中，每个对象都有属于自己的hashcode

Java 및 대부분의 객체 지향 언어에서 각 객체에는 서로 다른 객체를 구별하기 위한 자체 해시코드가 있으며 이 해시코드는 정수 변수입니다. 이 시점에서 우리는 이 정수 변수를 배열의 첨자로 변환해야 합니다. 가장 간단한 변환 방법은 배열 길이의 모듈로를 취하는 것입니다.

공식은 다음과 같습니다:

index = HashCode(key) % Array.length

예:

길이가 8인 배열이 있을 때 키 "001121"에 해당하는 Vaule을 찾고 "001121"의 해시코드는 1420036703입니다. 다음을 사용할 수 있습니다. 계산에서는 먼저 배열 첨자를 얻습니다.

index = HashCode("001121")%Array.length = 1420036703 % 8 = 7

해시 테이블의 읽기 및 쓰기 작업

1. 쓰기 작업

쓰기 작업은 해시에 새 키-값 쌍을 삽입하는 것입니다. 테이블(jdk에서는 Entry라고 함)

구체적인 방법은 다음과 같습니다. 해시 함수를 통해 키 값을 배열 첨자로 변환한 다음 배열의 해당 위치에 Entry를 삽입합니다(값뿐만 아니라 항목 키-값 쌍인 Key+Value라는 점에 유의하세요). . 서로 다른 키 값이 동일한 첨자로 변환되어 해시 충돌이 발생할 수 있다고 생각됩니다.

해시 충돌을 해결하기 위해 일반적으로 사용되는 방법은 개방형 주소 지정 방법과 연결 목록 방법입니다.

개방형 주소 지정 방법의 기본 아이디어는 해시 충돌이 발생하면 항목이 배열의 다음 빈 위치에 배치됩니다. 즉, 하나씩 뒤로 이동합니다.

연결된 목록 메서드(Java의 HashMap 컬렉션 클래스에 적용됨)의 기본 아이디어는 배열의 각 요소가 항목 개체일 뿐만 아니라 연결 목록의 헤드 노드이기도 한다는 것입니다. 각 Entry 객체는 다음 포인터를 통해 다음 Entry 노드를 가리킵니다. 새 항목 개체가 충돌하는 배열 위치에 매핑되면 해당 연결 목록에만 삽입하면 됩니다.

2. 읽기 작업

읽기 작업은 쓰기 작업에 해당하며 충돌 상황만 특별히 처리하면 됩니다.

구체적인 아이디어는 해시 함수를 사용하여 찾을 키 값을 배열 첨자로 변환한 다음 배열의 해당 위치에 있는 키 값이 우리가 찾고 있는 키인지 확인하는 것입니다. 발견되면 항목이 반환될 수 있습니다. 그렇지 않으면 연결된 목록을 계속 검색하여 해당 키 값이 있는지 확인하세요.

예를 들어 Key 002936에 해당하는 값을 찾으려면 먼저 Key를 배열 첨자로 변환하고 첨자 2를 얻습니다. 그런 다음 요소를 확인하고 해당 요소의 Key가 002947임을 확인합니다. 쿼리하려는 키가 아닙니다. 그런 다음 연결된 목록을 계속 검색하세요.

3. 확장

배열의 요소 수가 배열의 최대 길이에 도달하면 배열 확장이 필요하다는 것을 알고 있습니다. 그러면 해시 테이블은 언제 확장됩니까?

여러 요소 삽입 후 해시 테이블이 어느 정도 포화 상태에 도달하면 해시 충돌 가능성이 높아집니다. 이때 동일한 배열 첨자 위치에 많은 수의 요소가 붐비므로 이후의 문제가 됩니다. 삽입과 쿼리는 작업의 성능에 큰 영향을 미치며 이때 해시 테이블을 확장해야 합니다.

해시 테이블 확장에 영향을 미치는 요소는 다음과 같습니다.

🎜

Capacity，即HashMap的当前长度

LoadFactor，即HashMap的负载因子，默认值为0.75

扩容需要满足的条件：

HashMap.Size >= Capacity X LoadFactor

简单解释为：当哈希表中的条目数超出了当前容量与其加载因子的乘积时，并且要存放的位置已经有元素了（哈希碰撞），这两个条件满足时，需要进项扩容，会将容量扩大为原来的两倍。加载因子默认值0.75，是在空间和时间上的一个折中，加载因子过高（发生冲突可多存放在链表），虽然减少了空间成本，但也增加了查询成本。

扩容的步骤：

扩容不是简单地把散列表的长度扩大，而是经历了下面两个步骤：

1.扩容，创建一个新的Entry空数组，长度时原数组的2倍；

2.重新Hash，遍历原Entry数组，所有的Entry重新Hash到新数组中。

经过扩容，原本拥挤的散列表重新变得稀疏，原有的Entry也重新得到了尽可能均匀的分配。需要注意的是，关于HashMap的实现，JDK8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时，为了提高插入和查找的效率，HashMap会把Entry的链表转化为红黑树这种数据结构。

相关文章教程推荐：java语言入门

위 내용은 Java의 해시 테이블에 대한 자세한 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!