먼저 인터뷰 질문을 살펴 보겠습니다.
해시 맵에 저장된 일련의 키 값 쌍은 키가 사용자 정의하는 특정 유형입니다. 해시 맵을 넣은 후 키의 속성을 외부 적으로 변경 한 다음이 키를 사용하여 해시 맵에서 요소를 제거합니다. 현재 해시 맵은 무엇을 반환합니까?
이 기사에서 샘플 코드와 답변이 주어졌지만 해시 맵의 원리에 대한 설명은 없습니다.
1. 기능
우리는 클래스를 해시 맵 키로 사용할 수 있지만이 클래스의 제한 사항은 무엇입니까? 다음 코드를 살펴 보겠습니다.
공개 클래스 사람 {개인 문자열 이름; 공개 사람 (문자열 이름) {this.name = 이름; }} map <person, string> testmap = new Hashmap <> (); testmap.put (새 사람 ( "hello"), "world"); testmap.get (새 사람 ( "hello")); // ---> null원래 필드 값이 동일한 사람 클래스의 값을 얻고 싶었지만 결과는 Null이었습니다. Hashmap에 대한 지식이 거의없는 사람은 Person 클래스에 Override Hashcode 메소드가 없으므로 객체 해시 코드의 상속을 초래합니다 (리턴은 메모리 주소입니다). 이것은 또한 문자열 (또는 정수 등)과 같은 불변 클래스가 일반적으로 해시 맵의 키로 사용되는 이유입니다. 그렇다면 Hashmap은 어떻게 해시 코드를 사용하여 키를 빠르게 색인합니까?
2. 원리
먼저 "Java in Java"에서 간단한 해시 맵 구현 솔루션을 살펴 보겠습니다.
// : 컨테이너/simplehashmap.java // 시연 해시 맵. import java.util. // 물리적 인 제네릭 배열을 가질 수는 없지만 @SuppressWarnings ( "Checked Uneched") LinkedList <mapentry <k, v >> [] 버킷 = 새로운 LinkedList [size]; public v put (k key, v value) {v OldValue = null; int index = math.abs (key.hashcode ()) % 크기; if (버킷 [index] == null) 버킷 [index] = new LinkedList <mapentry <k, v >> (); LinkedList <MapEntry <k, v >> 버킷 = 버킷 [색인]; mapentry <k, v> pair = new mapentry <k, v> (키, 값); 부울 발견 = 거짓; Listiterator <mapentry <k, v >> it = bucket.listiterator (); while (it.hasnext ()) {mapentry <k, v> ipair = it.next (); if (ipair.getKey (). Equals (key)) {OldValue = ipair.getValue (); it.set (쌍); // Old를 New Found = True로 바꾸십시오. 부서지다; }} if (! found) 버킷 [index] .add (쌍); OldValue를 반환하십시오. } public v get (객체 키) {int index = math.abs (key.hashcode ()) % 크기; if (버킷 [index] == null) return null; for (mapentry <k, v> ipair : 버킷 [index]) if (ipair.getkey (). equals (key)) return ipair.getValue (); 널 리턴; } public set <map.entry <k, v >> entryset () {set <map.entry <k, v >> set = new Hashset <map.entry <k, v >> (); for (linkedlist <mapentry <k, v >> 버킷 : 버킷) {if (bucket == null) 계속; for (mapentry <k, v> mpair : bucket) set.add (mpair); } 반환 세트; } public static void main (String [] args) {SimpleHashMap <String, String> M = new SimpleHashMap <String, String> (); M.putall (국가 .capitals (25)); System.out.println (M); System.out.println (M.get ( "Eritrea")); System.out.println (M.EntrySet ()); }}Simplehashmap은 키를 저장하기 위해 해시 테이블을 구성합니다. 해시 함수는 모듈러스 작동 math.abs (key.hashcode ()) %크기이며, 링크 된 목록 메소드를 사용하여 해시 충돌이 해결됩니다. 버킷의 각 슬롯은 아래 그림과 같이 맵을 동일하게 (해시) 인덱스 값으로 저장합니다.
JDK의 해시 맵의 구현 원리는 그와 유사하며, 이와 유사하며, 체인 주소의 해시 테이블을 사용하여 Map.entry :
/*** 테이블, 필요에 따라 크기가 조정되었습니다. 길이는 항상 2의 힘이어야합니다. */과도 항목 <k, v> [] table = (Entry <k, v> []) empty_table; 정적 클래스 항목 <k, v> emp.Entry <k, v> {최종 K 키; v 값; 입력 <k, v> 다음; int 해시; …}Map.entry의 색인은 키의 해시 코드를 해싱하여 얻습니다. 키에 해당하는 값을 얻으려면 키에 대한 색인을 계산 한 다음 테이블에서 맵을 가져와 가져옵니다. 자세한 내용은 코드를 참조하십시오.
public v get (Object Key) {if (key == null) return getFornUllKey (); Entry <k, v> entry = getentry (키); return null == Entry? NULL : entry.getValue ();} 최종 항목 <k, v> getEntry (개체 키) {if (size == 0) {return null; } int hash = (key == null)? 0 : 해시 (키); for (Entry <k, v> e = table [indexfor (hash, table.length)]; e! = null; e = e.next) {object k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k))) return e; } return null;}해시 코드는 해시 맵의 해시 기능의 효율에 직접적인 영향을 미친다는 것을 알 수 있습니다. 좋은 해시 코드는 해시 충돌을 크게 줄이고 쿼리 성능을 향상시킵니다. 동시에, 이것은 처음에 제기 된 두 가지 질문을 설명합니다. 사용자 정의 클래스가 해시 맵 키를 사용하는 경우 해시 코드 계산은 생성자의 모든 필드를 커버해야합니다. 그렇지 않으면 NULL을 얻을 수 있습니다.