TechCodeview

해싱이란 무엇입니까?

객체를 정수값으로 변환하는 과정입니다. 정수 값은 인덱싱과 빠른 검색에 도움이 됩니다.

해시맵이란?

HashMap은 Java 컬렉션 프레임워크의 일부입니다. 해싱(Hashing)이라는 기술을 사용합니다. 지도 인터페이스를 구현합니다. Key와 Value 쌍에 데이터를 저장합니다. HashMap에는 노드 배열이 포함되어 있으며 노드는 클래스로 표시됩니다. Key와 Value를 저장하기 위해 내부적으로 배열과 LinkedList 데이터 구조를 사용합니다. HashMap에는 4개의 필드가 있습니다.

HashMap의 내부 동작을 이해하기 전에 hashCode()와 equals() 메소드를 알아야 합니다.

자바의 역사

같음():두 개체의 동등성을 확인합니다. 키가 같은지 여부를 비교합니다. Object 클래스의 메소드입니다. 이는 재정의될 수 있습니다. equals() 메서드를 재정의하는 경우 hashCode() 메서드를 재정의하는 것이 필수입니다.해시 코드():이것이 객체 클래스의 방법입니다. 객체의 메모리 참조를 정수 형식으로 반환합니다. 메소드로부터 받은 값이 버킷 번호로 사용됩니다. 버킷 번호는 맵 내부 요소의 주소입니다. null Key의 해시 코드는 0입니다.버킷:노드 배열을 버킷이라고 합니다. 각 노드에는 LinkedList와 같은 데이터 구조가 있습니다. 두 개 이상의 노드가 동일한 버킷을 공유할 수 있습니다. 용량이 다를 수 있습니다.

HashMap에 키, 값 쌍 삽입

우리는 HashMap에 Key와 Value 쌍을 삽입하기 위해 put() 메소드를 사용합니다. HashMap의 기본 크기는 16(0~15)입니다.

예

다음 예에서는 HashMap에 세 개의 (키, 값) 쌍을 삽입하려고 합니다.

 HashMap map = new HashMap(); map.put('Aman', 19); map.put('Sunny', 29); map.put('Ritesh', 39); 

키, 값 쌍이 HashMap에 저장될 인덱스를 살펴보겠습니다. put() 메소드를 호출하면 'Aman' 키의 해시 코드가 계산됩니다. 'Aman'의 해시 코드가 2657860이라고 가정합니다. Key를 메모리에 저장하려면 인덱스를 계산해야 합니다.

git pull 오리진 마스터

지수 계산 중

인덱스는 배열의 크기를 최소화합니다. 지수 계산 공식은 다음과 같습니다.

 Index = hashcode(Key) & (n-1) 

여기서 n은 배열의 크기입니다. 따라서 'Aman'의 인덱스 값은 다음과 같습니다.

 Index = 2657860 & (16-1) = 4 

값 4는 키와 값이 HashMap에 저장될 계산된 인덱스 값입니다.

해시 충돌

2개 이상의 Key에 대해 계산된 인덱스 값이 동일한 경우입니다. 또 다른 Key 'Sunny'의 해시 코드를 계산해 보겠습니다. 'Sunny'의 해시 코드가 63281940이라고 가정합니다. Key를 메모리에 저장하려면 인덱스 수식을 사용하여 인덱스를 계산해야 합니다.

 Index=63281940 & (16-1) = 4 

값 4는 키가 HashMap에 저장될 계산된 인덱스 값입니다. 이 경우, equals() 메소드는 두 키가 같은지 여부를 확인합니다. 키가 동일하면 값을 현재 값으로 바꿉니다. 그렇지 않으면 LinkedList를 통해 이 노드 개체를 기존 노드 개체에 연결합니다. 따라서 두 키는 모두 인덱스 4에 저장됩니다.

Java의 arraylist 정렬

마찬가지로 'Ritesh' 키를 저장하겠습니다. 키의 해시 코드가 2349873이라고 가정합니다. 인덱스 값은 1이 됩니다. 따라서 이 키는 인덱스 1에 저장됩니다.

HashMap의 get() 메소드

get() 메소드는 키로 값을 가져오는 데 사용됩니다. 키를 모르면 값을 가져오지 않습니다. get(K Key) 메소드가 호출되면 해당 키의 해시 코드를 계산합니다.

'Aman' 키를 가져와야 한다고 가정해 보겠습니다. 다음 메서드가 호출됩니다.

 map.get(new Key('Aman')); 

해시 코드는 2657860으로 생성됩니다. 이제 인덱스 공식을 사용하여 인덱스 값 2657860을 계산합니다. 위에서 계산한 대로 인덱스 값은 4가 됩니다. get() 메소드는 인덱스 값 4를 검색합니다. 첫 번째 요소인 Key를 주어진 Key와 비교합니다. 두 키가 모두 같으면 값을 반환하고 노드에 다음 요소가 있는지 확인합니다. 우리 시나리오에서는 노드의 첫 번째 요소로 발견되며 값 19를 반환합니다.

또 다른 Key 'Sunny'를 가져오겠습니다.

'Sunny' 키의 해시 코드는 63281940입니다. 계산된 인덱스 값 63281940은 put() 메서드에 대해 계산한 대로 4입니다. 배열의 인덱스 4로 이동하여 첫 번째 요소의 Key를 주어진 Key와 비교합니다. 또한 키를 비교합니다. 우리 시나리오에서는 주어진 Key가 두 번째 요소이고 노드의 다음 요소는 null입니다. 두 번째 요소 Key를 지정된 Key와 비교하고 값 29를 반환합니다. 노드의 다음 항목이 null이면 null을 반환합니다.