이 기사에서는 LinkedHashMap의 소스 코드를 분석하기 시작했습니다. LinkedHashMap은 HASHMAP를 상속합니다. 즉, LinkedHashMap은 해시 맵을 기반으로 확장됩니다. 따라서 LinkedHashMap의 소스 코드를보기 전에 독자는 해시 맵의 소스 코드를 이해해야합니다. 이전 기사 "Java Collection Series [3] ---- 해시 맵 소스 코드 분석"의 소개를 확인할 수 있습니다. 해시 맵의 구현 원리를 깊이 이해 한 다음 LinkedHashmap의 소스 코드, Hashset 및 LinkedHashSet의 소스 코드를 살펴보면 모두 매우 간단합니다. 따라서 독자는 인내심을 갖고 해시 맵 소스 코드를 연구해야합니다. 이것은 하나를 구매하는 좋은 사업입니다. 해시 맵 소스 코드를 이전에 분석 할 때 소스 코드의 문제 지향 분석을 사용하여 헤드리스 플라이처럼 무작위로 분석하지 않도록 독자는 문제에 대해 더 깊이 이해할 수있었습니다. 이 기사에서는이 방법을 사용하여 LinkedHashMap을 분석하기로 결정했습니다.
1. LinkedHashmap 내부에는 어떤 구조가 사용됩니까?
보시다시피 LinkedHashMap은 Hashmap에서 상속되므로 LinkedHashMap 내부에는 여전히 해시 테이블이 있지만 LinkedHashMap은 항목을 다시 작성하고 원래 해시 맵 항목, 즉 이전 노드 참조 및 후속 노드 참조에 두 멤버 변수를 추가했습니다. 이런 식으로 모든 노드는 함께 연결되어 양방향 링크 목록을 형성합니다. 요소를 얻을 때는 양방향 링크 목록을 직접 가로 지르십시오. Entry의 LinkedHashMap 구현이 어떻게 보이는지 봅시다.
개인 정적 클래스 항목 <k, v>는 hashmap.entry <k, v> {// 양방향 링크 링크 목록 입력 <k, v> 이전; // 양방향 링크 링크 목록 항목에서 전류 노드의 후속 노드의 참조 <k, v> 이후; Entry (int Hash, k key, v value, hashmap.entry <k, v> next) {super (해시, 키, 값, 다음); } // 양방향 링크 링크 목록 에서이 노드를 제거하십시오 비공개 void void remove () {prever.after = After; 후. } // 양방향 링크 링크 목록의 기존 노드에 전류 노드를 삽입 개인 void addbefore (Entry <k, v> exciententingentry) {// 현재 노드의 다음 노드의 참조는 주어진 노드에 대한 = 기존 노드; // 현재 노드의 이전 노드의 참조는 주어진 노드의 이전 노드를 가리 킵니다. // 주어진 노드의 다음 노드의 참조는 이전 노드를 가리 킵니다. // 주어진 노드의 이전 노드의 참조는 다음 후 현재 노드를 가리 킵니다. } // 액세스 순서대로 정렬 된, 작업이 획득 될 때마다 기록 된 레코드 어택시 (hashmap <k, v> m) {linkedhashmap <k, v> lm = (linkedhashmap <k, v>) m; // 액세스 순서로 정렬 된 경우 if (lm.accessorder) {lm.modcount ++; // 먼저 양방향 링크리스트에서 자신을 제거합니다. // 양방향 링크 링크 목록의 꼬리에 자신을 두십시오 (lm.header); }} void RecordRemoval (Hashmap <k, v> m) {remove (); }}2. LinkedHashMap은 어떻게 삽입 순서로 정렬을 구현합니까?
// 상위 클래스의 퍼팅 메소드에서 호출되는 메소드 void addentry (int Hash, k key, v value, int bucketIndex) {// 부모 클래스 Super.addentry (Hash, key, value, bucketIndex)의 addentry 메소드 호출; // 다음 작업은 LRU 캐시 구현에 편리합니다. 캐시 용량이 불충분 한 경우 가장 오래된 요소 항목 <k, v> 노인 = 헤더를 제거하십시오. if (removeEldestEntry (eldest)) {removeAntryforkey (eldest.key); }} // 메소드 void createEntry (int hash, k key, v value, int bucketIndex) {// 먼저 hashmap.entry <k, v> old = table [buctIndex]의 항목 해시 맵을 가져옵니다. // linkedhashmap의 자체 항목으로 래핑 <k, v> e = new entry <> (해시, 키, 값, 구형); 표 [bucetIndex] = e; // 양방향 연결된 목록의 꼬리에 현재 노드를 삽입 e.addbefore (헤더); 크기 ++;}LinkedHashMap은 부모 클래스 해시 맵의 AddEntry 및 CreateEntry 메소드를 무시합니다. 키 값 쌍을 삽입하려면 부모 클래스 해시 맵의 PUT 메소드가 먼저 호출됩니다. PUT 방법에서는 해시 테이블에 해당 키가 존재하는지 확인합니다. 존재하는 경우 그 값을 직접 교체하십시오. 존재하지 않는 경우 Addentry 메소드를 호출하여 새 항목을 작성하십시오. 현재 LinkedHashMap의 자체 Addentry 메소드가 호출됩니다. 위의 코드가 보입니다. 이 AddEldestry는 부모 클래스의 AddEldestentry 메소드를 다시 호출하는 것 외에도 가장 오래된 요소를 제거하기 위해 RemogEldestentry를 호출합니다. 이 작업은 주로 LRU 알고리즘을 구현하기위한 것입니다. LinkedHashMap도 CreateEntry 메소드를 다시 작성합니다. 새 항목을 만들려면이 메소드가 호출됩니다. 항목이 해시 테이블에 넣을 때마다 추가 메소드를 호출하여 현재 노드를 양방향 연결된 목록의 꼬리에 삽입합니다. 이러한 방식으로, 양방향 링크 된 목록은 삽입 된 각 노드의 순서를 기록합니다. 요소를 얻을 때는 양방향 링크 된 목록을 가로 지르십시오. 다음 그림은 addbefore에 대한 각 호출의 작동을 보여줍니다. 양방향 링크 목록이므로 전류 노드를 헤드 노드에 삽입하기 전에 실제로 현재 노드를 양방향 연결된 목록의 꼬리에 삽입합니다.
3. Linkedhashmap을 사용하여 LRU 캐시를 구현하는 방법은 무엇입니까?
캐시의 구현은 컴퓨터의 메모리에 달려 있으며 메모리 리소스가 상당히 제한되어 있으며 제한없이 요소를 저장하는 것은 불가능합니다. 따라서 용량이 충분하지 않은 경우 일부 요소를 적절하게 삭제해야합니다. 그렇다면 어떤 요소가 삭제하는 것이 더 낫습니까? LRU 알고리즘에 대한 아이디어는 최근에 데이터에 액세스되면 미래에 액세스 할 가능성도 높다는 것입니다. 따라서 종종 액세스되지 않은 데이터를 삭제할 수 있습니다. 다음으로 LinkedHashmap이 LRU 메커니즘을 어떻게 구현하는지 살펴 보겠습니다.
공개 클래스 LinkedHashMap <k, v> 확장 해시 맵 <k, v> 구현 맵 <k, v> {// 링크 된 목록 헤드러 개인 과도 입력 <k, v> 헤더; // 액세스 순서대로 개인 최종 부울 accessorder를 정렬합니다. ... public linkedhashmap (int initialcapacity, float loadfactor, boolean accessorder) {super (InitialCapacity, loadfactor); this.accessorder = accessorder; } // key public v get (객체 키)에 따라 값을 가져옵니다. {// 상위 클래스 메소드를 호출하여 해당 항목 입력을 얻습니다. if (e == null) {return null; } // 액세스 순서로 정렬되면 각 사용 후 노드는 양방향 연결된 목록의 끝에 배치됩니다. e.recordAccess (this); return e.value; } 개인 정적 클래스 항목 <k, v>는 hashmap.entry <k, v> {... // 현재 노드를 기존 노드 앞에 삽입 한 링크어링 된 목록 개인 void addbefore (Entry <k, v> 기존) {// 주어진 노드에 대한 다음 노드의 참조가 주어진 노드에 대한 참조; // 현재 노드의 이전 노드의 참조는 주어진 노드의 이전 노드를 가리 킵니다. // 주어진 노드의 다음 노드의 참조는 이전 노드를 가리 킵니다. // 주어진 노드의 이전 노드의 참조는 다음 후 현재 노드를 가리 킵니다. } // 액세스 순서대로 정렬 된, 조작 void recordAccess (hashmap <k, v> m) {linkedhashmap <k, v> lm = (linkedhashmap <k, v>) m; // 액세스 순서로 정렬 된 경우 if (lm.accessorder) {lm.modcount ++; // 먼저 양방향 링크리스트에서 자신을 제거합니다. // 양방향 링크 링크 목록의 꼬리에 자신을 두십시오 (lm.header); }} ...} //이 메소드는 상위 클래스 PUT 메소드 void addentry (int Hash, k key, v value, int bucketIndex)에서 호출됩니다. {// 부모 클래스의 addentry 메소드 super.addentry (hash, key, value, bucketindex); // 다음 작업은 LRU 캐시 구현에 편리합니다. 캐시 용량이 불충분 한 경우 가장 오래된 요소 항목 <k, v> 노인 = 헤더를 제거하십시오. if (removeEldestEntry (eldest)) {removeEldestforKey (eldest.key); }} // 가장 오래된 요소는 어디에서 삭제해야합니까? 이 방법은 서브 클래스 보호 된 부울 removeLedestry (Map.Entry <k, v> 노인) {return false; }}더 직관적으로 위에 게시 된 코드에서 관련없는 코드를 생략했습니다. LinkedHashMap에는 멤버 변수 액세서더가 있으며 액세스 순서대로 정렬 해야하는지 여부를 기록합니다. Accessorder 자체의 값을 지정할 수있는 생성자를 제공합니다. 요소를 얻기 위해 get 메소드를 호출 할 때마다 E.recordaccess (this)가 호출되며, 이는 현재 노드를 양방향 링크 된 목록의 끝으로 이동합니다. 이제 우리는 AccessOrder가 참이면 요소를 얻을 때 마다이 요소를 양방향 링크 목록의 끝으로 이동할 것임을 알고 있습니다. 이 단계의 목적은 가장 일반적으로 사용되는 요소를 자주 사용하지 않는 요소와 구별하는 것입니다. 종종 사용되는 요소는 끝에 배치되고 덜 일반적으로 사용되는 요소가 헤드에 배치됩니다. 위의 코드로 돌아가서 Addentry 메소드가 호출 될 때마다 가장 오래된 요소를 삭제 해야하는지 여부를 결정합니다. 판단의 논리는 removeeldestry에 의해 구현되며, 서브 클래스로 재정의하고 내부로 논리를 다시 작성하도록 설계되었습니다. 최근에 방문한 노드가 양방향 링크리스트의 꼬리로 이동되므로 가장 오래된 노드는 삭제를 위해 양방향 링크 링크 목록의 헤드에서 꺼집니다. 다음 예제는 간단한 LRU 캐시를 구현합니다.
공개 클래스 lrumap <k, v>는 LinkedHashMap <k, v> {개인 int 용량; lrumap (int capacity) {// 부모 클래스 생성자를 호출하고 액세스 순서로 정렬하도록 설정 (용량, 1f, true); this.capacity = 용량; } @override public boolean removeeldestentry (map.entry <k, v> 노인) {// 키 값 쌍이 해시 테이블 용량보다 크거나 동일 할 때 this.size ()> = 용량; } public static void main (string [] args) {lrumap <integer, string> map = new lrumap <integer, string> (4); map.put (1, "a"); map.put (2, "b"); map.put (3, "c"); System.out.println ( "원본 컬렉션 :" + 맵); 문자열 s = map.get (2); System.out.println ( "get element :" + map); map.put (4, "d"); System.out.println ( "삽입 후 :" + map); }}결과는 다음과 같습니다.
참고 : 위의 모든 분석은 JDK1.7을 기반으로하며 다른 버전간에 차이가있을 것이므로 독자는주의를 기울여야합니다.
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.