멀티태스킹 Java의 Set, List, Map 상세 정보
언제부터 천천히 코드에 HashMap이나 HashSet 같은 도구 종류가 자주 등장할지 모르겠다.HashMap이 비교적 많다고 해야 할 뿐만 아니라 면접 명제이기 때문에 평소에도 많이 본다.사용하기 시작할 때 간단하게 이해하면 키 값 대응표이기 때문에 키를 사용하여 데이터를 찾는 것이 비교적 편리하다.나중에 자세히 알아보면
이 물건은 아직 약간의 비밀이 있다. 특히 새로운 버전의 JDK가 HashMap을 나무로 바꾸자 코드가 약간 복잡하다.
Set은 비교적 적게 사용하기 시작했는데 무심결에 하나의 코드에서 TreeSet을 발견했습니다. 이 종류가 순조롭게 진행될 수 있다는 것을 발견하고 약간 재미있어서 천천히 발견했습니다. 이것도 좋은 도구입니다.
코드를 많이 쓰면 기초의 중요성을 느끼기 때문에 여기에 작은 글을 써서 집합에 대한 지식을 간단하게 정리한다.
자, 간단하게 정리해 봅시다.
• List: 목록, 수조, 체인 테이블의 기능을 지원하며 일반적으로 선형이다
• Map: 매핑 테이블입니다. 키와 값의 대응 관계를 저장합니다.
• Set: 집합이라는 뜻으로 주로 데이터 배열 및 정렬에 사용된다
일단 List를 볼게요.
List는 선형 데이터를 저장하는 창입니다. 예를 들어 그룹을 위한 ArrayList와 체인 테이블에 사용되는 LinkedList입니다.
ArrayList
이것은 수조 목록이지만 자동 용량 확장 기능을 제공하여 List 인터페이스를 실현하고 외부 조작은 모두 인터페이스를 통해 설명하는 방법으로 접근하여 안전하고 편리하게 한다.
ArrayList의 관건은 자동 확장이다. 대상을 초기화할 때 초기 용량을 설정할 수도 있고 기본 용량에 따라 설정할 수도 있다.그룹 크기가 특별히 명확하지 않으면 초기 크기를 지정하지 않을 수 있고, 명확하면 크기를 지정하여 동적 확장을 줄일 수 있습니다.이쯤 되면 확장이 어떻게 이루어졌는지 다음 코드를 보세요.
private void grow(int minCapacity) {
// overflow-conscious code
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 is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}1. 수조의 길이를 얻어 오른쪽으로 옮기면 oldCapacity/2에 해당하고 새로운 길이를 얻는다
2、이 길이가 최소 용량보다 작으면 직접 최소로 사용하기 쉽다
3. 최대치보다 크면 최대치를 얻을 수 있습니다. 여기는 hugeCapacity 방법을 사용합니다. 주로 minCapacity와 MAX_를 비교합니다.ARRAY_SIZE의, minCapacity가 MAX보다 크면 _ARRAY_SIZE는 Integer를 사용합니다.MAX_VALUE, 그렇지 않으면 MAX_ARRAY_SIZE, 재미있는 건 MAX_ARRAY_SIZE는 Integer를 사용합니다.MAX_VALUE - 8;이렇게 하는 의미가 뭔지 모르겠어요.
4. 마지막으로 기존 수를 새로운 그룹에 복사하는 복제 방법을 사용합니다.
이 복제 과정이 있기 때문에 수조가 비교적 크면 자꾸 확장을 촉발하면 당연히 끊기는 상황이 발생한다.따라서 처음부터 최대치를 알고 이 값으로 성장하기 쉽다면 초기화를 시작할 때 크기를 지정하는 것이 어느 정도 작용한다.
LinkedList
이것은 체인 시계를 대상으로 하는 도구 종류입니다. 체인 시계의 우수성은 삭제를 추가하는 것이 비교적 빠르지만 찾기가 느릴 수 있습니다.
코드에 대해서도 특별한 것은 없는 것 같다. 바로 바늘로 연결된 것이다. 물론 자바에서는 대상을 사용하여 대체하고 노드의 대상을 구축한다. 노드 자체가 앞의 노드와 뒤의 노드를 가리킨다. 이것이 바로 체인 테이블의 구조이다.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}1. 마지막 Node를 가져와 l에 놓기
2. 새 Node를 만들고 이 Node에서 데이터를 가져옵니다. 생성 과정에서 새 Node의prev를 l로 가리키면 체인이 연결됩니다.
3. 그리고 last를 이 새 Node로 가리키기
4. l가 null인지 아닌지를 판단한다. null이 빈 체인표라면 새로운 node가 첫 번째 요소이다. 이렇게 하면first도 newNode를 가리켜야 한다
5. 비어 있지 않으면 l의 next를 newNode로 가리킨다
6. 누적 계수기
삭제 작업도 이러한 Node의 앞뒤 Node가 이동을 가리키는 작업입니다.
맵 한 번 더 볼게요.
맵은 키와 값이 하나의 맵을 만드는 응용 프로그램으로 주요한 실현 클래스: HashMap, HashTable, TreeMap
HashMap 및 HashTable
hash 알고리즘을 사용하여 키 값을 비추는 것이 바로 HashMap입니다. HashTable은 동기화된 스레드가 있는 안전한 클래스입니다. 두 가지 주요 차이점은 바로 이것입니다.원리도 유사하다. 모두 통+사슬을 통해 조합되어 이루어진다.통은 키를 저장하는 데 사용되며, Hash 충돌의 원인 값은 체인 시계로 저장해야 한다.
• 배럴의 의미는 효율적이고 Hash 컴퓨팅을 통해 한 번에 위치를 정할 수 있다는 데 있다
• 체인 테이블의 의미는 중복된hash 데이터를 저장하는 데 있다
구체적인 원리는 이전에 《학습노트:Hashtable과 HashMap》을 쓴 적이 있다.
단지 JDK1.8의 HashMap이 저장 구조를 바꾸고 붉은색과 검은색 나무의 구조를 채택한 것을 보면 체인 테이블의 검색 효율 문제를 해결할 수 있겠지?구체적으로는 세밀한 연구가 없다.
TreeMap
트리맵 코드를 보니 트리 구조, 붉은색과 검은색 트리가 그대로 사용됩니다.붉은색과 검은색 나무는 질서가 있기 때문에 자연적으로 정렬 기능을 가지고 있다.물론comparator를 통해 비교 방법을 지정하여 특정한 정렬을 실현할 수도 있다.
트리 구조로 저장되어 있기 때문에 데이터를 추가하고 삭제할 때 좀 번거롭습니다.put 코드를 보십시오.
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}2. 비교기 존재 여부를 판단하고 존재하면 비교기를 사용하여 데이터의 저장 위치를 찾습니다. 비교기 반환 결과가 0보다 작으면 왼쪽, 0보다 크면 오른쪽, 그렇지 않으면 현재 노드의 값을 직접 바꿉니다.
3. 비교기가 존재하지 않으면 키는 노드의 키와 직접 비교하고 비교는 앞의 방법과 같다
4. 다음은 찾은parent에 하위 노드를 만들고 왼쪽 또는 오른쪽 하위 노드에 넣는다
5, fixAfterInsertion은 노드를 음영처리합니다.
6. 누적기 처리
리무브를 조작할 때도 약간의 번거로움이 있습니다. 데이터를 삭제하는 것 외에 빨간색과 검은색 트리를 다시 균형 있게 해야 합니다.
또한 TreeMap은 NavigableMap
마지막으로 셋.
Set은 주로 두 가지 응용 프로그램입니다: HashSet과 TreeSet.
HashSet
글자의 뜻이 명확해서 Hash의 집합을 사용했다.이런 집합의 특징은 바로 Hash 알고리즘을 사용하여 데이터를 저장하기 때문에 데이터가 중복되지 않고 접근이 비교적 빠르다는 것이다.어떻게 했지?
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
private transient HashMap<E,Object> map;이 점을 알고 다른 것을 알게 되면 아주 잘 알게 될 것이다.
TreeSet
이 집합은 집합을 정렬하는 데 쓰인다. 즉, 무게를 배열하는 능력을 제외하고는 스스로 정렬 기능을 할 수 있다.다만 트리셋의 코드를 보면 트리맵의 기초에서 이루어진 것이다.더 정확히 말하면 Navigable Map의 파생류일 거예요.기본적으로 맵을 지정하지 않는 경우 TreeSet은 TreeMap을 기반으로 합니다.
public TreeSet() {
this(new TreeMap<E,Object>());
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}지금까지 여러분을 위해 가져온 다용도 다학의 자바 중 Set, List, Map의 모든 내용을 상세히 설명했습니다. 많은 응원 부탁드립니다~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
38. Java의 Leetcode 솔루션텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
