오랫동안 코드에서 더 자주 사용되는 데이터 목록은 주로 목록이며 모두 ArrayList입니다. 이건 충분하다고 느낍니다. ArrayList는 동적 배열을 구현하는 데 사용되는 래퍼 도구 클래스이므로 코드를 작성할 때는 입력 및 방향 및 트래버스를 끌어 올릴 수 있습니다.
Hashmap 및 Hashset과 같은 도구 클래스를 천천히 시작하기 시작한시기는 종종 코드에 나타납니다. 해시 맵이 더 일반적이며 고전적인 인터뷰 질문이기도하므로 일상 생활에서 더 많이 읽을 것입니다. 처음 사용하기 시작했을 때 단순히 키 값 대응 테이블로 이해했으며 키를 사용하여 데이터를 찾는 것이 더 편리합니다. 추가 조사 후, 나는 발견했다
이 문제는 특히 새로운 버전의 JDK 버전이 해시 맵을 트리로 변경 한 후 코드가 약간 복잡합니다.
세트를 적게 사용하기 시작했지만 실수로 코드에서 트리셋을 찾았습니다. 나는이 수업이 부드러움으로 올 수 있음을 발견했다. 꽤 흥미로운 느낌이 들었습니다. 나는 이것이 또한 좋은 도구라는 것을 점차적으로 발견했다.
코드를 너무 많이 쓰면 기본의 중요성을 느낄 수 있으므로 여기에 짧은 기사를 작성하여 컬렉션에 대한 지식을 간단히 구성합니다.
좋아, 간단히 정리해 봅시다 :
• 목록 : 즉, 배열 및 링크 된 목록의 함수를 지원하는 목록이며 일반적으로 선형입니다.
•지도 : 키와 값 사이의 해당 관계를 저장하는 매핑 테이블입니다.
• 세트 : 수단 세트, 주로 데이터를 정렬하고 정렬하는 데 사용됩니다.
먼저 목록을 살펴 보겠습니다
목록은 다음과 같은 선형 데이터를 저장하기위한 창입니다. : 배열 용 배열리스트 및 링크 된 목록의 링크드리스트.
배열 목록
이것은 배열 목록이지만 목록 인터페이스를 실현하기 위해 자동 확장 기능을 제공합니다. 외부 작업은 인터페이스 선언 방법을 통해 액세스하며 안전하고 편리합니다.
ArrayList의 핵심은 자동 용량 확장입니다. 객체가 초기화되거나 기본 용량을 측정 할 때 초기 용량을 설정할 수 있습니다. 배열 크기가 명확하지 않으면 초기 크기를 지정할 수 없습니다. 명확한 경우 크기를 지정하여 동적 확장으로 인한 지연이 줄어 듭니다. 이에 대해 말하면, 우리는 확장이 어떻게 구현되는지에 대해 이야기해야합니다. 다음 코드를보십시오.
Private Void Grow (int mincapacity) {// 오버 플로우에 민감한 코드 int OldCapacity = ElementData.length; int newCapacity = OldCapacity + (OldCapacity >> 1); if (newCapacity -MinCapacity <0) newCapacity = mincapacity; if (newCapacity -max_array_size> 0) newCapacity = hugecapacity (mincapacity); // mincapacity는 일반적으로 크기에 가깝기 때문에 이것은 다음과 같습니다. elementData = arrays.copyof (elementData, newCapacity); }Grow는 요소 또는 쉬운 점검을 추가 할 때 Arraylist를 트리거하는 방법입니다. 주요 과정 :
1. 배열의 길이를 가져 와서 올바른 Capacity/2에 해당하는 오른쪽으로 이동하고 새 길이를 얻으십시오.
2.이 길이가 최소 용량보다 작 으면 직접 사용하기 쉽습니다.
3. 최대보다 큰 경우 최대 값을 취하십시오. MinCapacity와 Max_Array_size를 비교하기 위해 HugeCapacity 방법이 여기에서 호출됩니다. mincapacity가 max_array_size보다 크면 integer.max_value를 가져 가면 max_array_size를 사용하십시오. 흥미롭게도 max_array_size는 정수를 가져옵니다 .max_value -8; 이 일의 의미가 무엇인지 모르겠습니다.
4. 마지막으로 복사 방법을 호출하여 기존 번호를 새 배열로 복사하십시오.
이 복사 프로세스로 인해 배열이 비교적 큰 경우 확장으로 인해 지연이 발생합니다. 따라서 처음부터 최대 값을 알고이 값으로 쉽게 성장하기가 쉽습니다. 초기화를 시작할 때 크기를 지정하면 특정 효과가 있습니다.
Linkedlist
링크 된 목록을위한 도구 클래스입니다. 링크 된 목록의 장점은 물건을 더 빨리 추가하고 삭제한다는 것입니다.
코드는 코드가 일련의 포인터로 연결되어 있다는 것이 특별한 것 같습니다. 물론 Java는 대신 객체를 사용하여 노드 객체를 만듭니다. 노드 자체는 이전 노드와 다음 노드를 가리 킵니다. 링크 된 목록의 구조입니다.
개인 정적 클래스 노드 <e> {e 항목; Node <e> 다음; 노드 <e> 이전; 노드 (Node <e> prev, e 요소, 노드 <e> next) {this.item = 요소; this.next = 다음; this.prev = 이전; }}그런 다음 두 개의 노드를 사용하여 머리와 꼬리를 가리키면 완료됩니다. 다음 코드 :
/*** 첫 번째 노드에 대한 포인터. * 불변 : (첫 번째 == null && last == null) || * (First.prev == null && first.Item! = null) */ 과도 노드 <E> 먼저; /*** 마지막 노드에 대한 포인터. * 불변 : (첫 번째 == null && last == null) || * (last.next == null && last.Item! = null) */ 과도 노드 <E> 마지막;
추가 작업 참조 :
/*** e를 마지막 요소로 연결합니다. */ void linklast (e e) {최종 노드 <e> l = 마지막; 최종 노드 <e> newnode = new Node <> (l, e, null); 마지막 = 뉴 노드; if (l == null) first = newnode; else l.next = newnode; 크기 ++; 모드 카운트 ++; }과거의 과거의 과거는 다음 과거입니다. 과거는 다음 과거입니다.
1. 마지막 노드를 가져 와서 l에 넣습니다.
2. 새 노드를 만들고 데이터를이 노드로 가져옵니다. 생성 프로세스는 새 노드의 이전을 L로 가리켜 체인에 연결되도록합니다.
3. 그런 다음이 새 노드를 마지막으로 가리 킵니다
4. 그런 다음 L이 널 여부를 결정하십시오. NULL이 NULL 인 경우 비어있는 링크 목록임을 의미합니다. 새 노드가 첫 번째 요소입니다. 이런 식으로 첫 번째는 NewNode를 가리켜 야합니다.
5. 비어 있지 않으면 L의 다음 L을 NewNode로 가리 킵니다.
6. 축적 카운터
삭제 작업은 또한이 노드의 이동 작업을 가리키는 전면 및 후면 노드입니다.
지도를 살펴 보겠습니다
맵은 키 및 값에 대한 매핑 테이블을 응용 프로그램으로 사용합니다. 주요 구현 클래스 : Hashmap, Hashtable, Treemap
해시 맵 및 해시 가능
Hashmap은 키 값 매핑에 해시 알고리즘을 사용하는 것입니다. Hashtable은 동기화 된 스레드 안전 클래스입니다. 이것이 그들 사이의 주요 차이점입니다. 원리는 비슷하며 버킷 + 체인 조합을 통해 달성됩니다. 버킷은 키를 저장하는 데 사용되며 해시 충돌로 인해 링크 목록에 값을 저장해야합니다.
• 버킷의 중요성은 효율성에 있으며 해시 계산을 통해 한 단계에 위치 할 수 있습니다.
• 링크 된 목록의 의미는 반복 된 해시의 데이터에 액세스하는 것입니다.
내가 "연구 노트 : Hashtable 및 Hashmap"을 쓴 특정 원리
그러나 방금 JDK1.8의 해시 맵이 저장 구조를 변경하고 빨간색과 검은 색 트리 구조를 채택한 것을 보았습니다. 링크 된 목록 검색의 효율성을 해결할 수 있습니까? 자세한 연구는 수행되지 않았습니다.
트리 맵
Treemap 코드를 읽은 후에도 나는 여전히 나무 구조, 빨간색과 검은 나무를 사용한다는 것을 알았습니다. 빨간색과 검은 색 나무가 주문되었으므로 자연스럽게 분류 기능이 있습니다. 물론 비교기를 통해 비교 방법을 지정하여 특정 분류를 달성 할 수 있습니다.
트리 구조는 저장하는 데 사용되므로 데이터를 추가하고 삭제하는 것이 더 번거 롭습니다. 풋 코드를 살펴 보겠습니다.
public v put (k key, v value) {enther <k, v> t = root; if (t == null) {비교 (키, 키); // type (및 가능한 null) Check root = new Entry <> (키, 값, null); 크기 = 1; 모드 카운트 ++; 널 리턴; } int cmp; 입력 <k, v> 부모; // 분할 비교기 및 비교 경로 비교기 <? 슈퍼 k> cpr = 비교기; if (cpr! = null) {do {parent = t; cmp = cpr.compare (key, t.key); if (cmp <0) t = t.left; 그렇지 않으면 (cmp> 0) t = t.right; 그렇지 않으면 t.setValue (value)를 반환합니다. } while (t! = null); } else {if (key == NULL) TRATH NULLPOONETEREXCEPTION (); @suppresswarnings ( "확인되지 않은") 비슷한 <? SUPER K> K = (비슷한 <? SUPER K>) 키; {parent = t; cmp = k.compareto (t.key); if (cmp <0) t = t.left; 그렇지 않으면 (cmp> 0) t = t.right; 그렇지 않으면 t.setValue (value)를 반환합니다. } while (t! = null); } entry <k, v> e = new Entry <> (키, 값, 부모); if (cmp <0) parent.left = e; else parent.right = e; fixafterinsertion (e); 크기 ++; 모드 카운트 ++; 널 리턴; }1. 먼저 루트 노드가 존재하는지 확인하십시오. 존재하지 않는 경우, 첫 번째 데이터이며 트리의 근본으로 직접 사용됨을 의미합니다.
2. 비교기가 있는지 여부를 결정하십시오. 있는 경우 비교기를 사용하여 데이터의 저장 위치를 찾으십시오. 비교기 반환 결과가 0보다 작은 경우 왼쪽을 가져 가서 오른쪽을 취하십시오. 그렇지 않으면 현재 노드의 값을 직접 교체하십시오.
3. 비교기가 없으면 키는 노드 키와 직접 비교됩니다. 비교는 이전 방법과 동일합니다.
4. 다음 단계는 발견 된 부모에 자식 노드를 만들어 왼쪽 또는 오른쪽 자식 노드에 넣는 것입니다.
5. FixAfterinsertion은 색상 노드입니다
6. 축합기 처리
또한 데이터를 제거 할 때는 약간 번거 롭습니다. 데이터를 삭제하는 것 외에도 빨간색과 검은 색 나무를 재조정해야합니다.
또한 Treemap은 NavigableMap <k, v> 인터페이스를 구현하므로 데이터 세트에서 일부 반환 작업을 제공합니다.
마지막으로 세트를 살펴보십시오
주로 세트에는 두 가지 유형의 응용 프로그램이 있습니다 : Hashset과 Treeset.
해시 세트
문자 적 의미는 해시 모음을 사용하여 매우 명확합니다. 이 컬렉션의 특징은 해시 알고리즘을 사용하여 데이터를 저장하는 것이므로 데이터가 복제되지 않고 액세스가 비교적 빠릅니다. 어떻게 끝났습니까?
public boolean add (e e) {return map.put (e, present) == null; }맵 객체가있는 것으로 밝혀졌습니다. 지도가 무엇인지 살펴 보겠습니다.
개인 과도 해시 맵 <e, 객체>지도;
해시 맵입니다. 해시 맵을 아는 사람들은 그러한 데이터가 반복되지 않을 것이라는 것을 이해할 것입니다. 객체 자체가 입금 될 때 키로 저장되므로 해시 맵에는 하나의 사본 만 존재합니다.
이것과 다른 것들을 이해 한 후에는 잘 이해할 것입니다.
트리 셋
이 세트는 세트를 정렬하는 데 사용되며, 이는 무거운 정렬 기능 외에도 고유 한 정렬 기능을 가질 수 있음을 의미합니다. 그러나 TreeSet 코드를 살펴본 후 Treemap의 기본 사항에서 구현 된 것을 발견했습니다. 더 정확하게는, 이는 파생 된 클래스의 NavigableMap이어야합니다. TreeSet은 기본적으로 맵을 지정하지 않고 Treemap을 기반으로합니다.
public treeset () {this (new treemap <e, object> ()); }그렇다면, 우리가 여기에 더 많은 관심을 기울일 수있는 것은 트리 셋이 어떻게 무거워 지는가? 추가 방법을 살펴 보겠습니다.
public boolean add (e e) {return m.put (e, present) == null; }해시 세트와 다소 유사하며, 둘 다 무거운 하중을 달성하기위한 맵의 특징을 기반으로합니다. 정말 간단하고 효과적입니다.
위의 내용은 편집자가 당신에게 가져 오는 Java의 세트, 목록 및지도에 대한 자세한 설명입니다. wulin.com을 더 지원할 수 있기를 바랍니다 ~